我实际上没有问题编码,但搜索算法,我希望这没关系.在作业中,我需要解决以下问题:
"描述dfid比dfs差得多的状态空间,例如O(n²)对O(n)." dfid是深度优先迭代 - 深化搜索和dfs正常深度优先搜索.我不知道如何解决这个问题,我知道最糟糕的情况运行时就像树中的两次搜索都是O(b ^ d),但我发现很难找到一个很好的例子.
我想到了一个只有2的分支的树,因为分支越低,dfid运行时越差.
有人可以帮我解决这个问题吗？
如果您的状态空间类似于链接列表(即每个节点只有1个子节点)并且目标状态是叶子,那么您将最终得到您描述的情况.
使用DFS,您将沿着每个孩子前进,直到您到达叶子.如果有n节点,则运行时间为O(n).
使用IDS,在第一次迭代中,您将只访问根的子级.在第二次迭代中,您将访问root的子项及其自己的子项(depth = 2,访问2个节点).在第三次迭代中,您将深入3,访问3个节点.因此,总访问次数是1 + 2 + .... + n = O(n ^ 2).