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

28 搜索難題

「你給我出去!」Loop教授又說了一遍。

「我是來談公事的。」Frank回應道,並沒有站起來。他能聽到身後輕輕的腳步聲,有人正拿著十字弓向他靠近。

「不太可能,」Loop教授說,「我認識Donovan警長很久了,他不是那種依靠私家偵探的人。在我印象中,他總喜歡選擇直面新的挑戰,並讓好事之徒遠離他的案件。」

Frank的手準備伸向口袋。

「別想輕舉妄動!」他身後傳來粗重的聲音。

Frank心中的怒火開始燃燒,他最恨別人拿著十字弓在背後指著自己。「只是一張羊皮紙。」他咬牙切齒地說。

「那就慢慢拿,」那個粗重的聲音說,「要是敢快了,我就射箭。」

Frank默默歎了口氣。只有一種人會這樣說話——Boolean家族。Boolean家族非黑即白的世界觀使他們成為非常能幹的警衛。你不可能通過說服Boolean家族中的任何一個人來讓自己脫身。在Boolean人看來,要麼你破壞了規則,要麼沒有破壞,沒有其他可能。

Frank極其緩慢地取出警長的信,身體往前傾,花了整整一分鐘才將信放到桌面上。他沒有靠回去,此時的動作越少越好。

Loop教授研究了一會,向她的警衛點點頭。Frank聽到十字弓的保險扣上了。他鬆了口氣,靠回椅背。Loop教授揮手示意警衛出去。

「你讓Donovan警長給你寫了一封介紹信?」Loop教授問道。

「如你所說,這是一個敏感話題。」Frank回答。

「你應該聽說過我的聲望吧。」Loop教授輕聲笑道。

「我上過你的課。」Frank低聲含糊地說,Loop教授沒有聽到。

「所以,你正在調查盜賊。你想知道什麼?」

一瞬間,她的態度發生了180度轉變。她的眼睛快速掃過Frank的臉,彷彿在分析每一個反應。所有幽默的語氣全部不見了,只剩下公事公辦的態度。Frank想知道她剛才愉快的閒談中有多大成分是逢場作戲。巫術犯罪學是一個危險的領域,而Loop教授卻一直能夠倖存下來。

「警察局有哪些保護魔法?」Frank問道。

「基本的報警咒語,」Loop教授說,「這些咒語可以發現哪些人在警察局使用了魔法,但不能預防。」

「為什麼不採用魔法屏障?」

「不切實際,」教授解釋道,「警察局僱傭了太多的巫術顧問。他們需要給證據施加神聖咒語,給囚犯施加真理咒語,給檔案施加魔法反射咒語,以及給午飯施加再加熱咒語。」

Frank點點頭,想起來一次有關魔法優先隊列的談話。

「無論如何,這太過於昂貴了,」Loop教授補充道,「只有皇家城堡和監獄配備了基本警報咒語之外的咒語。城堡擁有一大堆的保護咒語,但沒有抑制咒語。Marcus為國王做了太多的事情。」

「所以說有人能夠在城堡裡使用魔法?」Frank想確認下。

「他們可以,」Loop教授回答,「但是這樣做不太明智。城堡擁有十多個保護咒語,可以阻隔攻擊性魔法。Fredrick國王也僱傭了六個巫術警衛。他們雖是新手,但也能解開基本的咒語,況且還有Marcus。很少有巫師想跟他交手。」

「使用魔法神器怎麼樣?」

「額,這是個好問題。這取決於魔法神器本身。當然,城堡擁有針對武器類神器的保護咒語,但是沒有人可以抵抗所有神器,因為種類實在太多。鑒於多數神器無須新的魔法(之前已經被施魔法),監獄裡的咒語阻隔的咒語甚至都起不了作用。」

「什麼?」Frank問道,「我以為監獄不受任何魔法的影響。他們不是關押了邪惡巫師嗎?而且Exponentious不是也被關押在裡面嗎?他曾經試過使用魔法毀滅整個王國。為什麼他們不直接阻隔所有魔法神器?」

Loop教授乾笑了兩聲:「要讓你失望了,你無法阻隔所有神器。但也不用太擔心,這些巫師對最強大的囚犯進行了很好的警衛。並且,所有的囚犯在抵達監獄時都要先進行徹底的搜身。」

「監獄還有哪些其他的保護措施?」Frank繼續問,隨著瞭解的越來越多,他開始變得害怕起來。

「我們來仔細看看,」Loop教授說,她開始在清單上用手指打鉤,「石牆、護城河裡佈滿暴躁的獾、100個警衛、重型橡樹門、一些裝飾性松木門、每條走廊裡的輕度作嘔咒語、困難搜索咒語,還有……」

「困難搜索咒語?」Frank打斷道。

「這也不是什麼新鮮事物了,」Loop教授解釋道,「在施加咒語阻隔的咒語之前,他們在監獄裡施加了大量的保護咒語。」

「那麼困難搜索咒語是什麼意思?」Frank繼續問,一股恐懼感在心中升起。

「它讓人很難找到某個囚犯的房間。更準確地說,它能夠神奇地交換房間。如果你把這些房間想像成一個巨型的數組,困難搜索咒語即是一個交換數組下標的算法。它每天半夜都會對所有房間進行隨機交換。

「這使得任何想要從監獄中救出罪犯的想法都很難實施。由於數組值之間沒有結構,闖入者只能依靠窮舉搜索。並且,因為房間每天重新打亂,你無法在幾個晚上完成搜查。監獄警衛都抱怨這種隨機性很討人厭。他們每天需要花費幾個小時才能完成點名。不過我聽說他們最近想出了一個遊戲叫作『猜猜下一扇門後的會是誰?』,賭注最高已經達到每扇門一個元寶。」

