|
|
巡回セールスマン問題 (traveling salesman problem) |
「あなたはセールスマンです。
現在、下の図の
印の位置にいます。
これから、
印の得意先を１軒づつすべて訪問して、
もとの位置に戻ってこなければなりません。
どのような順序で訪問すれば、歩く距離を最短にできるでしょうか。」
これが、コンピュータプログラムの 難問 として有名な
巡回セールスマン問題 です。
ゲームのつもりで、気軽に 最短巡回コース を考えてみて下さい。
まず、最初に訪問する得意先の印にマウスのカーソルを合わせます。
の色がブルーに変わります。
マウスのボタンをクリックすると巡回経路が描かれます。
順次をクリックし、すべての得意先を訪問し終わったら、
最後にをクリックすれば完了です。
誤ってクリックしてしまった場合は、をダブルクリックすると
巡回経路を消去できます。
次の得意先との距離 (len)、およびこれまでの巡回コースの合計距離 (Total) は、
ピクセル 単位で画面の右下に
表示されます。（下図の長方形は横480ピクセル、縦310ピクセルで描かれています）。
| ボタンの機能 | 説 明 | |
|---|---|---|
| 配 置 |
Example | 起動時に表示された例題が表示されます。 |
| Manual | 画面がクリアされます。
マウスでクリックすると、32軒の得意先を任意の位置に配置できます。 | |
| Random | このボタンをクリックする度に、得意先が自動的に配置されます。 | |
| 巡 回 経 路 |
APPROX. | 巡回セールスマン問題の近似解例を表示します。 手抜きプログラムですので、往々にして一目瞭然の「遠回り」経路を平然と描きます。 あしからず。 |
| CLEAR | 表示されている巡回経路が消去されます。 | |
以外の場所でマウスのボタンをダブルクリックすると、
最短巡回経路は表示されなくなります。
もう一度ダブルクリックをすると、最短巡回経路が再表示されます。
起動時に表示される例題の最短と思われる巡回経路の長さは 1742 ピクセルです。
経路図 をご覧ください。
これより短い経路を発見された方は、ぜひお知らせください。
update: 1999.06.22 ueyama@infonet.co.jp