最小化广度优先搜索的内存使用
在下面的代码中，我通过广度优先搜索遍历一个图。代码在遍历时构造图。这是一个非常大的图，扇形为 12。因此，只要广度优先搜索的深度增加，我就想破坏它上面的层以尝试最小化内存用法。我如何设计一个算法来做到这一点？
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;
}
}
In my the following code, I am traversing a graph through breadth first search. The code constructs the graph while it is traversing. This is a very large graph, with a fan out of 12. Due to this, any time the depth of the breadth first search increases, I want to destruct the layer above it in an attempt to minimize memory usage. How could I design an algorithm to do so?
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;
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在恒定扇出和假设树状图的情况下，BFS 访问过的节点数量几乎与边缘节点的数量相同。 （例如，扇出为K的树中，每层n有K^n个节点，深度比n低的节点数也是Theta(K^n)）。
因此，存储条纹已经占用了大量的内存。因此，如果内存是一个非常大的问题，那么“等效”技术（例如迭代加深 DFS）可能会更好。
但是，如果您想销毁“已访问”节点，则需要某种方法来跟踪已访问的内容（在一般图的情况下；如果它是树，那么就没有问题）设计的。在这种情况下，需要有关图表的更多信息。
编辑为什么迭代加深 DFS 更好。
BFS 中的边缘（与已访问节点相邻的未访问节点）的大小为 O(K^n)，n 是当前深度。 DFS 的边缘大小为 O(n)。
迭代加深 DFS 具有与 DFS 相同的条纹大小，并给出与 BFS 相同的结果，因为它“模拟”BFS。
With constant fanout and assuming a tree-like graph, the number of nodes that have been visited by a BFS is almost the same as the number of nodes on the fringe. (e.g. in a tree with fanout K, each level n has K^n nodes, and the number of nodes with lower depth than n is also Theta(K^n)).
Hence, storing the fringe will already take up alot of memory. So if memory is a very big problem, an "equivalent" technique such as iterative deepening DFS may be much better.
But if you want to destroy the "visited" nodes, then some way of tracking what has been visited (in the case of a general graph; if it is a tree then there's no problem) needs to be devised. In which case more information on the graph is needed.
EDIT on why iterative deepening DFS is better.
The fringe (unvisited nodes that are to be adjacent to the visited nodes) in a BFS is O(K^n) in size, n being the current depth. The fringe for DFS is O(n) in size.
Iterative deepening DFS has the same fringe size as DFS, and gives the same result as BFS, because it "simulates" BFS.
广度优先搜索本质上具有指数空间复杂度。任何技巧都只会对大图的内存需求产生边际影响。如果您想要易于处理的空间复杂性，那么最好使用深度优先搜索。
Breadth-first search inherently has exponential space complexity. Any tricks will make only marginal impacts in the memory requirements for large graphs. You're better off using depth-first search if you want tractable space complexity.