3

私が取得したいのは、グラフ内のすべてのポイントを接続するパスですが、アルゴリズムにどこから開始し、どこで終了するかを伝える必要はありません。

google-maps api で運転方向を使用する必要がありますが、開始点または終了点を設定する必要はありません。

私には「開始都市」がなく、「開始都市」に戻る必要もないため、TSPの問題ではありません。

この質問で表現されているように: Find the shortest path in a graph that visits certain nodes、いくつかのノードがあるため、順列を使用できますが、問題は、このいくつかのノードのいくつかのグループを分析する必要があることです。できるだけ時間のかからないように機能します。

注：これも最小スパニングツリーを探していません：https://math.stackexchange.com/questions/130863/connecting-all-points-on-a-plane-with-shortest-path-possible 私が欲しい最初にここに行き、次にあちらに行き、次にあそこに行き、最後にそこに行くと、ガスを節約できるという道です。

質問:それを助けることができるライブラリはありますか? それとも、すでに正確な答えがある既知の問題ですか? どうすれば解決できますか？

4

4 に答える 4

2

すべてのペアの最短経路アルゴリズムが必要なようです。これは、グラフ内の頂点のすべてのペア間の最短パス (または最短パスの長さ) を計算しようとする最短パス アルゴリズムのクラスです。

これらはよく知られた問題であり、解決策は存在します。これは、他の可能なアルゴリズムを説明する読み物です。選択した言語と開発環境用のジョンソンのアルゴリズムの実装があるかもしれません。

計算的に言えば、これは高価な問題であることを覚えておいてください。

于 2012-11-01T03:00:55.607 に答える
0

私があなたを正しく理解しているなら、あなたは事前定義された開始/終了なしで、1つのルートがすべてのノードを訪問することを望みます、そしてあなたはそれを最小限にしたいです。考えられる解決策は、グラフを少し変更して、巡回セールスマンアルゴリズムが完全なツアーを取得できるようにすることです。

グラフから始めて、ノードを1つ追加しますE。そのノードをグラフ内の他のすべてのノードに接続し、それらすべてのエッジのコストを非常に高い定数に設定しますM。次に、そのグラフで巡回セールスマンアルゴリズムを解き放ちます。これにより、Pから始まりE、すべてのノードを通過して、に戻るパスが得られますE。Pパスの残りの部分に接続されているエッジの2つのエッジを削除すると、E探していたものが得られます。

それが本当にあなたが探していたものであるという簡単で直感的な証拠：それがすべてのノードを接続する最も安価な方法ではないとします。おそらくより良いパスと呼びましょうQ。Q両方ともP、元のグラフのすべてのノードを接続します。のエンドポイントはとになりQます。これらは両方とも、コストのエッジでノードに接続されます。これらの2つのエッジをに追加すると、よりも優れたTSPソリューションが得られますが、これは最善であったため不可能です。ABEMQPP

于 2012-11-02T12:47:39.077 に答える
0

Google マップを使用しているため、TSP の特定のインスタンスが三角形の不等式を満たす場合があります。あなたは本当に距離や移動時間について話しているのですか?

距離の場合: グーグルを試してください: 「三角巡回セールスマン問題」

重要: 結果は、上限が保証された最良の結果の非常に優れた近似値であり、常に最良であるとは限りません。

于 2014-08-05T14:51:09.360 に答える
0

1 つの方法は、(自己組織化された) kohonen ネットワークを使用することです。
マップ上にn 個の都市があるとします (どの次元でも同じように機能します)。n 個
の接続された「ニューロン」 のチェーンを取り、マップ上にランダムに配置します。次に、いくつかの反復を行います。1 つの反復には以下が含まれます。

  1. 任意の都市を選択します。(例えば、順序立てて通過する)
  2. 「最も近い」ニューロンを決定し、それをxと呼びます。(例: ユークリッド距離)
  3. このxを都市に近づけます (たとえば、ニューロンから都市への方向ベクトルを取り、それに学習率 0 を掛けます)
  4. このニューロンの隣人もこの都市に向かって移動します (ただし、3. よりも小さく、隣人から「現在最も近い」ニューロンxまでの距離に依存します)

ステップ 2、3、4 でさまざまな機能を選択できます。

また、開始チェーンの場所やその他のさまざまな要因に依存するため、これはグローバルな最短パスを提供しない場合があることに注意してください。このため、異なる開始条件で複数の実行を行うことを検討するか、(問題に応じて) 事前知識を少し役立てることができます。

これが、他の読者のためにこの質問を完了するのに役立つことを願っています...

于 2016-11-23T17:04:06.623 に答える