3

我已经实现了 Clarke-Wright huristic 来解决 TSP（基于这里的伪代码）。我在 Matlab 中附加了我的实现。然而，它对我来说还不够快，并且占用了 O(n 2 ) 空间（因为成对距离）。我想知道是否可以应用任何理论或实际优化来降低复杂度（特别是空间复杂度）。如果有人可以帮助我，将不胜感激。

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
4

1 回答 1

1

如果空间是一个问题，这就是你可以做的（可能会降低计算速度）。

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

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

如果这比目前找到的最佳节省要好，请更新最佳节省，并记住这两点。

检查所有对后，只需执行最佳节省。

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

于 2013-07-12T09:40:30.677 回答