Chiaki Hirota

卒業研究で学生の佐藤未央さんと巡回セールスマン問題をアニーリング法で解くプログラムを作成しました．巡回セールスマン問題とは，いくつかの町があったとき，それらの町を1度だけ周り，最後に元にいた町に戻ってくる最短経路を求めるという問題です．経路の数はじゅず順列になり，n個の町があれば (n-1)!/2通りの経路があります．この問題を少い計算時間で解くことができる手法としてアニーリング法があります．アニーリング法は最適に近い解を短い計算時間(低い次数の多項式オーダ)で求めることができるアルゴリズムです．このアルゴリズムを用いて最適(?)経路を求めるJavaアプレットを作成しました． ただ解くだけではつまらないのでプレーヤーが経路を選択し，アニーリング法によって計算された経路とどちらが良いか比較するプログラムにしました．アニーリング法による解は最適である保証はないので，右図のように人間の選択した経路の方が優れている場合があります．是非コンピュータにチャレンジしてみてください!

ゲームのやり方は以下の通りです．

1. 町の数を入力する(デフォルトは10)．4以上300以下の値を設定してください．
2. 町の配置ボタンを押す．画面中央の四角の中に丸印が指定した個数表示される．
3. 丸印をクリックし経路を選択する．どこからはじめても構いません．2つ目の選択からは選択した経路が緑色の線で結ばれます．入力を間違えた場合は，一つ戻りたい場合は「直前の選択を解除」ボタンを，最初からやり直したい場合は「選択経路のリセット」ボタンを押してください．
4. 経路の選択が終ったら「アニーリング実行」ボタンを押しましょう．結果が地図上に赤線で表示されます．また詳細が下部のテキストエリアに表示されます．

ゲームを始める方はここをクリック!