深度优先迭代加深搜索与深度优先搜索

Question

其实我没有关于编码的问题，但是搜索算法，我希望这是可以的。在作业中，我需要解决以下问题：

描述其中dfid比dfs差得多的状态空间，例如O(n²)与O(N)。dfid是深度优先迭代加深搜索，dfs是普通深度优先搜索。我不确定如何解决这个问题，我知道对于两个树中的搜索，最坏的情况下运行时间都是O(b^d)，但我发现很难找到一个好的例子。

我考虑一棵分支率只有2的树，因为分支率越低，dfid运行时的情况就越糟糕。

有人能帮我解决这个问题吗？

Answer 1

如果您的状态空间就像一个链表(即每个节点只有一个子节点)，并且目标状态是叶子，那么您最终将得到您所描述的情况。

使用DFS，您将沿着每个子进程前进，直到到达叶。如果有n节点，则运行时间为O(n)。

使用IDS，在第一次迭代中，您将只访问根的子级。在第二次迭代中，您将访问根的子节点和它自己的子节点(深度= 2，访问了2个节点)。在第三次迭代中，您将访问3个节点，深度为3。因此，访问的总次数是1+2+ ...+n= O(n^2)。