3

我正在尝试在 Javascript 中实现广度优先搜索（还有其他算法，但目前是 bfs）。

最终我想在一个网格上应用所有的搜索算法，找到一条从起点到目标节点的路径（我知道 bfs 并不是特别擅长这个）。我已经做了一个实现，但问题是我没有提前整棵树。我想要的是给它一个 startnode 和 endnode 并在此基础上找到它们之间的路径。

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

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

我希望我已经把自己说清楚了。

在此先感谢，斯特凡

4

1 回答 1

1

如果你会“忘记”你访问的节点，你可能会遇到DFS遇到的同样的麻烦——它不是最优的（可能找不到最优路径）也不是完整的（由于无限循环，它可能找不到解决方案，即使一个存在）。

注意：

  • 即使你只记得最深层次的节点——它仍然对你没有多大帮助——请记住，例如，在二叉树中，一半的节点是叶子，所以空间复杂度仍然很大。
  • 只记住部分节点并不能保证最优性，因为最终你会重新发现一个你忘记的顶点——到那时——你让自己陷入了循环。

如果您正在寻找既完整又优化的内存效率更高的算法 -迭代深化 DFS可能就是您所追求的。

于 2012-05-09T22:03:45.467 回答