巡回セールスマン可視化
3〜10 個の平面点について、最近傍巡回路と厳密な最短閉路をブラウザー内で比較します。
使い方
使い方
- 1 行に name, x, y 形式で都市を入力します。
- 最近傍巡回路と厳密閉路を計算します。
- 順序、距離、描画された経路を比較します。
What is compared
最近傍法は最も近い未訪問点を順に選びます。厳密解は制限付き動的計画法で、最初の都市に戻る最短閉路を返します。
Small planar problems only
Enter 3 to 10 unique city names with finite x/y coordinates from −1,000,000,000 to 1,000,000,000. Distances are straight-line coordinate units, not roads, fares, or travel times.
よくある質問
あわせて知りたいこと
最近傍法は常に最適ですか？
いいえ。高速なヒューリスティックです。入力点に対する最短閉路は厳密解で確認できます。
距離は何を表しますか？
座標上の直線ユークリッド距離であり、道路、運賃、移動時間ではありません。
都市数が10件までなのはなぜですか？
厳密な巡回セールスマン計算は急速に増大するため、ローカル計算と描画を応答性の高い範囲に保ちます。