「你又開始有這種表情了。」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城市搜索三次。
雖然這些重複的工作會加重我們的計算量，但迭代加深還是有它的好處。首先，它具有深度優先搜索節省內存的特點，同時它也像廣度優先搜索那樣，可以找到最短路徑，並能夠避免在一些最壞情況下被困在一條長的死路上。