0

在此处输入图像描述

我首先尝试将 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 会有什么不同吗？好像很相似

4

1 回答 1

1

  1. 是的，当您实施 DFS 时，您可以并且应该通过跟踪您已经访问过的节点来摆脱重复的节点。如果你不这样做，你的代码在找到一个循环时不会终止。不要忘记清除每个新级别的访问节点集。因此，请从您的列表中忽略访问过的节点，除非包含正在考虑但未重新访问过的节点很重要。

  2. 如果你写出 BFS 和 DFS 的扩展，你会发现 IDDFS 开始看起来像 BFS，最终看起来越来越像 DFS，随着级别的提高。当 level = length-of-longest-path 时，瞧，你得到了 DFS，这并不奇怪，因为 IDDFS是DFS，只有在给定数量处切断路径；在那种特殊情况下，这个数字没有任何影响，因为没有足够长的路径可以被切断。

  3. 图中的顺序没有很好地定义。您自己选择一个或另一个订单。如果您随机选择下一个节点，您将获得非确定性算法。如果您按字母顺序选择它们，不知道，那么您会得到一些确定性。有时区别并不重要，但确定性对于调试代码等很有用。现在，当你做这个练习时，你这样做是为了查看模式，所以最好忽略随机性。

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

于 2016-11-23T16:34:45.190 回答