15 迭代加深可以救你的命（第3/3页）

他摇了摇头，最终说道：“我还是用我一般用的老方法吧。”

Mavis严肃地点了点头，望着大海说道：“好吧。但小心点，Frank。你没多少时间了，而一个长的死路会耗费掉很长时间。不管你用什么算法，都至少应该想想，如何保护自己不要掉进最坏的情况里。”

警用算法导论：迭代加深

节选自Drecker教授讲义

迭代加深是深度优先搜索的一种改版。它限制了每一次搜索的深度。在第k轮搜索的时候，这个算法会执行一次深度限制（max-depth）为k的深度优先搜索。

再一次来看看从A城开始找逃犯的这个例子：

我们以一轮深度优先搜索作为开始，但在搜索完第一个城市A后，我们就会结束这轮搜索。这相当于我们只在案发城市里进行了寻找。

下一轮搜索时，我们会允许深度优先搜索再多走一个城市。这一轮中，我们会在A、B和D三个城市中寻找。

当搜索逐渐进行下去时，我们需要走到离案发地越来越远的地方。在这一轮一轮搜索的过程中，我们将邻近案发地的城市搜索了多次，比如我们会将A城市搜索四次，将B城市搜索三次。

虽然这些重复的工作会加重我们的计算量，但迭代加深还是有它的好处。首先，它具有深度优先搜索节省内存的特点，同时它也像广度优先搜索那样，可以找到最短路径，并能够避免在一些最坏情况下被困在一条长的死路上。