广度优先搜索实现

Question

我想在Javascript中实现广度优先搜索（也是其他算法，但目前是bfs）。我最终想要在网格中应用所有的搜索算法，找到从开始到目标节点的路径（我知道bfs并不是特别擅长这一点）。我已经做了一个实现，但问题是我没有预先提供整棵树。我想要的是给它一个startnode和endnode，并基于它找到它们之间的路径。

我遇到的问题是，当我确定相邻的网格时，它会返回所有邻居，所以即使是已经遍历的邻居。这将其转化为图搜索而不是树搜索。解决这个问题的一个方法是记住所有路径，以便我可以检查哪些邻居已经遍历，因此不需要进一步检查。但是，正如我在搜索算法课程中所了解的，bfs在当前深度级别上具有所有节点的内存使用情况。如果我存储所有的路径，那么它会消耗更多的内存吗？

当我没有预先设置树结构并且仍然避免有循环时，是否有可能只保存bfs正在搜索的当前深度的节点？

我希望我已经明确自己。

由于提前， 斯特凡

Answer 1

如果将“忘记”您访问的节点，就可能进入DFS遇到同样的烦恼 - 这是不是最佳的（可能找不到最优路径），也不完整（由于无限循环，即使存在解决方案，也可能找不到解决方案）。

需要注意的是：

• 即使你只记得最深层次的节点 - 它仍然不帮你了 - 记得在二叉树，例如，节点的一半是叶子，所以空间复杂性仍然很大。
• 只记住一部分节点并不能保证最佳性，因为最终你会重新发现一个你已经忘记的顶点 - 然后 - 你进入了一个循环。

如果您正在寻找更多的内存有效的算法，既完整又优化 - Iterative Deepening DFS可能就是您所追求的。