11

問題: ポイントのコレクションが大量にあります。これらの各ポイントには、他のポイントへの参照を含むリストがあり、それらの間の距離はすでに計算および保存されています。出発地から始まり、特定の数のポイントを通過して任意の目的地に到達する最短ルートを決定する必要があります。

例: 私は休暇中で、特定の都市に滞在しています。私は 4 つの都市のいずれかを見るために片道旅行をしていますが、可能な限り最短距離で移動したいと考えています。同じ都市を複数回訪問することはできません。

現在の解決策: 現在、すべての可能性を手動で反復処理し、最短パスを保存しています。これは機能しますが、非効率的です。また、この問題は最終的に複数の出発地から複数の目的地への検索を含むように拡張されるため、検索スペースが爆発する可能性があると思います.

最短ルートを検索するより良い方法は何ですか?

4

7 に答える 7

7

更新された投稿に答えると、すべての可能性をチェックするソリューションが最適です (少なくとも、これまでより優れたアルゴリズムを発見した人はいません)。はい、それは巡回セールスマンです。その本質は、すべての都市に触れるのではなく、すべての都市に一度触れることです。可能な限り最適なソリューションを検索したくない場合は、より高速に機能するヒューリスティックを使用すると便利ですが、理想的なソリューションとの相違を制限することができます。

将来の回答者のために: Floyd-Warshall アルゴリズムとすべての Floyd のようなバリエーションは、ここでは適用できません。

于 2009-10-02T20:34:08.617 に答える
3

一般に、悪いバリアントを厳密にする必要があります... Branch_and_bound メソッドのいくつかのバリエーションを使用する必要があると思います http://en.wikipedia.org/wiki/Branch_and_bound

于 2009-10-02T20:28:40.237 に答える
2

Norheim.seが言ったように最初に検索するか、Dijkstraのアルゴリズムも私の提案です。

于 2009-10-02T20:28:51.887 に答える
1

これは非常に一般的でリアルタイムの状況であり、誰もが陥る可能性があります。Google マップのユーザー インターフェイスでは、目的地リストに追加するのと同じ順序でパスが表示されます。独自の Google マップ API がソリューションを提供しますが、最適なパスは提供されません。

Google Maps API は、これに対するソリューションを提供します。パスを見つけるためのリクエストでは、フラグ「optimizeWaypoints: true」を指定する必要があります。リクエストはこのようになります。

var request = {
            origin: start,
            destination: end,
            waypoints: waypts,
            optimizeWaypoints: true,
            travelMode: google.maps.TravelMode.DRIVING
        };

完全なユーティリティは JavaScript と HTML で開発されているため、ビュー ソースでユーティリティのコード全体を確認できます。

それが役立つことを願っています。

于 2014-01-10T06:27:06.960 に答える
1

これは巡回セールスマン風に聞こえますか？1 つの解決策は、進化的アルゴリズムなどの最適化手法を使用することです。現在、徹底的な検索を行っていますが、これはすぐに非常に遅くなります。しかし、これはほとんど巡回セールスマンの問題であり、数世紀とは言わないまでも数十年にわたって取り組まれてきたため、いくつかの攻撃方法が考えられます。グーグルはあなたの友達です。

于 2009-10-02T20:19:05.887 に答える
1

おそらくこれは、「各可能性を手動で繰り返し、最短経路を保存する」という元のポスターの意味ですが、ベースライン ソリューションと思われるものを明示したいと思いました。

すでに 2 点最短経路アルゴリズムがあると仮定します。これには、さまざまな種類のグラフに対する古典的なソリューションがあります。すべての距離が非負であり、d(A->B->C) = d(A->B) + d(B->C) であると仮定します。

要点は、パスが S で始まり、中間都市「abcd」の 1 つを通り、E で終わることです。

例：SabcdE、SacbdE など...

中間都市が 4 つしかないため、24 の順列すべてを列挙します。順列ごとに、最短の 2 点アルゴリズムを使用して、頭から尾までの経路とその合計距離を計算します。

次に、開始点と終了点が与えられると、abcd の 1 つに接続する 12 の可能性と、それぞれの内部の 2 つの可能性があります。これらの距離は既に計算されているので、S から頭まで、尾から E までの距離を追加します。最小値を選択します。したがって、内陸都市の固定セットの中間距離を事前に計算したら、始点と終点の任意のペアに対して 12 の 2 点最短経路問題を実行する必要があります。

これは、中間都市の数が増えると、明らかにスケーリングが不十分になります。グラフ構造に大きな制限を課さない限り、それがうまくいくかどうかは私には明らかではありません (これは物理的なユークリッド空間にありますか? 三角形の不等式ですか?)。

私の考えた例: 都市間のすべての中間距離が O(1) であるとします。グラフに制限がない場合、S から任意の中間都市までの距離は、1 を除いて 1000 になる可能性があります。テールについても同じです。したがって、最初に訪問する都市を強制的に任意にすることができます。次に、1 層下に移動し、最初の都市を「開始点」とします。同じ引数を適用します。グラフの距離を操作することで、次の都市のいずれかに最適なパスを作成できます。

したがって、追加の仮定がなければ、複雑さは避けられないようです。

于 2009-10-04T06:54:24.570 に答える
-2

グラフのエッジは双方向のようです。この場合、探しているアルゴリズムはダイクストラのアルゴリズムです。

于 2009-10-02T20:35:27.393 に答える