以下をクリックすると、巡回セールスマン問題のアプレットを見ることができます。
巡回セールスマン問題のアプレット

いくつかの方法により、巡回セールスマン問題の入力をグラフとして生成することができます。
生成したグラフに対して、局所探索と呼ばれるアルゴリズムを使って、近似解を求めることができます。
速度を設定することで、アルゴリズムが近似解を求めていく様子をアニメーションで見られます。
自分で問題を解いてみることもできますので、プログラムが選んだ近似解よりも良い解が見つかるかどうか、試してみてください。

使い方

グラフの生成

グラフの生成方法を48 US cities、532 US cities、Randomから選んでください。それぞれ米国48都市、米国532都市、ランダムなグラフです。ランダムなグラフを選ぶときは、頂点数を入力してください。「グラフの生成」ボタンをクリックすると、グラフが生成されます。赤い四角がスタート地点です。米国48都市と米国532都市のデータは、TSPLIB95のatt48とatt532を利用させていただいています。

頂点の表示・非表示

頂点を表示するかしないかを選ぶことができます。

頂点のサイズ

頂点を表す四角の大きさを調整できます。

解く

「解く」ボタンをクリックすると、問題を自分で解くことができます。赤い四角をスタート地点として、次に訪問する青い四角を次々にクリックしていってください。全ての青い四角をクリックしてから赤い四角をクリックすると、解を求めたことになります。画面の右側の「選んだ解のコスト」に、求めた解のコスト（距離）が表示されます。

近似解

局所探索と呼ばれる近似アルゴリズムを使って、近似解を求めます。近似解が計算される様子を見ることができます。画面の右側の「近似解のコスト」に、得られた近似解のコスト（距離）が表示されます。

繰り返し回数

局所探索の繰り返し回数を指定します。数値を大きくするとより精度が高い解がえられますが、その分、計算時間がかかります。

速さ

数値を大きくするとアニメーションの表示速度が遅くなります。

クリア

グラフを消去します。