最小化广度优先搜索的内存使用

Question

在我的下面的代码中,我正在遍历一个图表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;
    }
}

Answer 1

在恒定扇出和假设树状图的情况下，BFS 访问过的节点数量几乎与边缘节点的数量相同。（例如，扇出为K的树中，每层n有K^n个节点，深度比n低的节点数也是Theta(K^n)）。

因此，存储条纹已经占用了大量的内存。因此，如果内存是一个非常大的问题，那么“等效”技术（例如迭代加深 DFS）可能会更好。

但是，如果您想销毁“已访问”节点，则需要设计某种方法来跟踪已访问的内容（在一般图的情况下；如果它是树，则没有问题）。在这种情况下，需要有关图表的更多信息。

编辑为什么迭代加深 DFS 更好。

BFS 中的边缘（与已访问节点相邻的未访问节点）的大小为 O(K^n)，n 是当前深度。DFS 的边缘大小为 O(n)。

迭代加深 DFS 具有与 DFS 相同的条纹大小，并给出与 BFS 相同的结果，因为它“模拟”BFS。