TSP プログラムのデモ
Computer Today 誌では、「アルゴリズムの道具箱」という連載記事が
掲載されましたが、その中の1999年1月--12月（No.89 -- No. 94）の6回を
私が担当しました。これはその後、臨時別冊・数理科学「アルゴリズムの
道具箱」、戸川隼人・有澤誠（編）、サイエンス社、2000年1月、として出版
されています。この一番最後に、巡回セールスマン問題を解説しましたが、
その中で、2-OPTとOr-OPTに基づく簡単な局所探索アルゴリズムのプログラム
を与えました。（私のホームぺージからダウンロードできます。）
下のデモは、このアルゴリズムの動作の様子を視覚的に見るようにした
ものです。土村展之氏に作って貰いました。SPATH と同様
「アルゴリズム工学」 の活動の一環でもあります。
さて、このTSPアルゴリズムは、「道具箱」で説明したように、ランダムな初期解から
始め、2-OPTとOr-OPTの近傍を用いて、局所探索にしたがって巡回路を改良して
行き、局所最適解になったところで停止します。
試みる度に初期解が異なるので、結果も違ってきます。
もちろん、近似アルゴリズムですので、最適解に到達する
保証はありません。４つの問題例が準備されていますが、それぞれ２次元
平面上の問題ですので、デモによって巡回路が変化していく様子を見ることが
できます。また、これらの問題例については、最適値が分かっていて、
それらからの誤差（％）も表示されるようになっています。問題例の最後の
ものが、「道具箱」で用いた、att532、すなわち532都市の問題です。
この問題あたりになると、計算停止までに結構時間が掛かります。
気長に見て下さい。
デモの開始
茨木研究室ホームページへ
< Last update: May, 2000 >