我一直在阅读有关迭代深化的内容，但我不明白它与深度优先搜索的区别 .
我知道深度优先搜索越来越深入 .
在迭代深化中，您 Build 一个级别的值，如果该级别没有解决方案，则递增该值，然后从头开始（根） .
Wouldn't this be the same thing as depth-first search?
我的意思是你会继续增加和增加，直到找到解决方案 . 我认为这是同样的事情！我会走同一个分支，因为如果我从头开始，我会像以前一样走下同一个分支 .
在深度优先搜索中，您从图中的某个节点开始，不断深入探索图，同时您可以找到尚未到达的新节点（或直到找到解决方案） . 每当DFS耗尽动作时，它就会回溯到可以做出不同选择的最新点，然后从那里进行探索 . 如果您的图形非常大并且只有一个解决方案，这可能是一个严重的问题，因为您可能最终沿着一个DFS路径探索整个图形，只能在查看每个节点后找到解决方案 . 更糟糕的是，如果图形是无限的（例如，您的图形可能包含所有数字），搜索可能不会终止 . 此外，一旦找到了您正在寻找的节点，您可能没有最佳路径（即使它刚好位于起始节点旁边，您也可以遍布图表寻找解决方案！）
解决此问题的一个可能方法是限制DFS采用的任何一条路径的深度 . 例如，我们可能会进行DFS搜索，但如果我们采用长度大于5的路径，则停止搜索 . 这可以确保我们永远不会从起始节点探索任何距离大于5的节点，这意味着我们永远不会探索无限地或（除非图形非常密集）我们不搜索整个图形 . 但是，这确实意味着我们可能找不到我们正在寻找的节点，因为我们不一定会探索整个图形 .
迭代深化背后的想法是使用第二种方法，但要不断增加每个级别的深度 . 换句话说，我们可能尝试使用长度为1的所有路径，然后是长度为2的所有路径，然后是长度为3的路径等，直到我们最终找到有问题的节点 . 这意味着我们永远不会沿着无限的死端路径探索，因为每个路径的长度在每一步都有一定长度 . 这也意味着我们找到了到达目标节点的最短路径，因为如果我们在深度d找不到节点但是确实在深度d 1找到它，那么就不会有长度为d的路径（或者我们会已经采取了它，所以长度d 1的路径确实是最佳的 .
这与DFS的不同之处在于，它永远不会遇到图形周围需要非常长且迂回的路径而不会终止的情况 . 路径的长度总是有上限，所以我们永远不会最终探索不必要的分支 .
这与BFS的不同之处在于，在BFS中，您必须同时将所有边缘节点保存在内存中 . 这需要存储器O（bd），其中b是分支因子 . 将其与迭代加深中的O（d）内存使用情况进行比较（以保持当前路径中每个d节点的状态） . 当然，BFS从不会多次探索相同的路径，而迭代加深可能会多次探索任何路径，因为它会增加深度限制 . 但是，渐近地，两者具有相同的运行时 . 在考虑距离d处的所有O（bd）节点之后，BFS以O（bd）步骤终止 . 迭代加深使用每级的O（bd）时间，总计为O（bd），但具有更高的常数因子 .
简而言之：
DFS无法保证找到最佳路径;迭代加深是 .
DFS可以在找到目标节点之前探索整个图形;迭代加深只有在开始和结束节点之间的距离是图中的最大值时才会这样做 .
BFS和迭代加深都在O（bd）中运行，但迭代加深具有更高的常数因子 .
BFS使用O（bd）内存，而迭代加深仅使用O（d） .
希望这可以帮助！
关于这一点，wikipedia上有一个不错的页面 .
我认为你错过的基本思想是迭代加深主要是一种启发式 . 当一个解决方案很可能被发现接近根迭代加深时会发现它相对较快，而直接深度优先搜索可能会做出决定并花费大量时间在一个没有结果的深分支上 .
（当搜索树可以是无限的时候，这一点尤其重要 . 自从DFS可以永久卡住而BFS或迭代加深肯定会在某一天找到答案（如果存在的话））
只是添加到已经存在的内容，但这里有来自丹佛大学移动AI实验室的一些视频，显示了这些差异 .
http://movingai.com/dfid.html
您可以在他们的示例中看到迭代加深胜利，当目标很浅（解决方案深度3，树深度）并且解决方案在右侧时，但无论解决方案是在最后一行，DFS都会获胜 .
我进入了关于国际象棋编程的阅读，接下来我正在考虑quiescence search如果你想了解更多有关人工智能编程的搜索策略的话 .
3 回答
在深度优先搜索中，您从图中的某个节点开始，不断深入探索图，同时您可以找到尚未到达的新节点（或直到找到解决方案） . 每当DFS耗尽动作时，它就会回溯到可以做出不同选择的最新点，然后从那里进行探索 . 如果您的图形非常大并且只有一个解决方案，这可能是一个严重的问题，因为您可能最终沿着一个DFS路径探索整个图形，只能在查看每个节点后找到解决方案 . 更糟糕的是，如果图形是无限的（例如，您的图形可能包含所有数字），搜索可能不会终止 . 此外，一旦找到了您正在寻找的节点，您可能没有最佳路径（即使它刚好位于起始节点旁边，您也可以遍布图表寻找解决方案！）
解决此问题的一个可能方法是限制DFS采用的任何一条路径的深度 . 例如，我们可能会进行DFS搜索，但如果我们采用长度大于5的路径，则停止搜索 . 这可以确保我们永远不会从起始节点探索任何距离大于5的节点，这意味着我们永远不会探索无限地或（除非图形非常密集）我们不搜索整个图形 . 但是，这确实意味着我们可能找不到我们正在寻找的节点，因为我们不一定会探索整个图形 .
迭代深化背后的想法是使用第二种方法，但要不断增加每个级别的深度 . 换句话说，我们可能尝试使用长度为1的所有路径，然后是长度为2的所有路径，然后是长度为3的路径等，直到我们最终找到有问题的节点 . 这意味着我们永远不会沿着无限的死端路径探索，因为每个路径的长度在每一步都有一定长度 . 这也意味着我们找到了到达目标节点的最短路径，因为如果我们在深度d找不到节点但是确实在深度d 1找到它，那么就不会有长度为d的路径（或者我们会已经采取了它，所以长度d 1的路径确实是最佳的 .
这与DFS的不同之处在于，它永远不会遇到图形周围需要非常长且迂回的路径而不会终止的情况 . 路径的长度总是有上限，所以我们永远不会最终探索不必要的分支 .
这与BFS的不同之处在于，在BFS中，您必须同时将所有边缘节点保存在内存中 . 这需要存储器O（bd），其中b是分支因子 . 将其与迭代加深中的O（d）内存使用情况进行比较（以保持当前路径中每个d节点的状态） . 当然，BFS从不会多次探索相同的路径，而迭代加深可能会多次探索任何路径，因为它会增加深度限制 . 但是，渐近地，两者具有相同的运行时 . 在考虑距离d处的所有O（bd）节点之后，BFS以O（bd）步骤终止 . 迭代加深使用每级的O（bd）时间，总计为O（bd），但具有更高的常数因子 .
简而言之：
DFS无法保证找到最佳路径;迭代加深是 .
DFS可以在找到目标节点之前探索整个图形;迭代加深只有在开始和结束节点之间的距离是图中的最大值时才会这样做 .
BFS和迭代加深都在O（bd）中运行，但迭代加深具有更高的常数因子 .
BFS使用O（bd）内存，而迭代加深仅使用O（d） .
希望这可以帮助！
关于这一点，wikipedia上有一个不错的页面 .
我认为你错过的基本思想是迭代加深主要是一种启发式 . 当一个解决方案很可能被发现接近根迭代加深时会发现它相对较快，而直接深度优先搜索可能会做出决定并花费大量时间在一个没有结果的深分支上 .
（当搜索树可以是无限的时候，这一点尤其重要 . 自从DFS可以永久卡住而BFS或迭代加深肯定会在某一天找到答案（如果存在的话））
只是添加到已经存在的内容，但这里有来自丹佛大学移动AI实验室的一些视频，显示了这些差异 .
http://movingai.com/dfid.html
您可以在他们的示例中看到迭代加深胜利，当目标很浅（解决方案深度3，树深度）并且解决方案在右侧时，但无论解决方案是在最后一行，DFS都会获胜 .
我进入了关于国际象棋编程的阅读，接下来我正在考虑quiescence search如果你想了解更多有关人工智能编程的搜索策略的话 .