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

Question

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

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

我想到了一棵只有 2 个分支的树，因为分支越低，dfid 运行时就越差。

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

Answer 1

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

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

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