「他們是否記錄新房間的位置?」

「不,那樣就毀了所有的目的了!如果他們製作一份所有囚犯所在房間的地圖,類似於倒排索引,那麼你就能找到囚犯了。如果你能闖進首都警察局的檔案室偷走房間分配資料,那這個咒語還有什麼用?這個咒語的目的就是讓闖入者花費數個小時在監獄裡尋找,而這顯然無法實現。所有警衛都相互認識。」

Frank終於瞭解完所有情況了。警長曾說過,Unnecessary Complexity聯盟是那個邪惡巫師Exponentious的追隨者者或同謀,他是皇家監獄裡最危險的犯人。每個人都在擔心這個聯盟正在策劃再一次的反擊,甚至可能襲擊城堡。但是實際的策劃簡單很多。聯盟正在策劃劫獄,他們打算解救聯盟領導。Frank從椅子上跳起來,幸好身後的十字弓箭手早就不在了,他衝向門口。

「謝了。」他回過頭來說,開始下樓梯。

Frank找到Notation時,他上氣不接下氣,費了很大的勁才說出:「需要你的幫助……劫獄……今晚……巫師。」

Notation看了他足足五分鐘,有些擔憂,有些興趣,但又有種被打擾到的氣憤。「快說,Frank。」她最後終於說道。

Frank仍然彎著腰,雙手撐在膝蓋上,以一種警告的眼神看著她。

「你一路跑來找我,」她說道,「我剛才聽到你喘著氣說需要我的幫助。」

Frank無視了她的意見。「我想明白了,」他終於有氣力講話了。「巫師們準備今晚劫獄。」

Notation看起來很驚訝。「劫獄?Socks劫獄想幹什麼?」

「等等。你怎麼知道是Socks?」Frank問道,有些出乎意料。

Notation很迷惑:「你什麼意思?我以為你懷疑他一段時間了。不是嗎?他一點也不狡猾。」

「是的。是有些蛛絲馬跡。」Frank沒有正面回應。

Notation沉默下來,盯著地面,她的大腦飛速運轉著,試圖將其餘的事件聯繫起來。突然,她的表情變得灰暗了,又看回Frank。「為什麼告訴我這些?」她問道,「我現在不管這個案子了,還記得嗎?」

Frank盯著她,難以置信。「你怎麼能讓那種事阻攔你的腳步?」他問道,「難道你不想抓住這些盜賊嗎?」

「我當然想,」Notation簡短地回答,「但是警長說過……」

「忘記警長吧,」Frank打斷了她的話,「這是你的案子,無論他說了什麼都不重要,不是嗎?」

Notation看起來有些矛盾,Frank抓住這個間隙。

「聽著,」他補充道,「想要抓住這些賊,我需要幫助,這次我不能調集警察,至少現在還不行。我很確信其中一個惡棍正假扮一名警察,但是我不知道他是誰。在我搞清楚之前,我無法相信任何人。」

「那麼為什麼相信我?」Notation反問。

「因為你在這裡。」Frank說。

「這不是一個好理由!」Notation說,顯然被這句話的隱含意義冒犯了。

「不是那樣,」Frank說,試圖打消她的反對意見,「我的意思是,因為你在這家店裡用你自己的資金購買定價過高的『堆』。這說明你很關心自己的工作。更重要的是,如果你以某種方式參與到巫師的劫獄中,你將很容易讓邪惡巫師聯盟給你做一個魔法『堆』。只要有更好的選擇,任何心智正常的人都不會直接走到Orb區。」

Notation站在那兒,直視著Frank。

「是你讓我來這裡的。」她咬牙切齒地說道。

「這也是好事,」Frank說,「因為我可以準確地知道今天上午在哪裡可以找到你。這是全世界最簡單的搜索問題,如同在一個數組中去找一個已知下標的值一樣簡單。我只需要直接來到Heaperous的店。不過我的確是跑過來的,」他承認,「我想到你會來得早一些,我不想與你錯過。」

Notation看起來還沒有完全釋懷:「你讓我來這裡是想驗證我是否參與此次陰謀?」

「不,我讓你來這裡是不想讓你參與其中,」Frank承認道,「我只在跑來途中想過證明這一點。我以為……」

「你不相信我?」Notation冷冷地問道,聽起來每個字都像是在譴責Frank。

「不要認為這是針對你個人的,」Frank說,「我不相信任何人。」

「你……你……」Notation氣急敗壞地說,漸漸漲紅了臉,顯然無法說完對Frank的指責。

幾分鐘後,Frank說:「你要加入嗎?」

她僵硬地點點頭。

「好,」Frank說,「兩個小時後在監獄門口見面,帶上十字弓。」

Notation再次點了點頭。

「還有一個碗。」Frank補充道。

「一個碗?」Notation問道,暫時從憤怒中走出來,很是驚訝。

Frank開口大笑:「監獄的走廊裡有一些輕度作嘔的咒語。你可能需要一個碗來嘔吐。」

警用算法導論:期末考試複習課

節選自Drecker教授講義

如果你從這門課中只學到了一樣東西,那應該是:高效算法的關鍵在於信息。當遇到一個新的問題時,應該花些時間理解這個問題的結構和它的數據。問題擁有的結構越多,你越有可能使用這些信息。正如你所看到的,在一個有序數組中找到一個值比在一個完全隨機的數組中找到一個值要簡單得多。有時候,你甚至可以建立附屬的數據結構,例如堆或逆向索引,以提供所需要的結構。儘管如此,解決問題的第一步始終應該是理解問題。