5

次のコードでは、 を介してグラフをトラバースしていますbreadth first search。コードは、トラバース中にグラフを構築します。これは非常に大きなグラフで、ファン アウトは 12 です。このため、深さがbreadth first search増すたびに、メモリ使用量を最小限に抑えるために、その上のレイヤーを破棄したいと考えています。そのためのアルゴリズムをどのように設計できますか?

string Node::bfs(Node * rootNode) {
QQueue<Cube *> q;
q.enqueue(rootNode);

while (!(q.empty())) {
    Node * currNode = q.dequeue();
    currNode->constructChildren();
    foreach (Node * child, currNode->getListOfChildren()) {
        q.enqueue(child);
    }
    if (currNode->isGoalNode()) {
        return currNode->path;
    }
}
4

2 に答える 2

3

ファンアウトが一定で、ツリー状のグラフを想定すると、BFS がアクセスしたノードの数は、フリンジのノードの数とほぼ同じになります。(たとえば、ファンアウト K のツリーでは、各レベル n には K^n 個のノードがあり、n より小さい深さのノードの数も Theta(K^n) です)。

したがって、フリンジを保存すると、すでに大量のメモリが占​​有されます。したがって、メモリが非常に大きな問題である場合は、DFS の反復的な深化などの「同等の」手法の方がはるかに優れている可能性があります。

しかし、「訪問した」ノードを破棄したい場合は、訪問したものを追跡する何らかの方法 (一般的なグラフの場合。ツリーの場合は問題ありません) を考案する必要があります。その場合、グラフに関する詳細情報が必要です。

反復深化 DFS が優れている理由について編集します。

BFS のフリンジ (訪問済みノードに隣接する未訪問ノード) のサイズは O(K^n) で、n は現在の深さです。DFS のフリンジのサイズは O(n) です。

反復深化 DFS は、DFS と同じフリンジ サイズを持ち、BFS を「シミュレート」するため、BFS と同じ結果をもたらします。

于 2010-12-02T04:51:29.337 に答える
1

幅優先探索には、本質的に指数関数的な空間の複雑さがあります。どんなトリックも、大規模なグラフのメモリ要件にわずかな影響しか与えません。扱いやすいスペースの複雑さが必要な場合は、深さ優先検索を使用することをお勧めします。

于 2010-12-02T04:51:17.237 に答える