FinalDayII

巡回セールスマン問題とは，ある街から出発していくつかの街を次々とめぐって元の街に戻ってくる最短の経路を求める問題です．訪れる街の数が少ないときにはすべての経路を数え上げればいいのですが，数が増えるとその計算時間は指数関数的に増えてしまうと予想される問題です．このような問題はセールスマンだけでなく，コンピュータのCPUの配置や，都市ガスの配管設計などでも出会う問題です． 対象となる経路の長さの合計を >|ruby| def Energy(a)

 tmp=0.0;
 for i in 0..a.size-2 do
   tmp+=distance($city[a[i]],$city[a[i+1]])
 end
 return tmp

end

としておきます．ここでaはそれぞれの街の順番あるいは配置を示しています．$cityはそれぞれ街の座標で，大域変数として関数の外から直接呼び出しています．distanceは２次元ベクトルを受け取って距離を返します．すべての配置についてEnergy(a) を求めれば，最小値が求まります．あるいは初期の配置を

a = [0,1,2,3,...,N,0]

として，一定の手順で変更δa を加え，E(a +δa) が下がった場合にその配置を採用するという方法をとることも出来ます．しかし，この方法は極小値に落ちてしまうことが分かるでしょう．最小値を探すには時として坂を駆け登る必要があるのです．このような問題の一つの解法としてアニーリング法(simulated annealing)があります．これは格子欠陥を多く含んだ金属を高温へ上げて欠陥を掃き出し柔らかくする熱処理(焼きなまし，annealing)からの類推で名付けられた手法です．

アルゴリズム

アルゴリズムは以下のとおりです．

1. 配置aを仮定しE(a)を求める．
2. aからすこし違った配置a+δa を作る．
3. Δ E = E(a+δa)-E(a) を求める．
4. Δ E < 0 なら新たな配置を採用する．
5. Δ E > 0 なら新たな配置をexp(-Δ E/T) の確率で受け入れる．
6. 手順2以下を適当な回数繰り返す．

ここでT は温度から類推される制御パラメータで，十分大きい場合はすべての状態が採用されます．一方，Tを下げるにつれて採用される試行が少なくなり，徐々に状態が凍結されていきます．a+δa の生成方法とT の下げ方をうまく取れば最小値に近い状態が確率的に高く出現し，最小値かそれに近い状態へ落ち着くというアルゴリズムです．

計算例

ランダムに生成した16個の街に適用した巡回セールスマン問題の(a)初期配置，(b)Energy(a)が下がっていく様子，および(c) simulated annealingの計算結果．

街の位置をsafari(svg)で表示する方法

以下のようにroute.resに街の位置座標が順に保存されているとします． >|tcsh| [bob-no-MacBook-Pro:Ruby/Excer/final] bob% cat route.res 0.548813503927325 0.715189366372419 0.423654799338905 0.645894113066656 0.77815675094985 0.870012148246819 0.978618342232764 0.799158564216724 0.963662760501029 0.383441518825778 0.791725038082665 0.528894919752904 0.602763376071644 0.544883182996897 0.521848321750072 0.414661939990524 0.071036058197887 0.087129299701541 0.118274425868933 0.639921021327524 0.264555612104627 0.774233689434217 0.461479362252932 0.780529176286455 0.568044561093932 0.925596638292661 0.437587211262693 0.89177300078208 0.143353287409046 0.944668917049584 0.020218397440326 0.832619845547938 0.548813503927325 0.715189366372419

以下のようにしてsafari上でsvg(scalble vector graphics)で街の位置と経路(route)を表示する事が可能． >|tcsh| [bob-no-MacBook-Pro:Excer/TSP/svg] bob% ruby ./TSP_display.rb < route.res > test.svg [bob-no-MacBook-Pro:Excer/TSP/svg] bob% open -a safari test.svg

TSP_display.rbは以下の通り．

>|ruby| require 'pp' scale=400 city=[] ii=gets.chomp.split("\t") city<<[ii[0].to_f*scale,ii[1].to_f*scale] while (c=gets.chomp.split("\t")).size>1 do

 city<<[c[0].to_f*scale,c[1].to_f*scale]

end city<<[ii[0].to_f*scale,ii[1].to_f*scale]

1. pp city

points = [] city.each { |ele| points << "#{ele[0]},#{ele[1]}" }

1. pp points

data = "<svg xmlns=\"http://www.w3.org/2000/svg\"

    xmlns:xlink=\"http://www.w3.org/1999/xlink\" >
 <polyline fill=\"none\" stroke=\"#333\" stroke-width=\"1\"
   points = \"#{points.join(' ')}\" />

</svg>"

puts data

コピーしてTSP_display.rbとして保存すれば稼働する．コピーのときに"\\"がちゃんとバックスラッシュに変換してコピーされているか注意！！

街の位置をgnuplotで表示する方法gnuplot1

問題とヒント

1. 街の間の距離をあらかじめ計算して，2次元の配列に入れておき，配置a から任意に2都市を取りだして入れ替える試行をδa として上述のアルゴリズムにしたがって最短経路を探すプログラムを作成してください．
   1. 試行にともなうトータル距離の変化．
   2. 初期状態と最終状態のパス
2. ヒント:1..N_city-1の整数をランダムに生成する関数

    sel_city=rand(N_city-1)+1: