迭代深化与深度优先搜索

Question

我一直在阅读有关迭代深化的内容,但我不明白它与深度优先搜索的区别.

我知道深度优先搜索越来越深入.

在迭代深化中,您建立一个级别的值,如果该级别没有解决方案,则递增该值,然后从头开始(根).

这不会与深度优先搜索相同吗？

我的意思是你会继续增加和增加,直到找到解决方案.我认为这是同样的事情!我会走同一个分支,因为如果我从头开始,我会像以前一样走下同一个分支.

Answer 1

在深度优先搜索中,您从图中的某个节点开始,不断深入探索图,同时您可以找到尚未到达的新节点(或直到找到解决方案).每当DFS耗尽动作时,它就会回溯到可以做出不同选择的最新点,然后从那里进行探索.如果您的图形非常大并且只有一个解决方案,这可能是一个严重的问题,因为您可能最终沿着一个DFS路径探索整个图形,只能在查看每个节点后找到解决方案.更糟糕的是,如果图形是无限的(例如,您的图形可能包含所有数字),搜索可能不会终止.此外,一旦找到了您正在寻找的节点,您可能没有最佳路径(即使它刚好位于起始节点旁边,您也可以遍布图表寻找解决方案!)

解决此问题的一个可能方法是限制DFS采用的任何一条路径的深度.例如,我们可能会进行DFS搜索,但如果我们采用长度大于5的路径,则停止搜索.这可以确保我们永远不会从起始节点探索任何距离大于5的节点,这意味着我们永远不会探索无限地或(除非图形非常密集)我们不搜索整个图形.但是,这确实意味着我们可能找不到我们正在寻找的节点,因为我们不一定会探索整个图形.

迭代深化背后的想法是使用第二种方法,但要不断增加每个级别的深度.换句话说,我们可能尝试使用长度为1的所有路径,然后是长度为2的所有路径,然后是长度为3的路径等,直到我们最终找到有问题的节点.这意味着我们永远不会沿着无限的死端路径探索,因为每个路径的长度在每一步都有一定长度.这也意味着我们找到了到达目标节点的最短路径,因为如果我们没有在深度d找到节点但是确实在深度d + 1找到它,那么就不会有长度为d的路径(或者我们我会采取它,所以长度d + 1的路径确实是最佳的.

这与DFS的不同之处在于,它永远不会遇到图形周围需要非常长且迂回的路径而不会终止的情况.路径的长度总是有上限,所以我们永远不会最终探索不必要的分支.

这与BFS的不同之处在于,在BFS中,您必须同时将所有边缘节点保存在内存中.这需要存储器O(b ^d),其中b是分支因子.将其与迭代加深中的O(d)内存使用情况进行比较(以保持当前路径中每个d节点的状态).当然,BFS从不会多次探索相同的路径,而迭代加深可能会多次探索任何路径,因为它会增加深度限制.但是,渐近地,两者具有相同的运行时.在考虑距离d处的所有O(b ^d)节点之后,BFS以O(b ^d)步骤终止.迭代加深使用每级的O(b ^d)时间,总计为O(b ^d),但具有更高的常数因子.

简而言之:

• DFS无法保证找到最佳路径; 迭代加深是.
• DFS可以在找到目标节点之前探索整个图形; 迭代加深只有在开始和结束节点之间的距离是图中的最大值时才会这样做.
• BFS和迭代加深都在O(b ^d)中运行,但迭代加深具有更高的常数因子.
• BFS使用O(b ^d)存储器,而迭代加深仅使用O(d).

希望这可以帮助!