我正在尝试在Javascript中实现广度优先搜索（也是其他算法，但目前是bfs） .
最终我想在网格上应用所有搜索算法，以找到从开始到目标节点的路径（我知道bfs在这方面并不是特别擅长） . 我已经实现了，但问题是我没有事先提供整个树 . 我想要的是给它一个startnode和endnode，并在此基础上找到它们之间的路径 .
我遇到的问题是，当我确定相邻的网格方块时，它返回所有邻居，所以即使是那些已经遍历的邻居 . 将其转换为图搜索而不是树搜索 . 解决它的一种方法是记住所有路径，以便我可以检查哪些邻居已经被遍历，因此不需要进一步检查 . 但是，正如我在搜索算法课程中学到的，bfs具有当前深度级别上所有节点的内存使用量 . 如果我存储所有路径，那么它会消耗比这更多的内存？
是否有可能只保留bfs正在搜索的当前深度的节点，当我没有预先提供树结构并且仍然避免循环时？
我希望我已经清楚了 .
在此先感谢，Stefan
1 回答
如果你将访问你所访问的节点，你可能会遇到同样的麻烦 - 它不是最佳的（可能找不到最佳路径）也不完整（由于无限循环，它可能找不到解决方案，即使存在一个） .
注意：
即使你只记得最深层次的节点 - 它仍然没有多大帮助 - 请记住，在二叉树中，例如，一半的节点是叶子，因此空间复杂性仍然很大 .
只记住部分节点并不能保证最佳性，因为最终你会重新发现一个你忘记的顶点 - 然后 - 你自己进入一个循环 .
如果您正在寻找更加完整且最优的内存效率更高的算法，那么Iterative Deepening DFS可能就是您所追求的 .