4

私は、ユーザーが望むものの間の最短ルートを見つけるマッピング アプリケーションに取り組んでいます。ユーザーが必要とするもの (パンやガスなど) には、複数の可能な場所があります。ただし、現時点では、ユーザーと、ユーザーに最も近い各アイテムのインスタンスとの間のルートを計画しているだけです。これは常に最適なルートではありません。以下の図に示すように、最速のルートには、遠く離れたノードのクラスターを訪問することが含まれる場合があります。 ここに画像の説明を入力 アイテムごとに、最大 50 の可能なノード (場所) があります。すべてのノードを (任意の順序で) 訪問する最短ルートを計画するにはどうすればよいですか? これを解決する方法の具体的な例へのポインタは素晴らしいですが、私が本当に探しているのは、この問題の解決を開始するための正しい方向へのポイントです。

4

3 に答える 3

1

この問題の解決策は、新しいグラフG'を導入することで見つけることができます。

  • G'のノードは、元のグラフを通る単純なパスです
  • 2 つのノードが部分パスpおよびp'に対応する場合、2 つのノード間にエッジが存在します。st pは、それにノードを追加することによってp'に拡張できます。

このグラフ (非常に大きいため、メモリ内で明示的に表さないでください) では、A* 検索などを使用して目的のツアーを見つけることができます。

于 2013-04-20T18:44:36.413 に答える