如何在图上应用迭代加深深度优先搜索 (IDDFS)

Question

我试图通过首先以树形形式将 IDDFS 应用于该图，结果是这样的：

 At level 1: d,e,p
 At level 2: d,b,e,c,e,h,r,p,q
 At level 3: d,b,a,e,h,c,a,e,h,q,p,r,f,p,q
 At level 4: d,b,a,e,h,p,q,c,a,e,h,q,p,q,r,f,c,GOAL

我对路径中那些重复的节点感到困惑，我们是否可以消除它们，否则它们会出现在最终路径中？

这是遍历图形以达到目标的正确方法吗？以及我们如何知道图中接下来要访问哪个节点（例如，在树中我们从左到右开始）。

如果我们在同一个图上应用 DFS 和 BFS，路径会是什么？

DFS 结果和 IDDFS 会有什么不同吗？好像有点像

Answer 1

是的，您可以并且应该在实现 DFS 时通过跟踪您已经访问过的节点来摆脱重复的节点。如果不这样做，您的代码将不会在找到循环时终止。不要忘记清除每个新级别的已访问节点集。因此，请从您的列表中删除访问过的节点，除非包含正在考虑但未重新访问的节点很重要。
如果你写出 BFS 和 DFS 的扩展，你会发现 IDDFS 开始看起来像 BFS，随着关卡的增加，它最终看起来越来越像 DFS。当 level = length-of-longest-path 时，瞧，你得到 DFS，这并不奇怪，因为 IDDFS 是 DFS，只有路径在给定数字处被切断；在这种特殊情况下，该数字无效，因为没有任何路径足够长可以被切断。
图表中的顺序未明确定义。您自己选择一个订单或另一个订单。如果你随机选择下一个节点，你会得到非确定性算法。如果你选择它们，不知道，按字母顺序，那么你会得到一些确定性。有时区别并不重要，但确定性对调试代码等很有帮助。现在，当你做这个练习时，你这样做是为了查看模式，所以最好忽略随机性。

你的问题看起来确实像作业。 ;)

How to apply Iterative Deepening Depth First Search(IDDFS) on Graphs