matlab - 如何在 Matlab 中优化 TSP 的 Clarke-Wright 启发式？

Question

我已经实现了 Clarke-Wright 启发法来解决 TSP(基于伪代码 here )。我已附上我在 Matlab 中的实现。然而，它对我来说不够快，并且需要 O(n²) 空间(因为成对距离)。我想知道是否可以应用任何理论或实践优化来降低复杂性(特别是空间复杂性)。如果有人能帮助我，我将不胜感激。

function [tour, length] = clarke_wright (data)

n=size(data,1); % number of records

center = mean(data,1); % mean of data

hubIdx = knnsearch(data,center,'k',1);  % nearest record to center

distances = dist(data,data');   % this requires O(n^2) space :(

savings = zeros(n);  % place to store the saving after adding an edge %

% Can be more vectorized? %
for i=1:n    
    if i==hubIdx
        continue;
    end
        savings(i,(i+1):n)=distances(i,hubIdx)+distances(hubIdx,(i+1):n)-distances(i,(i+1):n);
end

minParent = 1:n;

[~,si] = sort(savings(:),'descend');
si=si(1:(end/2));

Vh = zeros(1,n);
Vh(hubIdx) = 1;
VhCount = n-1;
degrees = zeros(1,n);

selectedIdx = 1;  % edge to try for insertion

tour = zeros(n,2);
curEdgeCount = 1;

while VhCount>2
    i = mod(si(selectedIdx)-1,n)+1;
    j = floor((si(selectedIdx)-1)/n)+1;

    if Vh(i)==0 && Vh(j)==0 && (minParent(i)~=minParent(j)) && i~=j && i~=hubIdx && j~=hubIdx     % always all degrees are <= 2, so it is not required to check them
%     if (minParent(i)~=minParent(j)) && isempty(find(degrees>2, 1)) && i~=j && i~=hubIdx && j~=hubIdx && Vh(i)==0 && Vh(j)==0
        degrees(i)=degrees(i)+1;
        degrees(j)=degrees(j)+1;
        tour(curEdgeCount,:) = [i,j];

        if minParent(i)<minParent(j)
            minParent(minParent==minParent(j))=minParent(i);
        else
            minParent(minParent==minParent(i))=minParent(j);            
        end


        curEdgeCount = curEdgeCount + 1;

        if degrees(i)==2
            Vh(i) = 1;
            VhCount = VhCount - 1;
        end

        if degrees(j)==2
            Vh(j) = 1;
            VhCount = VhCount - 1;
        end
    end
    selectedIdx = selectedIdx + 1;

end

remain = find(Vh==0);
n1=remain(1);
n2=remain(2);

tour(curEdgeCount,:) = [hubIdx n1];
curEdgeCount = curEdgeCount + 1;

tour(curEdgeCount,:) = [hubIdx n2];

tour = stitchTour(tour);
tour=tour(:,1)';
length=distances(tour(end),tour(1));
for i=1:n-1  % how can I vectorize these lines?
    length=length+distances(tour(i),tour(i+1));
end
end


function tour = stitchTour(t) % uniforms the tour [a b; b c; c d; d e;.... ]

n=size(t,1);

[~,nIdx] = sort(t(:,1));
t=t(nIdx,:);

tour(1,:) = t(1,:);
t(1,:) = -t(1,:);
lastNodeIdx = tour(1,2);

for i=2:n
    nextEdgeIdx = find(t(:,1)==lastNodeIdx,1);
    if ~isempty(nextEdgeIdx)
        tour(i,:) = t(nextEdgeIdx,:);
        t(nextEdgeIdx,:)=-t(nextEdgeIdx,:);
    else
        nextEdgeIdx = find(t(:,2)==lastNodeIdx,1);
        tour(i,:) = t(nextEdgeIdx,[2 1]);
        t(nextEdgeIdx,:)=-t(nextEdgeIdx,:);
    end
    lastNodeIdx = tour(i,2);
end


end

Answer 1

如果空间有问题，您可以这样做(可能会稍微降低计算速度)。

我没有真正研究过你的代码，但从伪代码来看，这应该可以解决问题:

对于每一对或每一点，计算通过连接它们所节省的成本。

如果这比迄今为止找到的最佳节省更好，请更新最佳节省，并记住两点。

检查完所有对后，只需实现最佳节省即可。

这样您就几乎不需要额外的空间。