沒聽見敲門聲，門竟然開了——只有大門鉸鏈的嘎吱嘎吱聲宣告了有人到訪。Frank立馬起身欲取來十字弓，卻又驟然停住，他想若是Vinettee集團的人登門造訪，一定會敲門——不過是用斧頭。進門者無論是誰，想必都有話要說。於是，Frank伸手拿起馬克杯，將杯底僅剩的那點冷掉的咖啡一飲而盡。
「Donovan警長，」Frank看到來訪者說道，「是什麼風把您吹到這片和諧的街坊來了？我還以為您再也不敢越過第15號街了呢。」
「好久不見，」Donovan警長簡短地說道，「Frank，別來無恙？」
「好極了。」Frank乾巴巴地答道，同時盯著在屋裡緩緩踱步的Donovan警長。
Donovan警長掃視著Frank寒酸的辦公室，他紅色的警官披風在身後沙沙作響。「私家偵探的遊戲玩得可好？」
「夠還債。」Frank在說謊。
Donovan警長點了點頭。他稍作停頓，然後轉向書櫃，看了看書櫃上的書。
「您這次來算是探訪故人了？」Frank說道，「那我應該問候一下Marlene和孩子們的近況吧？」
「他們好得很，」Donovan警長頭也不回地答道，「Marlene的海龜美容生意這些日子做得不錯。Bill去年加入警隊了。Veronica在做會計，我們最後本該……」
「我只是隨便問問。」Frank打斷了Donovan警長的話。
Donovan警長聳聳肩。他從書架上抽出一本書，隨意翻了起來。Frank伸長脖子瞧了瞧封面——《警察學院年鑒：第21班》。
「你想要什麼，Donovan警長？」Frank問道。
Donovan警長與Frank對視了一下，「我需要你的幫助，Frank。」他說。
Frank直起了身子。在Frank離開警隊後的五年間，Donovan警長一共上門見了他兩次，兩次都是來警告他別再插手案件。這次Frank也已經做好了被威脅的準備，但現在，Donovan警長似乎遇到了特殊的問題——幫助解決這種程度的問題，或許可以用報酬還清Frank拖欠的房租。
「我早就不是警隊的人了，」Frank漫不經心地說道，「你怎麼不派個你信得過的偵探去接手？」
「我需要警隊之外的人，」Donovan警長說道，「別裝了，Frank。如果你不清楚我上這兒來意味著什麼，那你也不是我需要的人。」
Frank笑了：「出內鬼了？在你的隊裡？」
「更糟。昨晚有人闖進局裡的檔案室，偷走了五百多份卷宗。」
「他們想找什麼呢？」Frank問道。坐在椅子上的他，不假思索地往前探身，並迅速地抄起一卷新羊皮紙和一桿羽毛筆。Frank對這一系列的動作已駕輕就熟，就如同喝咖啡和爬樓梯一般。
「我不知道，」Donovan警長說道，「無跡可循！他們偷了整架整架的文件，從財產糾紛的文件到費用報表。我們記錄的有關殺手、名流、私家偵探、司法人員的分類文件，統統被他們拿走了……甚至連農夫Swinson的兩筐噪聲投訴信也被他們拿去了。但奇怪的是，其餘架子他們連碰都沒碰。據我們統計，至少丟失了512份文件。」
「沒準是農夫Swinson的某位鄰居干的，」Frank打趣道，「他們一定是聽說了，但凡超過100封投訴信，就會有實習生到你家給你嚴厲地上上課。」
Donovan警長懶得理他，他只是可憐地瞪著眼，直到Frank清了清嗓子，才打破沉默：「所以，你想讓我去找回這些文件？」
Donovan警長搖搖頭說：「我想讓你找出那些賊。我們有文件的備份。我想知道，他們想要什麼信息，打算用來做什麼。」
「是一個搜索問題啊。」Frank若有所思地說。當年在警隊時，Frank的兩大特長就是解決搜索問題，以及惹怒Donovan警長。
「國王知道了嗎？」Frank問道。
「我昨天已向國王簡要稟報過了，」Donovan警長說道，聲音中透出一絲不悅，「自打那個瘋癲癲的巫師鬧過之後，國王堅決要求對諸事進行每日簡報。」兩年前，一個名為Exponentious的狂妄巫師曾企圖摧毀整個王國。此後，Fredrick國王親自製定了全面的措施，以提升王國的安全。他為此頒布了三百多條新的安全法規，其中至少有五條是關於十層以下政府大樓內的公文保管的。
「這也不能怪他，」Donovan警長嘟囔道，「當時真是挺險的。多虧有Ann公主，否則誰知道王國今天是何種境地。」
Frank默默點頭。當年Exponentious巫師對研究算法的學者們施下詛咒，從而襲擊了王國的算法基礎。短短幾個月的時間，就連簡單的操作都被他搞得低效不堪，王國逐漸瀕臨停轉。損壞的跡象隨處可見，甚至在當地的麵包店裡，Frank都親身目睹了恐慌爆發，因為顧客們發現，他們都想不起來如何排成一個隊列了。
「當然了，國王對此問題也抱有個人興趣，」Donovan警長生氣並急躁地說道，「他想知道所有的細節：誰在負責此案？我們在用哪些搜索算法？我們是否搜遍了所有相鄰的建築物？」
Frank強忍住笑，開始仔細考慮這個問題。為首都的警察部隊客串一回顧問，應該能拿到不少錢。他低頭瞥了一眼自己的腳，一根腳趾頭已經快從鞋子的破洞裡露出來了。「如果讓我做顧問，」他說，「那就得按我的方式來。」
決定性的關鍵就在這兒了。五年前他被踢出警隊，就是因為他太按自己的方式做事。而Donovan警長是個信奉規則和命令的人。Frank上一次使用了啟髮式搜索，也是最後的那根稻草——於是就在當天下午，Donovan警長收回了他的警徽。不過，話又說回來，按Frank的方式做事總能得到結果。
「不出我所料。」Donovan警長最終答道。他從披風式風衣下抽出一份薄薄的文件夾，丟在Frank的桌上。
「我會跟你聯絡的。」Donovan警長說。然後，他毫無任何表示地轉身離開了辦公室。
在接下來的三個小時內，Frank喝了12杯咖啡，此時他弓身伏坐在桌前，第七次翻閱著這份薄薄的信息文件夾。文字在搖曳的燭光中跳動搖擺，卻未能顯示任何新的信息。
線索並不多。Donovan警長給他的是丟失文件的清單及事發當晚的值班名冊，僅此而已。
最後，Frank誇張地歎了口氣，抓起一張羊皮紙，開始做筆記。
任何搜索問題的第一步，都是確定你想找到的東西——目標，他的老教練在警用算法導論課上是這麼稱呼的。Frank很早就吸取了這個教訓：他在成為警官的第一個星期，就被任命去找回公爵的名貴種馬，結果那天下午他帶了一隻42磅重的海龜得意地回到警局。顯然，這只搶眼的爬行動物不是目標。如果你找錯了東西，那算法再好也毫無意義。
這一次的案件中，問題不在於是什麼，而在於是誰。Donovan警長在這一點上說對了。一旦賊拿到了文件，警方就算找回來也於事無濟。因為賊已經獲得了他們想要的任何信息。
所以，他的目標很簡單：弄清楚是哪個人或哪些人偷走了文件。
任何搜索問題的第二步，都是確定搜索空間。你要搜哪裡？Frank每天找自己的鑰匙時，搜索空間是辦公室裡的所有平坦表面。而當Frank想找出一個犯罪分子時，他的搜索空間則是首都附近的每一個人。
Frank坐了回去，揉了揉眼睛。這是一個很大的搜索問題——要在犯罪之都找到一個特定的罪犯。不過他遇過更糟的情況。
既然他已經明確了問題，那麼現在他可以開始選擇算法了。線性搜索首先出局，因為他可沒能耐去審問城裡的每一個人。他還可以排除掉過去在學院裡學來的很多其他的花哨算法。對於這樣的問題，他必須回到自己的基本搜索算法工具包，這是私家偵探最值得信賴的朋友。
Frank在羊皮紙上寫下一條筆記。他有了尋找的目標，知道了搜索空間，現在也確定了算法，是時候開工了。
警用算法導論：搜索問題
節選自Drecker教授講義
在本課程中，我們將討論幾種不同的算法（以及相關的數據結構），來解決搜索問題。搜索問題的定義為：任何需要我們在可能的空間範圍（搜索空間）內，找到一個特定值（即目標）的問題。
等你們將來畢業成為警察後，每天都會遇到可被歸為搜索問題的問題。搜索問題的廣義定義涵蓋了很多不同的計算問題，例如「在警察日誌上搜索某一特定條目」這樣的簡單搜索，以及「從窩點中找到房間」，乃至「找出符合某些條件的所有逮捕記錄」這樣的複雜搜索。這個類別是無法窮舉的，但是在後面，我會給你們講解一些基本和重要算法的簡單例子。
該類別中所描述的算法擁有下面三個共同元素。
目標：你所尋找的那條數據。目標可以是一個特定的值，或是一條表示搜索成功完成的標準。
搜索空間：用於探測目標的所有可能性的組。例如，搜索空間可以是一份數值列表，或是圖中的所有節點。搜索空間內的單個可能性被稱為狀態。
搜索算法：用於進行搜索的一組具體步驟或指令。
部分搜索問題會有額外的要求或複雜性，在我們學習不同的算法時將會逐一談到。