Traveling Salesman
すべての都市を一度ずつ巡る最短ルートを見つけよう · 古典的な巡回セールスマン問題
巡回セールスマンについて
巡回セールスマンは、コンピューターサイエンスで最も有名な問題の1つである巡回セールスマン問題（TSP）を基にした、一口サイズの経路最適化パズルです。いくつかの都市が地図上に散らばっており、あなたは自宅からスタートします。あなたの仕事は、すべての都市を正確に1度ずつ訪れ、自宅に戻るツアーを、可能な限り最短の総距離で計画することです。都市を訪れる順序でタップするとルートが描画され、ライブ距離カウンターがループの長さを表示します。
なぜ脳を鍛えるのか。最短ツアーを見つけることは、純粋な空間推論と計画です。あなたは、全体の順序を比較検討し、ルートが交差して距離を無駄にしていることに気づき、打ち破ることのできない配置を探す必要があります。適用する公式はありません。幾何学について直接推論します。これは、TSPが有名にした最適化思考そのものです。
最適解と一致させて勝利。すべてのマップは舞台裏で正確に解かれているため、あなたのループが真の最短ルートと一致した場合にのみ、ラウンドは勝利とみなされます。同じくらい短いツアーはすべて勝利とみなされます。より長いルートになった場合、ゲームはあなたのルートの上に最適なルートを表示し、あなたが解きほぐすべきだった交差点を見ることができます。
レベルアップするにつれてマップが成長。初期のラウンドは4つまたは5つの都市で、目視で確認できるほど短いです。数レベルごとにマップに都市が追加され、追加の停留所ごとに可能なルートの数が倍増するため、連勝が続くほど最短ループを見つけるのが難しくなります。
PlayMemorizeファミリーの脳トレゲームの一部です。完全にブラウザで動作し、プログレッシブウェブアプリとしてオフラインでも動作します。
FAQ
-
巡回セールスマンの遊び方は？
ホームマーカーからスタートします。他の都市を訪れる順序で1つずつタップします。ルートは進むにつれて描画され、距離カウンターが更新されます。すべての都市がルート上にあることを確認したら、「チェック」を押します。あなたのループが可能な最短ルートと一致すれば、ラウンドに勝利します。 -
巡回セールスマン問題とは？
これは古典的な最適化問題です。与えられた都市の集合に対して、各都市を正確に1度ずつ訪れ、出発点に戻る最短ルートを見つけるというものです。都市を追加するにつれて可能なルートの数が爆発的に増えるため、非常に難しいことで有名です。このゲームでは、手作業で解決可能な小さなインスタンスに取り組むことができます。 -
ゲームはルートが最適であることをどうやって知るのですか？
各マップは十分に小さいため、ゲームは可能なすべての順序をチェックすることで正確な最短ツアーを計算します。あなたのループの長さがその最適解と一致した場合に勝利となります。2つの異なるルートが最短で同点の場合、どちらか一方が勝利とみなされます。 -
私のルートが最短でない場合はどうなりますか？
そのラウンドは敗北とみなされ、ゲームはあなたのルートの上に真の最適ルートを描画し、比較できるようにします。あなたのループが交差している場所を探してください。交差を解消すると、ほとんどの場合ツアーが短縮されます。「元に戻す」で最後の都市を削除するか、「クリア」でルートを最初からやり直してください。 -
進むにつれて難しくなりますか？
はい。成功するたびにレベルが上がり、数レベルごとにマップに都市が追加されます。追加の停留所ごとに可能なルートの数が急激に増加するため、連勝が続くほど最短ループを見つけるのが着実に難しくなります。 -
オフラインでも動作しますか？
はい。PlayMemorizeはプログレッシブウェブアプリです。一度インストールすれば、インターネット接続なしでどこでも巡回セールスマンをプレイできます。