私はグラフ検索アルゴリズムを研究しています (この質問のために、アルゴリズムを DFS、BreadthFS、ID のみに制限します)。
これらのアルゴリズムはすべて、前方検索 (開始ノードから終了ノードまで) または後方検索 (終了ノードから開始ノードまで) として実装できます。
私の質問は、後方検索が前方検索よりも優れたパフォーマンスを発揮するのはいつですか? そのための一般的なルールはありますか？
3310 次
1 に答える
2
幅優先検索または反復深化では、質問に対する数学的な答えには、頂点の周りの「ボール」の概念が含まれると思います。Ball(v, n) をノード v から最大で n の距離にあるノードの集合と定義し、開始ノード s から宛先ノード t までの距離を d とします。次に、最悪の場合、|Ball(s, d)| の場合、前方検索が後方検索よりも優れたパフォーマンスを発揮します。< |ボール(t, d)|. これは、幅優先検索 (最悪の場合は ID) が、深さ k + 1 のノードにアクセスする前に、開始ノードから距離 k のすべてのノードを常に展開するためです。ターゲットよりも開始が前方検索は高速である必要がありますが、ターゲットの周囲にノードの数が少ない場合は、開始および後方検索が高速である必要があります。残念ながら、この数をアプリオリに知ることは困難です。どちらが該当するかを判断するには、通常、検索を実行する必要があります。あなたは潜在的に使用することができますこの値のヒューリスティックとして 2 つのノードの周りの分岐係数ですが、必ずしも 1 つの検索が高速になるとは限りません。
調査を検討したい興味深いアルゴリズムの 1 つは、双方向の幅優先検索です。これは、ソース ノードとターゲット ノードから同時に検索を行います。これは、標準の幅優先検索よりもはるかに高速になる傾向があります (特に、分岐係数が b でノード間の距離が d の場合、双方向 BFS は O(b d/2 )かかりますが、BFS はおよそ O(b d ) 時間かかります)。 . 優れた BFS 実装があれば、コードを作成するのもそれほど難しくありません。
深さ優先検索に関しては、最悪の場合、両方の検索がパスを見つける前にグラフ全体を探索する可能性があるため、どちらが高速かを判断する良い方法を実際には知りません。どちらが優れているかを判断する方法について誰かが適切な説明を持っている場合は、投稿していただければ幸いです。
于 2011-02-08T19:52:56.463 に答える