如何在Matlab中優化Clarke-Wright啓發式TSP？

我已經實施了Clarke-Wright的huristic解決TSP（基於僞代碼here）。我已經在Matlab中附加了我的實現。然而它對我來說不夠快，並且需要O（因配對距離）而導致空間不足O（n ）空間。我想知道是否可以應用任何理論或實際優化來降低複雜性（特別是空間複雜度）。如果有人能幫助我，我將不勝感激。如何在Matlab中優化Clarke-Wright啓發式TSP？

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

來源

2013-07-08 remo

這就是你可以做的，如果空間是一個問題（可能會降低計算速度）。

我還沒有真正看着你的代碼，但是從僞代碼這應該做的伎倆判斷：

對於每一對或點，計算通過連接它們產生的節餘。

如果這比迄今爲止發現的最佳儲蓄更好，請更新最佳儲蓄，並記住兩點。

檢查所有對後，只實施最佳節省。

這樣你幾乎不需要額外的空間。

來源

2013-07-12 09:40:30

如何在Matlab中優化Clarke-Wright啓發式TSP？

回答

相關問題