15 迭代加深可以救你的命

“你又开始有这种表情了。”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的所有正方形也排除掉了。”