0

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

これを現実的に適用するために、オンタリオ州ブランプトンからオンタリオ州ハミルトンに行く必要があるとしましょう。出発点で可能な選択肢は、ローカルトランジット、GOバス、またはウォーキングです。目的地に行くには徒歩が一番嫌いな方法だと知っているので、まずGOバスを見てみます。ハミルトンに近い地点までGOを利用できることはわかっていますが、その時点でGOバスが曲がり、その最も近い地点で別の方向に進むのは、選択肢がない場所です（歩く以外、アルゴリズムは歩くことだけを考慮します）短距離の場合、それ以外の場合はルートが実行不可能と見なされます）

この同じ例を使用して、アルゴリズムが、より長い方法でそこに到達できるが、より高い重み付けされたパスである宛先ノード（または宛先ノードで可能）に近づくことができることを検出した場合（重み付けは行われません）検索中は非常に重要ですが、結果が配信された場合にのみ、宛先に最も近いパスが昇順で一覧表示されます）。たとえば、1つのGOバスで目的地のノードから3 kmの距離になり、3つの公共交通機関のバスで500mの距離になります。

したがって、私の質問は2つあります。1）どのアルゴリズムから始めれば、同様のことができます。2）ノードが接続されていなくても、ノードAからノードRにジャンプしないように、プログラムで説明するにはどうすればよいでしょうか。最後から始めて、逆方向に作業することでこれを達成できますか

編集：特に大きなグラフでは、この問題の解決策が何百万もある可能性があるため、最良の近似解を目指す方法を尋ねるのを忘れました。

ありがとう、マイケル

4

3 に答える 3

4

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

アルゴリズムを実行し、最高の特性値を持つ頂点を追跡します。これは、ソースからのグラフ距離とターゲットまでのユークリッド距離から何らかの方法で計算されます。唯一注意が必要なのは、いつ終了するかを決定することです（グラフ全体をトラバースしたい場合を除く）。

于 2009-04-12T17:00:49.100 に答える
2

すべてのノードが接続されていると想定できないのはなぜですか？現実の世界では、彼らは通常そうです、すなわちあなたはいつでも歩いたりタクシーを呼んだりすることができますか？

この場合、次の方法でモデルを簡単に変更できます。輸送方法ごとに1つのグラフがあります。同じ場所にあるノードは、重み0のエッジに接続されています（つまり、空港や駅で車で降ろされた場合）。

次に、各頂点とエッジにトランスポートタイプのラベルを付けると、既存のルーティングアルゴリズムを簡単に使用できます。ちなみに、A*は本当に大きなネットワークにはうまく拡張できません。Yahoo / Google / Microsoft Mapsのようなソフトウェアが実際に使用するものを入手するには、こちらをご覧ください。この研究グループの作業には、DIMACS最短経路チャレンジの勝者が含まれます。

于 2009-04-12T17:49:15.740 に答える
-1

追加のノード特性を持つ巡回セールスマン問題のように聞こえます。このタイプの問題はNP完全であることに注意してください。最善の策は、ある種の近似アルゴリズムを使用することです。

于 2009-04-12T17:01:58.443 に答える