何百万ものノードを持つ大きなグラフがあります。ノード「A」がノード「B」から4ホップ未満で到達可能かどうかを確認したいと思います。可能であれば、最短経路が必要です。この問題を解決するための最良の方法（またはアルゴリズム）はどれですか？
2778 次
3 に答える
7
グラフが重み付けされていない場合（質問のように）、ソースからターゲットまでの最短パスを見つけるには、単純で効率的なBFSで十分であることに注意してください。
また、単一のソースと単一のターゲットがあるため、双方向BFSを適用できます。これは、BFSよりも効率的です。
アルゴリズムのアイデア：ソースとターゲットから同時にBFS検索を実行します：[両方で深さ1まで、両方で深さ2までBFS、....]。
両方のBFSの前面にある頂点vが見つかると、アルゴリズムは終了します。
アルゴリズムの動作：アルゴリズムの実行を終了する頂点vは、ソースとターゲットのちょうど中間にあります。
このアルゴリズムは、ほとんどの場合、ソースからのBFSよりもはるかに優れた結果をもたらし[BFSが続くよりも優れている理由の説明]、存在する場合は確実に答えを提供します。
ソースからのBFSよりも優れているのはなぜですか？
ソースからターゲットまでの距離がkであり、分岐係数がB[すべての頂点にBエッジがある]と仮定します。
BFSが開きます：1 + B + B^2 + ... + B^k頂点。
双方向BFSが開きます：2 + 2B^2 + 2B^3 + .. + 2B^(k/2)頂点。
大きなBとkの場合、2番目の方が明らかに最初の方がはるかに優れています。
（*）双方向検索の説明は、私が投稿した別の回答から引用しています
于 2012-11-01T14:12:15.073 に答える
3
1つのノードがターゲットに近い可能性についての追加情報がないグラフで2つのノード間の最短経路を見つけるための最良のアルゴリズムは、ダイクストラのアルゴリズムです。このアルゴリズムを簡単に変更して、3ホップ後に終了し、関心のない結果の計算を無駄にしないようにすることができます。
特定のノードがターゲットに近い可能性に関する追加情報がある場合は、A *検索を使用できます。これは、ノードからターゲットまでの距離のヒューリスティックを使用して、ランタイムパフォーマンスを向上させます。
于 2012-10-31T06:19:08.707 に答える
1
If you need path less than 3 hops, then all possible paths are A (A=B), A-B (nodes are adjacent), A-X-B (X is a node adjacent to both ends). So there's no need in any complex algorithm. First, test for A=B, second, test that A and B are adjacent, and third, try to find X that is adjacent to both A and B (eg. intesection of endpoint adjacency sets).
于 2012-11-01T13:24:52.210 に答える