全探索したデータから重複分を取り除く

前回(n個の組み合わせを全部列挙してみる)で作ったプログラムを改造して巡回セールスマン問題用のプログラムを作ってみる。

まず巡回セールスマン問題とは、あるセールスマンが複数の都市を訪れるとき、どのような順番で巡回すれば最も効果的(時間、移動距離、交通費等)かを解くグラフ理論の有名な問題の一つ。この問題の難しい点は巡回する都市の数が多くなると計算量が爆発的に増えてしまい、コンピュータを用いての解析でさえ困難にしてしまう点にある。\(n\)個の都市を巡回する場合その組み合わせの数は\(n!\)となり、\(n\)が大きくなるにつれてあっという間に数が大きくなってしまう。具体的には

nn!nn!
116720
2275040
36840320
4249362880
5120103628800

こんな感じ。

前回作ったプログラムは\(n\)個の点の組み合わせを総当たりで調べたので、今度は重複分を削除する。重複分を削除するために作成した関数は

function result = duplicate_check(data)
result=0;
c = arrayfun(@(x)length(find(data == x)), unique(data), 'Uniform', false);
if all(cell2mat(c)==1)
    result=1;
end
end

これを関数化して前回のソースコードに組み込めば

n=6;
data=zeros(1,6,n^n);
count=0;

for i=1:1:n
    for j=1:1:n
        for k=1:1:n
            for l=1:1:n
                for m=1:1:n
                    for o=1:1:n
                        temn=[i,j,k,l,m,o];
                        data(1,:,count+1)=temn;
                        clear temn
                        count=count+1;
                    end
                end
            end
        end
    end
end
clear i j k l m o count
count=0;

for i=1:1:n^n
    if duplicate_check(data(1,:,i))
        data2(1,:,count+1)=data(1,:,i);
        count=count+1;
    end
end

変数名が適当すぎるけど、data2に重複を削除した組み合わせが代入されている。

コメント

タイトルとURLをコピーしました