广度优先搜索实现

Question

广度优先搜索实现

3

我正在尝试用Javascript实现广度优先搜索（也包括其他算法，但目前仅限于BFS）。

最终，我想将所有搜索算法应用于网格上，以找到从起点到终点节点的路径（我知道BFS在这方面并不特别好）。我已经实现了一个版本，但问题是我没有整个树结构。我想要的是给它一个起始节点和结束节点，并基于此找到它们之间的路径。

我遇到的问题是当我确定相邻的网格方块时，它会返回所有邻居，甚至是已经遍历过的。这使得它成为图形搜索而不是树形搜索。解决方法是记住所有路径，以便我可以检查哪些邻居已经被遍历过，因此不需要进一步检查。然而，正如我在搜索算法课程中学到的，BFS在当前深度级别上使用所有节点的内存。如果我存储所有路径，那么它消耗的内存比这还要多，对吗？

如果我没有预先构建树结构，是否有可能只在内存中保留BFS正在搜索的当前深度的节点，并仍然避免循环呢？

希望我表述清楚了。

提前感谢， Stefan

- Maricruzz

你是在搜索一棵树还是一张图？听起来你确实有一张图，但想使用基于树的搜索算法 - 这是行不通的。 - BrokenGlass

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

如果您“忘记”所访问的节点，您可能会遇到DFS遇到的相同问题 - 它不是最优的（可能找不到最优路径），也不完整（由于无限循环，即使存在解决方案，它也可能找不到解决方案）。

请注意：

即使只记住最深层次的节点，仍然没有帮助 - 请记住，在二叉树中，例如，一半的节点是叶子节点，因此空间复杂度仍然很高。
仅记住部分节点并不能保证最优性，因为最终你将重新发现所忘记的顶点 - 到那时，你已经陷入了一个循环。

如果您正在寻找更多内存有效的算法，既完整又最优 - 迭代加深搜索可能就是您想要的。