前回（n個の組み合わせを全部列挙してみる）で作ったプログラムを改造して巡回セールスマン問題用のプログラムを作ってみる。
まず巡回セールスマン問題とは、あるセールスマンが複数の都市を訪れるとき、どのような順番で巡回すれば最も効果的（時間、移動距離、交通費等）かを解くグラフ理論の有名な問題の一つ。この問題の難しい点は巡回する都市の数が多くなると計算量が爆発的に増えてしまい、コンピュータを用いての解析でさえ困難にしてしまう点にある。\(n\)個の都市を巡回する場合その組み合わせの数は\(n!\)となり、\(n\)が大きくなるにつれてあっという間に数が大きくなってしまう。具体的には
| n | n! | n | n! |
| 1 | 1 | 6 | 720 |
| 2 | 2 | 7 | 5040 |
| 3 | 6 | 8 | 40320 |
| 4 | 24 | 9 | 362880 |
| 5 | 120 | 10 | 3628800 |
こんな感じ。
前回作ったプログラムは\(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に重複を削除した組み合わせが代入されている。
コメント