3

TSP を解決するために、Clarke-Wright huristic を実装しました (疑似コードhereに基づく)。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

これは、スペースが問題になる場合に実行できることです (計算速度が少し低下する可能性があります)。

私はあなたのコードを実際には調べていませんが、疑似コードから判断すると、これでうまくいくはずです:

各ペアまたはポイントについて、それらを接続することによって生じる節約を計算します。

これがこれまでに見つかった最高の節約よりも優れている場合は、最高の節約を更新し、2 つのポイントを覚えておいてください。

すべてのペアをチェックした後、最適な節約を実装するだけです。

この方法では、余分なスペースはほとんど必要ありません。

于 2013-07-12T09:40:30.677 に答える