巡回セールスマン問題がおもしろそうなのでmatlabでシミュレーションしてみる #1
巡回セールスマン問題とは、あるセールスマンが複数の都市を訪れるとき、どのような順番で巡回すれば最も効果的(時間、移動距離、交通費等)かを解くグラフ理論の有名な問題の一つである。
この問題の難しい点は巡回する都市の数が多くなると計算量が爆発的に増えてしまい、コンピュータを用いての解析でさえ困難にしてしまう点にある。
今回は少ない有限の都市(以降ノード)を定義し、その点列について巡回セールスマン問題を考えていきたいと思う。
とりあえず次のプログラムでノードを設定することにする。
min=3; max=10; num=[min,max]; X=[-10,10]; Y=[-10,10]; A=randi(num); point=zeros(A,2); for i=1:1:length(point) point(i,:)=[randi(X),randi(Y)]; end B=randi([1,A]); startpoint=point(B,:);
都市といっても座標さえ与えてあればいいと思うのでこれで。
このプログラムは3~10個の整数の乱数を生成する。巡回セールスマン問題を解く上で都市(point)が10個もポイントがあれば十分だろう。
始点(startpoint)も乱数で与えられる。次回は組み合わせの個数を計算してみようと思う。