近似パス解を設計するにはどうすればよいですか？

Question

ノードが接続されているという保証がないと考えて、宛先ノードに最も近いパスを見つけることができるグラフ検索アルゴリズムを作成しようとしています（または展開しています）。

オンタリオ州のブランプトンからオンタリオ州のハミルトンに着く必要があるとしましょう。私は出発地点で私の可能な選択肢がローカルトランジット、GOバス、またはウォーキングであることを知っています。私は歩くことが私の目的地に行くための最も望ましい方法であることを知っているので、私は最初にGOバスを見る。私はハミルトンに近いところにGOすることができると知っていますが、その時点でGOバスが回って、その最も近いポイントで別の方向に向かいます。私は歩いている以外のオプションはありませんが、短距離の場合は実行可能でないとみなします）

この同じ例を使用すると、アルゴリズムで目的地ノードに近づけることができます宛先ノード）の重み付けは重要ではありません（重み付けは、検索の間はあまり重要ではなく、結果が配信される場合にのみ、どのパスが目的地に最も近いかによって昇順で表示されます）。例えば、1台のGOバスは3台の公共交通バスが500メートル離れ

私を得るだろうが私の質問は2倍で、宛先ノードから私に3キロを得ることができます： 1）どのようなアルゴリズム私はそれで開始する必要があります 似た何かをします2）ノードからノードRへノードAからノードRへジャンプしないようにノードが接続していないと、プログラムで説明するとどうでしょうか。特に大規模なグラフでは、この問題に対する何百万もの解決策が存在するため、最適な近似解を目指す方法を尋ねるのを忘れていました。

おかげで、A* algorithm上に読む マイケル

Answer 1

なぜ、すべてのノードが接続されていると思わないのですか？現実の世界では、通常通りに歩いたり、タクシーなどにいつでも電話することができます。

この場合、単純にモデルを次のように変更することができます。輸送方法ごとに1つのグラフがあります。同じ場所にあるノードは、ウェイト0のエッジで接続されます（つまり、空港または鉄道駅で車で降車した場合）。

次に、各頂点とエッジを輸送タイプでラベル付けします。既存のルーティングアルゴリズムをそのまま使用することができます。ああ、ところで、A *は本当に大きなネットワークにはうまく適用されません。 Yahoo/Google/Microsoft Mapsなどのソフトウェアが実際に使用するものを入手するには、hereをご覧ください。この研究グループの研究には、DIMACS shortest path challengeの受賞者が含まれています。

Answer 2

。これは、ダイクストラの最短経路アルゴリズムの一般化であり、ヒューリスティックを指定することで、2つの頂点間の距離の下限を指定できます。あなたの場合、ヒューリスティック関数は単にユークリッド距離を返します。

アルゴリズムを実行し、最良の特性値を持つ頂点を追跡します。これは、ソースとユークリッド距離からグラフまでの距離から何とか計算します。唯一の難しい部分は、いつ終了するかを決定することです（グラフ全体をトラバースしない限り）。

Answer 3

ノードの特性が追加されていると非常によく似ています（travelling salesman）。このタイプの問題がNP Completeであることにはちょっと注意してください。あなたの最善の策は、ある種の近似アルゴリズムを使うことでしょう。