A. TSP とは？
TSP （ Traveling Salesman Problem ）は，巡回セールスマン問題とも呼ばれます．いくつかの都市が与えられた時，適当な都市から出発し，すべての都市を 1 度だけ訪れ，出発した都市に戻る経路の中で最も短い経路を探す問題です．「すべての都市を 1 度だけ訪れ，出発した都市に戻る経路」ですので，例えば，6 都市の場合，下の図における左側の 2 つの経路はルールに従った経路となりますが（最も左の経路が，2 番目の経路より短い経路となる），右側の 2 つの経路はルール違反となります．
B. 遊び方
パズルの実行を開始すると，以下に示すような画面が表示されます．
「都市数」に対して 3 以上の数値を設定し，「ゲーム開始」ボタンをクリックすると，以下に示すような画面が表示されます（この図は，都市数が 10 の場合）．
この画面における円が都市に相当します．適当な都市をクリックすると画面の下部に「 Next？」というメッセージが表示されますので，その都市と結びたい都市をクリックしてください．メッセージが消え，2 つの都市が直線で結ばれます．メッセージが表示されなかったり，直線で結ばれなかった場合は，再度クリックしてください．上の図は，2 つの都市を結んだ後，次の都市を結ぶため最初の都市をクリックした状態を表しています．なお，都市を結ぶ順序と都市の訪問順序は関係ありませんので，どのような順番で都市間を結んでも構いません．また，同じ都市を続けてクリックすれば，「 Next？」メッセージが消え，何もクリックしない状態に戻ります．さらに，不適切な都市間を結ぼうとすると，画面の下部に「 ***ルール違反です」というメッセージが表示されます． 結んだ直線を消したい場合は，その直線の両端の都市を順にクリックしてください．線を結ぶ場合と同じように，最初の都市をクリックすると画面の下部に「 Next？」というメッセージが表示され，次の都市をクリックすると直線が消去されます．
全ての都市が正しく結ばれると，画面の下部に，その経路長が出力されます．その経路が最短である可能性がある場合は，経路長の後ろに「 : 最短経路」，または，「 : 最短経路 or その近似値」のいずれかのメッセージが出力されます．都市数が 10 以下である場合は，最小値を正確に計算できますので，最初のメッセージが出力されます．都市数が 10 より多い場合は，計算時間がかかりすぎるため，近似計算によって最小値の計算を行い，2 番目のメッセージが出力されます．この場合は，メッセージとして表示された数値が最小値とは限らず，実際の最小値はもっと小さな値である可能性があります．都市の数が多くなると，計算時間がかかる（私のパソコンで，20 都市の場合 1 分程度）と共に，表示された数値と実際の最小値との差が大きく異なる可能性が高くなります．
コメント