巡回セールスマン問題(逐次改善法)

  1. C/C++ によるプログラム

      添付したプログラムは,巡回セールスマン問題( TSP )を逐次改善法によって解くためのものです.コンパイルした後,

    実行可能ファイル名 ケーススタディファイル名

    と入力してやれば実行できます.ケーススタディファイルは,たとえば,同じ問題を乱数の初期値を変えて実行したいような場合や複数の問題を解く場合に効果的であり,以下のような形式で作成します.
    3 1 data/data10 12 data/data10 123 data/data10
      最初の行に問題の数を入力し,以下,その数だけ,乱数の初期値とデータファイル名をペアーで入力します.データファイルは,問題自身とその解法の詳細を記述するためのファイルであり,たとえば以下のように記述します.
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3 出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1 出力ファイル名 result\data10 表示間隔 0 -58 37 55 -19 6 -79 27 -30 44 -94 33 -58 -94 87 -9 3 33 69 43 -57
      日本語で記述した部分(「都市の数」,「最大試行回数」等)は,次に続くデータの説明ですのでどのように修正しても構いませんが,削除したり,または,複数の文(間に半角のスペースを入れる)にするようなことはしないでください.各データの意味は以下に示す通りです.

    都市の数

      都市の数を入力します

    最大試行回数

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

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

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

    近傍(2or3)

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

    出力レベル(負はファイル)

      結果の出力方法を入力します.
    =0 : 最終結果だけを出力します.
    =n : n 回毎に出力します.なお,n が負の場合は,-n 回毎に,ファイルに追加形式( append )で出力されます.n が正の場合は,出力するたびに,出力を行うか否か,および,どこに出力するかを聞いてきます.したがって,この段階において,出力先をファイルに変更することも可能です( n = 0 の場合も同様).

    出力方法(-1:なし,0:すべて,1:評価値)

      結果の出力方法を入力します.
    =-1 : 出力を全く行いません.
    =0 : 経路長と巡回する都市の順番を出力します.
    =1 : 得られた経路長だけを出力します.ただし,最終結果だけは,都市の順番も出力します.

    出力ファイル名

      結果を保存するファイル名です.なお,画面に出力する場合も,この項目を必ず入力してください(利用はされません).

    表示間隔

      計算がどこまで進んでいるのかを示すため,結果の概略を画面に表示しますが,それを何回毎に行うのかを入力します.

    -58 37
    55 -19
      ・・・・・

      以下,各都市の x 座標と y 座標です(整数値).都市の数だけ必要になります.この入力された順番が,その都市の都市番号になります( 0 から始まる).

      結果を画面に出力する場合,各ケースが終了毎に入力待ちの状態になります.また,都市の順番も出力する場合は,指定された数の都市を出力する毎に入力待ちの状態になります.return キーを入力すれば継続されます.

  2. Java によるプログラム

      添付したプログラムは,C/C++ のプログラム例を Java を使用して書いたものです.入力データ,結果は C/C++ のプログラム例とほとんど同じですが,このプログラムでは,計算結果を画面に図示することが可能になっています.そのため,データファイルが,たとえば,以下のように変わります.
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3 出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1 出力ファイル名 result\data10 表示間隔 0 画面表示(0:しない,1:結果,2:初期状態と結果,3:ステップ) 1 都市番号 20 画面の大きさ(幅,高さ) 1000 750 -58 37 55 -19 6 -79 27 -30 44 -94 33 -58 -94 87 -9 3 33 69 43 -57
      最初の 3 行,および,都市の座標部分は C/C++ のプログラム例と同じです.4 行目,および,5 行目の意味は以下の通りです.なお,結果を図示しない場合においても,4,5 行目を削除しないでください.

    画面表示(0:しない,1:結果,2:初期状態と結果,3:ステップ)

    結果を図示するか否かを入力します.
    =0 : 図示しない
    =1 : 最終結果だけを図示
    =2 : 初期状態と最終結果を図示
    =3 : 初期状態,最終結果,および,改善の過程を表示.改善過程の表示は,マウスで図中の 「 next 」 ボタンをクリックすることによって実行されます.したがって,初期状態を図示した後,この状態に入ると,
        終了したらreturnキーを押してください
    というメッセージが出力され,次に進まなくなりますので,マウスクリックによって最適解を達成した後,return キーを入力して継続してください.なお,マウスクリックによる表示の際,交換される前の枝が赤色で表示されますが,赤色の枝がなくなった時点が最適解となります.

    都市番号

      都市番号を表示する際,その字の大きさを入力します.0 を入力すると都市番号を表示しません.

    画面の大きさ(幅,高さ)
      画面の幅と高さの最大値を入力します.実際に表示される画面の大きさは,これらの値と都市座標の分布状況によって,上下,左右の縮尺が等しくなるように決められます.

      なお,図示する場合,対応する図が表示される毎に(マウスクリックによる場合を除く),MS-DOSの画面に

      図を確認したらreturnキーを押してください

    のようなメッセージが出力されますので,メッセージに従い return を押して継続してください.