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

“为什么不用一个广度优先搜索呢？”Frank问道，“实际上你们不就是在做广度优先搜索吗？从起点开始，不断地延伸搜索的范围。”

Mavis点了点头说：“广度优先搜索和迭代加深搜索有很多相似的地方。不过你忘了一点：我们的地图丢失了。如果没有地图，在广度优先搜索中你将很难记录还有哪些没有被探索过的状态。你用什么来记录目前的边界呢？迭代加深让我们可以一步步向外搜索，而不必记下所有未探索过的状态。我们只需要沿着一条有长度限制的路走就好了。”

“说的有道理。”Frank同意道。

“无论如何，搜索完两轮后我们的咖啡已经不多了，”Mavis继续说道，“一大群人，包括船长，都主动地换成喝无因咖啡了。不过我们都知道这只能给我们争取一点点额外的时间。我们重新开始了一次深度优先搜索，只不过这次我们将距离限制又向外延伸了一些。”

“你们在距离限制为3的时候找到补给站了吗？”Frank问道。

“幸运的是，我们找到了，”Mavis回复道，“那次搜索我们探索了所有距离为1、2和3的正方形。找到补给站时，完全不愿意喝无因咖啡的舵工已经将他的咖啡粉反复用了十次了。但更糟的是，大副已经开始唱‘甲板上的鼻涕虫’了，所幸，这首歌听起来其实还算欢乐。”

Frank思考了一下问道：“如果为了跳过那些重复的搜索，直接用深度优先搜索会怎么样？”

“我们会一直沿着一条长的死路走下去，直到我们的咖啡用完，”她回答道，“我之前不是和你说过这玩意救了我的命吗？”

“有道理。但这也有运气的因素吧。要是最近的补给站需要深度限制为5的深度优先搜索才能找到呢？”

“哈！你没有这么不讲道理吧，Frank。无论怎么做，你都可以找出一些幸运的情况和不幸运的情况。迭代加深可以让你在那些不幸的情况下不那么惨。它至少限制了你在每一轮中会走多远。”

“其他的算法也会这样做。”Frank反击道。

Mavis皱了皱眉说道：“我没有说迭代加深是唯一可以救我们的算法。我只是说它是我们选择的那一个。自从那次开始，我就一直在用它了。

“有一次我甚至用它去找一群愤怒的鱿鱼。我需要阻止它们把首都的港口弄得像墨一样黑。我简直无法想象那会是一种怎样的场面。有时候我在想，也许我不应该阻止它们的——如果它们真的那样做了，国王的反应一定十分精彩。”

Frank思考了好一会儿。他在想如果之前使用了迭代加深搜索是否可以节省一些时间。如果他早点终止搜索的话，他就可以倒退一步，去追查那根线头，或者那个神秘联盟的线索了。不过那样的话，他就不会去追查优先级最高的那条线索了。

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

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

警用算法导论：迭代加深

节选自Drecker教授讲义

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

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

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

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

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

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