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

“她将那块海域划分成了边长一英里的正方形。在当时的大雾下，一英里几乎是能见度的极限了，所以我们必须走到补给站所在的正方形内才能看到它。然后我们就开始用迭代加深进行搜索了。我们首先用了一个深度限制为1的深度优先搜索，我们参照的是常用的北→东→南→西的顺序。虽然在这轮搜索中什么都没找到，但至少我们只用了数小时就排除了相邻的所有正方形。”

Mavis摇了摇头，继续说道：“没有任何补给站的踪影。所以我们重新开始，又从原来的起点开始做了一次深度限制为2的深度优先搜索。因此这次我们搜索的范围大了许多。在这次搜索中，我们又一次重复走过了和起点相邻的那些正方形。虽然这次搜索完我们还是一无所获，但至少我们很快地将距离起点为2的所有正方形也排除掉了。”

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

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

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

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

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

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

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

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

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

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

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

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

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

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