讀古今文學網 > 算法神探:一部谷歌首席工程師寫的CS小說 > 26 啟髮式搜索 >

26 啟髮式搜索

那個夜晚,Frank反覆回顧著所有線索。一邊密切關注著窗外的Rebecca Vinettee,一邊抱怨安全屋裡竟沒有什麼可以吃的。很快,他意識到這裡不只是缺乏食物,就連警察大樓裡的很多基礎設施都沒有,例如空白筆記本、羽毛筆及堅實的傢俱等。這時,Frank在窗戶上發現了一個超大的「出租」(Safehouse forRente!)標誌。還好,目前這裡只是修改了密碼,還沒有被租出去。

幾個小時後,Frank確認Vinettee集團的人找不到自己後,他不再盯著窗外,開始在空蕩蕩的房間中走來走去,研究案情。確定案件的時間和地點很容易——線索暗示有人明晚會攻擊城堡。不幸的是,除了時間和地點,Frank還沒有找到任何有更加價值的線索,特別是:誰去攻擊?為什麼攻擊?怎樣攻擊?還有一個重要的問題:如何才能偷偷溜出去找點吃的又不被Vinettee集團的人發現?

然而,在一小時的踱步並仔細推敲案件的蛛絲馬跡後,Frank甚至開始懷疑案發的時間和地點了。攻擊城堡的意圖似乎太過明顯,並且警察們都已準備就緒。Socks甚至將此消息告訴了他所熟知的每個人,並讓他們特別留意。

Frank停下來,猛然意識到Socks可能有問題。Frank恢復了原有的理智,「我就知道我不應該相信任何人」,Frank的腦海中重演了過去幾天發生的事,這次他理清了種種跡象。他警覺到是Socks「不小心」點燃了監獄中的文件,並毀掉了證據;他應該意識到有人已經將他去披風商店的消息洩露了出去;他至少應該對那次荒謬又湊巧的幾桶醃鰻魚救援行動產生懷疑。但最重要的是,Socks曾經錯誤地將一個點加入了二叉搜索樹,可沒有任何一個二叉搜索樹專家會犯這樣的錯誤。無疑,Socks一直令人懷疑。不過話又說回來,Frank也一直在懷疑每一個人。

這種想法給他帶來了更多的問題,而且時間和地點的問題還是沒能解決。如果Socks一直在給他們提供虛假信息,那麼Frank不得不質疑每一件事。巫師要做什麼,怎麼做?作案動機是什麼?不過Frank發現,每當他摸透精心設計的情節時,犯罪者往往會無緣無故喋喋不休地談論案發動機。此時,他也已放棄溜出去尋找食物,儘管肚子不停地咕嚕咕嚕叫。

「魔法面具將如何實現偽裝?」Frank喃喃自語道。如果盜賊計劃攻擊城堡,他們還會用這個面具嗎?或者棄之,想辦法使Marcus魔法身份徽章失效?難道他們只是需要借助它闖入警察局嗎?盜賊循著的是什麼樣的規律?Frank開始在他的筆記本中一一列舉問題,很快這些問題的數量超過了已有線索的數量。

Frank開始思考接下該採取什麼措施。時間非常緊迫,他需要深入研究啟髮式搜索算法——如何依據經驗來幫助算法快速達到目標。比如說,搜尋一隻丟失的烏龜時,因為烏龜行動緩慢,所以Frank使用「附近優先」的尋找法則;在車站尋找最新鮮的咖啡時,他依賴「大咖啡壺優先」的法則,因為這種經常是最近剛泡的;在前往一個位於未知城市的高大城堡時,「優先沿著城堡方向行走」的法則通常能讓他僅僅遇到幾個死胡同後就能抵達目的地。啟髮式搜索並非永遠完美無缺,但往往能提供有用的信息。

在警隊工作期間,Frank逐漸喜歡以「優先追查最可靠線索」的方式來進行啟髮式搜索,因為特定名稱和實物證據總好過那些流言和無端的揣測。

在Frank的職業生涯中,只有一次查案忽略了使用啟髮式搜索。當時,「玻璃箱」Billy對於一次即將發生的盜竊案已留下多種提示。首先,Billy告訴Frank逃亡車的準確等候地點、車型甚至車輪發出的特殊聲音。另外,Billy在玩飛鏢遊戲的喧鬧歡呼聲中無意間聽到了謠言,說Rebecca Vinettee也親自參與了,而且目標和魚有關係。

但是Frank忽略了所有更有效的搜索算法,而是選擇直接去追捕Rebecca Vinettee。他明白在他們裝好車之前Rebecca Vinettee可能就會消失,或可能利用另外一個路線退避到藏身處。他需要在她消失之前逮住她。他監視了首都的魚倉,那裡離逃跑的車輛僅隔兩個街區。

事後警長聲嘶力竭地解釋道:「魚倉是與此處僅相隔兩個街區,但是在另一個方向!」另外,Orb商場與逃跑的車輛只相隔四分之一個街區,一夥與Vinettee集團毫不相關的人偷竊了64塊高質量的球狀玻璃寶珠和兩個立方寶珠,裝上車逃跑了,車輪子令人討厭地咯吱咯吱叫,就像Billy說的那樣。Frank對Billy提示的描述,以及他堅持應該始終懷疑Vinettee集團的做法,都沒能讓警長信服。

但是,在目前的情況下,Frank甚至連模糊的線索也沒有了。他已經用盡大部分可靠線索,早就開始憑猜測和懷疑辦案了。如果想要取得任何進展,就還需要更多信息。他轉向自己第二種最可信賴的搜索法:當走進死胡同時,收集更多信息。他需要知道更多有關魔法面具的信息:如何使用面具,何種防禦魔法能夠挫敗它。面對這種情況,他必須要找到一位專家才行。

警用算法導論:啟髮式搜索

節選自Drecker教授講義

啟髮式搜索是依據經驗來幫助算法快速達到目標。你可能親耳聽某些警察說啟髮式搜索法只不過是隨意亂猜,但你也能看到這些警察同樣是在依靠過去幫過他們的那些經驗技巧和法則。當然,與你所能得到的信息一樣,不同的啟髮式搜索算法質量不同,認清這一點是非常重要的。

啟髮式搜索算法的一個最顯而易見的例子是在生活中導航。不管你要穿越蜿蜒的迷宮、尋找一個未知城市,還是要找到通往餐廳的路,你都會發現自己在使用啟髮式搜索作為指導。如果有兩條道路,你要先走哪一條?一種通常可靠的常見搜索法是根據簡單的距離測量來進行優先選擇。我喜歡的方法是使用「和鳥類飛翔路徑」一樣的距離測量法:如果路上沒有擋路的東西,目標有多遠?在實踐中,這種搜索法意味著我總是要選擇看起來讓我離目標更近的路徑——至少這條路徑的方向是正確的。在這條路上,我可能會走進幾個死胡同,但就整體而言,我發現這是一種有效的搜索法。

當然,還有很多糟糕的啟髮式搜索法。警察們如果在使用新的搜索法時沒有仔細檢查的話,很容易讓自己深陷麻煩中。幾年前,一位年輕的警察創造了一種特別不好的搜索法。在搗毀一個走私集團取得前所未有的成功之後,他認為所有的調查必須從碼頭上開始。事實證明這種啟髮式搜索法是錯誤的,並沒有幫助他朝正確的方向進行調查,而是經常讓他很快就走進死胡同。在18次的調查失敗後,他的警長就讓他永遠從事巡邏碼頭的工作了。

要注意啟髮式搜索並不是胡亂猜測,而是需要在包含一些有用信息的基礎上根據具體問題情況正確使用。