“你又开始有这种表情了。”Mavis说道。Frank抬起头，恼怒地看了看TCP Flyer号的船长。他想一个人静静地思考一下，然而这十分钟内他已经被打断两次了。
“什么表情？”他低吼道。
“就是这种表情，”她向Frank所在的方向挥挥手说道，“你在怀疑你自己，你在想是不是花太多时间在这些走不通的线索上了。”
“我怎么可能会这么想？”Frank说道。
“我听到那个小孩说的话了，”Mavis解释道，“突然间，你的时间变得紧迫了许多。然而我们却至少还需要四个小时才能到Usb港。”
Frank点了点头说道：“如果这艘破船……”
“嘿，冷静点。就算你开始怀疑自己，也没理由侮辱我的船。”
“说的也对。”Frank低声说道，似是而非地道歉。
Frank已经在脑海里来回考虑过了每一个线索，思考是否其中的某个可以更快地给他答案。他知道那些日志是好线索——至少是这种案件中他能找到的最好线索了，但是它们也耗费了他很多时间：乘坐TCP Flyer号奔波于各个港口之间几乎就花掉了他一整天的时间。
Mavis弯下腰，坐在了Frank身边，说道：“迭代加深？”
Frank耸了耸肩。他也想到过这个主意。迭代加深是一个综合深度优先搜索和广度优先搜索的算法。这种算法一轮接一轮地搜索下去，而每一轮都是一个将深度限制为特定长度的深度优先搜索。
“我一直不是很喜欢用这种方法。”Frank承认道。他从来就不愿忍受在每一轮中将搜索过的一部分一次又一次地重复进行，因为这样简直是太浪费时间和资源了。
Mavis笑道：“看来你还没有遇到过足够多的死路。”
Frank的眉毛动了动：“你现在是在和一个私家侦探说话。我遇到过的死路比正确的路还多。”
“有没有因此追丢过罪犯呢？”Mavis问道。
“有几次吧。”Frank承认道。
“那么你就应该懂得欣赏迭代加深这种方法，”Mavis说道，“我第一次看人用这种方法时，也因为它需要不断地从头开始搜索而很不喜欢它。不过这种方法已经不止一次救过我的命了。”
“从头开始搜索救过你的命？”Frank问道。他无法掩饰语气中的不可置信。
Mavis看向大海，说道：“它第一次救我命的时候我还是一个小孩。我当时在一艘名为Void Star的货船上当学徒。那艘船棒极了——它可以装任何东西。当时，我们在Razor Ridges中迷路了，那是一片充满像迷宫一样的错落的火山口的海域。而且当时我们有一项重要的补给就要用完了。”
“水吗？”Frank问道。
“不是，”Mavis回答道，“我们剩的水和食物至少还够用两个星期。是咖啡快用完了——这对船上的官员来说真是一个坏消息。只要一天不喝咖啡，船上的大副就该开始焦躁不安，不停地哼唱让人绝望的水手歌。”
“听起来还没那么糟糕嘛。”
“要是没有咖啡了，他唱起歌来可以把方圆八里的凶鸟都吸引过来。”
Frank听着皱了皱眉。
“无论怎样，”Mavis继续道，“咖啡对我们的船来说太重要了。根据船长的估计，我们只剩下不到两天的时间可以用来找下一个有补给站的岛。她知道我们附近肯定有一个，但却不知道具体方位。我们的地图也在之前的即兴纸飞机大赛中丢失了，而且在那种大雾中，除非行驶到一个补给站旁边，否则根本看不到它。
“于是我们开始寻找一个有咖啡的岛。当时我还是一个新手，还没有听说过迭代加深，所以就大胆地提议说用深度优先搜索。船长只是笑了笑，对我说她永远都不会信任在Razor Ridges中使用深度优先搜索，因为死路太多了。
“她将那块海域划分成了边长一英里的正方形。在当时的大雾下，一英里几乎是能见度的极限了，所以我们必须走到补给站所在的正方形内才能看到它。然后我们就开始用迭代加深进行搜索了。我们首先用了一个深度限制为1的深度优先搜索，我们参照的是常用的北→东→南→西的顺序。虽然在这轮搜索中什么都没找到，但至少我们只用了数小时就排除了相邻的所有正方形。”
Mavis摇了摇头，继续说道：“没有任何补给站的踪影。所以我们重新开始，又从原来的起点开始做了一次深度限制为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城市搜索三次。
虽然这些重复的工作会加重我们的计算量，但迭代加深还是有它的好处。首先，它具有深度优先搜索节省内存的特点，同时它也像广度优先搜索那样，可以找到最短路径，并能够避免在一些最坏情况下被困在一条长的死路上。