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

实际上我没有一个关于编码的问题，但是搜索算法，我希望这是可以的。在作业中，我需要解决以下问题：深度优先迭代深化搜索与深度优先搜索

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

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

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

我猜想DFS可能更好的两种情况是，如果分支因子非常大，但在给定（大）深度上有很多解决方案（例如搜索找到一种方法让国王在棋盘上进行攻击所有正方形），或者如果分支因子非常小（例如1），在这种情况下，dfid需要继续加深才能找到正确的深度。 –

thx的帮助，我知道了，并找到一个很好的例子:) –

如果你的状态空间像一个链表（即每个节点只有一个孩子）并且目标状态是叶，那么你将最终确切地描述你描述的情况。

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

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

2013-04-12 15:17:59 maditya

这是一个很好的例子，thanx的！ –

回答