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 回答