巡回セールスマン問題（分割法）

ruby test.rb　ケーススタディファイル名

と入力してやれば実行できます．ケーススタディファイルは，たとえば，同じ問題を乱数の初期値を変えて実行したいような場合に効果的であり，たとえば以下のような形式で作成します．

問題の数 2
問題 data\pr439.tsp 繰り返し回数 10
問題 data\kroA100.tsp 繰り返し回数 10		

　　日本語で記述した部分（「問題の数」，「問題」等）は，次に続くデータの説明ですのでどのように修正しても構いませんが，削除したり，または，複数の文（間に半角のスペースを入れる）にするようなことはしないでください（以下の説明においても同様）．各データの意味は以下に示す通りです．

問題の数

問題の数を入力します．この例では 2 となっています．

問題

各問題の始まりであり，上で与えた問題の数だけ以下のデータが繰り返されます．この項には，データファイル名を入力します（上の例では，data\pr439.tsp と data\kroA100.tsp ）．

繰り返し回数

同じ問題を，乱数の初期値を変えて何回実行するかを示します．得られた結果の平均等によって，最終的な結論としたいような場合に利用します．

　　データファイルは，問題自身とその解法の詳細を記述するためのファイルであり，たとえば以下のように記述します．

都市の数 439 選択方法(0:最良，1:最初) 1 近傍（2or3） 3 整数 1
出力(0:ディスプレイ，1:ファイル) -1 出力ファイル名 result\pr439
分割数 Ｘ 4 Ｙ 3 最大試行回数 1000
7125 11300
7225 11050
         ･････
1775 5375
2075 6475		

　　各データの意味は以下に示す通りです．

都市の数

　　都市の数を入力します

選択方法(0:最良，1:最初)

　　分割された各領域の最適値を逐次改善法を利用して求めます．逐次改善法においては，λ近傍に含まれる（λ本の）枝を入れ替えるという作業を距離の改善がなされなくなるまで続けることによって，解を求めます．各ステップにおいて，どのλ本の枝を入れ替えるかを探索していきますが，ここに 0 を入力すると，λ本の枝を入れ替えるすべての組み合わせの内，最も改善度が高いものを選択します．また，1 を入力すると，最初に見つかったλ本の枝をすぐ入れ替えます．通常，1 で良いと思います．

近傍（2or3）

　　λの値を入力してください，利用できるのは 2 または 3 だけです．

整数

　　各都市の位置情報（ x 座標と y 座標）の入力方法と都市間距離の計算方法を指定します．

=1 : 位置情報は整数，距離は整数計算

=-1 : 位置情報は実数，距離は整数計算

=-2 : 位置情報は実数，距離を実数計算

出力(0:ディスプレイ，1:ファイル)

　　結果の出力方法を入力します．

=-1 : 得られた経路長だけを画面に表示します

=0 : 経路長と巡回する都市の順番を画面に表示します

=1 : 得られた経路長だけをファイルに保存します．なお，保存は，追加（ append ）形式で行われます．

=2 : 経路長と巡回する都市の順番をファイルに保存します．なお，保存は，追加（ append ）形式で行われます．

出力ファイル名

　　結果を保存するファイル名です．なお，画面に出力する場合は必要ありません（入力しても無視）．

分割数 Ｘ

　　x 軸方向の分割数です．1 （分割しない）以上の値を入力してください．この例に場合は，4 分割します．

Ｙ

　　y 軸方向の分割数です．1 （分割しない）以上の値を入力してください．この例の場合は，3 分割します．

最大試行回数

　　逐次改善法における最大試行回数です．もちろん，この回数より少ない回数で改善が不可能になればその時点で終了します．

7125 11300

　　･････

　　以下，各都市の x 座標と y 座標です．都市の数だけ必要になります．この入力された順番が，その都市の都市番号になります（ 0 から始まる）．

　　結果を画面に出力する場合，乱数の初期値が変化する毎に入力待ちの状態になります．また，都市の順番も出力する場合は，10 都市出力する毎に入力待ちの状態になります．return キーを入力すれば継続されます．