Frank、Socks和警官Notation現在正圍在監獄外牆的後門邊。儘管鐵門上銹跡斑斑，但在Frank用力踢了兩腳後，鐵門依然完好無損。只不過這兩腳讓鐵門上的鐵銹粉末和灰塵全都揚到了空中。而Frank在整個過程中一如既往地罵罵咧咧，讓站在一旁的Notation學會了至少六個新的用Boolean來罵人的詞彙。
「所以……看來這樣行不通。」Socks說道。Frank無視了他，開始研究門鎖的結構。這是一種很常見的密碼鎖，第一行上放著1、2、3、A、B、C共六個按鈕，而第二行則放著一個確定按鈕。
「看來我們得用老辦法了。」Frank說道。
「我們的老辦法不就是踢門嗎？」Notation說道。
Frank同樣無視了Notation。「Socks，你知道任何開鎖的咒語嗎？」
「當然不知道，」Socks大聲回答道，「那些咒語是違法的！」
「那有沒有可以削弱這個鎖的咒語？讓鎖鏈變脆弱點的？」Frank接著問道。
「你想讓我幫助你去破壞別人的財產？」Socks看起來嚇壞了，「這比開鎖還要糟糕。你知道我會惹上多大的麻煩嗎？」
「搜索咒語呢？完全組合咒語？或者廣度優先搜索咒語？」Notation插話道。她不想再聽Socks談論咒語合法與非法的話題了，在之前Frank問Socks能不能用魔法去複製一枚金幣時，Socks已經說得夠多了。當然，她和Socks都覺得用魔法去複製金幣這個事情是不道德的。
「我用過幾次廣度優先搜索咒語，」Socks回答道，「我真正擅長的是二叉搜索樹。不過我對很大一部分計算用的方法都很熟悉。曾經有次……」
「廣度優先搜索算法對這個鎖會有用嗎？」Frank打斷道。多年來，Frank在辦案中和很多巫師都合作過。其中既有聲名遠揚的大牌巫師，也有相對不那麼出名的巫師。他至少已經見識過十多種用來開鎖的咒語了，不過還從來沒有遇到過用廣度優先搜索咒語真正把鎖打開的。
Notation笑著說：「肯定有用！聽起來有點抽像，不過我最近在警用算法課上見過一個類似的問題。你仔細想想看，其實開密碼鎖就是一個搜索問題。你需要輸入一串字符去打開鎖，而搜索空間就是所有可以用那些字符組成的字符串。每一個這樣的字符串，從只有一個字符的，比如A和1，到那些複雜的字符串，比如ABC123CBA321，都是一個有效的選項。而我們要搜索的目標就是那個可以打開鎖的字符串。」
「不過我們都不知道這個密碼裡有多少個字符，」Socks說道，「有可能這個鎖的密碼有30位那麼長。」
「所以她才會建議用廣度優先搜索。」Frank說道，邊回答Socks的問題邊思考著。
「我不明白。」Socks說。
Notation緊接著解釋道：「你看，廣度優先搜索從一個起點開始，慢慢沿著一個邊界推進。所以理所當然地它就會由短到長地嘗試所有可能的字符串。」
「啊？」Socks說道，看起來Socks已經困惑得有些驚慌失措了，「我以為廣度優先搜索是用一個魔法表的。我從來都只是用一個魔法表的。難道它不就是用一個魔法表來搜索的嗎？」
「是的，」Notation說道，「廣度優先搜索會記錄下包含所有接下來需要嘗試的選項的一個列表。整個算法說到底就是一個不停在執行的循環。每次循環時，這個算法都會從那個選項列表最前面拿出選項去嘗試，同時將新的選項加到列表後面。每一次循環執行的時候，我們都會選出列表第一個可能的選項。如果它並不是我們的搜索目標，我們就將所有由它可以演變成的之前還沒有嘗試過的選項加到列表最後。
「整個搜索過程從一個起始點開始。在我們現在這個情況下，這個起始點就是一個空密碼字符串。而我們每嘗試一個密碼，都會將所有由這個密碼可以演變到的其他密碼加到列表最後。具體來說，每次嘗試一個密碼之後，我們都會嘗試在這個密碼後面再加上一個字符。舉個例子，我們現在知道這個密碼鎖的密碼只會包含1、2、3、A、B、C這六個字符。所以在我們嘗試過3A之後，就需要將3A1、3A2、3A3、3AA、3AB、3AC加到我們列表的最後。」
Socks聚精會神地思考著，隨後問道：「我們怎麼知道之後應該加哪些選項？」
「把它想像成一棵由所有可能選項組成的樹，」Notation說道，「樹的每一個分枝，即節點就是我們列表中的一個可能的密碼，比如3A。而由這個分叉點分出去的那些節點就是由這個密碼再加上一位可以得到的新的可能字符。而廣度優先搜索就是在搜索完樹的一層後再開始搜索下一層。」
「因為我們把那些新生成的更長的密碼加到了列表的最後，所以我們會優先嘗試所有短密碼。」Frank突然補充道，「所以，你能做到這些嗎？」
「這恐怕不合適吧……」Socks回應道。
「拜託！有沒有搞錯啊。」Frank打斷道。
「這不就相當於一個開鎖的咒語嗎！」Socks說道。
「對。一點不錯！」Frank大聲叫道。
「算了，別管了。」Notation說道，用力地甩了甩手臂以表示自己的無奈，「要是他不想用咒語開鎖的話，我們對他大喊大叫也沒用。」她轉過身，仔細地研究著那至少有十英尺高的石牆。過了一會兒，她對Frank說道：「Frank，要是你抬我一下的話，我也許可以爬過去。」
Frank用懷疑的眼光看了看那堵石牆。和大多數城堡的石牆不同，這堵牆雖然已經廢棄多年，但並沒有出現可以幫助人攀爬的大的裂口和青籐。這做工簡直值得讚歎。從城牆頂上那錯落有致的精緻的尖刺可以看出，建這座牆的人一定也對自己的作品相當滿意。
「也許吧。不過這座牆真的挺高的。而且那些尖刺看起來也相當鋒利。」Frank說道。
「其實和在警察學校學的避開障礙那個項目沒什麼區別，」Notation說道，「不過這裡地面是硬的，沒有手可以抓住的地方，還有那些尖刺。」
「有了這些更刺激吧。」Frank說道。
「Frank，你快點閉嘴，來抬我一下。」
「算了算了，還是我來開鎖吧，」Socks急切地說道，「我就用廣度優先搜索咒語。不過我需要一個東西來寫那個列表。你們有一卷羊皮紙嗎？」
Frank和Notation對望了一眼，說道：「沒有，就在地上寫吧，反正足夠泥濘，可以看清楚了。
「哦，那好吧。」
幾分鐘後，門上的鎖開始發光。「開始了！」Socks說道。
門上的「確認」按鈕短暫地閃了一下，緊接著發出了一聲短暫的卡嚓聲。不過門依然是鎖著的。咒語剛剛嘗試了第一個可能的密碼——空密碼。緊接著，泥濘的地上出現了一列字母和數字：
1，2，3，A，B，C
Frank在頭腦中想像了一下這個選項列表所對應的搜索樹：
數字1隨即亮了起來，隨後「確認」按鈕也亮了起來。再一次，門發出了卡嚓一聲，但依然是鎖住的。地上的列表再一次變了，這次加入了搜索樹第三層的一些可能的密碼：
2，3，A，B，C
11，12，13，1A，1B，1C
但這些新的可能的密碼被加到了列表的最後，而搜索算法本身依然還在繼續嘗試第二層剩下的密碼。
密碼2也不對，列表再一次變長了：
3，A，B，C
11，12，13，1A，1B，1C
21，22，23，2A，2B，2C
再一次，搜索樹的最後一層延伸出了新的可能性。但搜索算法本身依然停留在第二層繼續嘗試，在嘗試完所有一位的密碼後才會進入到搜索樹的下一層。
換句話說，搜索算法在嘗試完當前層的所有可能密碼後，才會進入下一層。
搜索算法又嘗試了3、A、B、C這四個可能性，完成了整個搜索樹的第二層的嘗試。Socks這時說道：「這估計得花上一段時間了。」
Frank點了點頭，眼睛一動不動地盯著地上不斷變長的數字列表。「Notation，不如你去前面偵查一下吧？」
「好的，」她同意道，眼神中透出明顯的解脫。新手警察一般都不善於長時間地等待，畢竟警察學院也沒有辦法教你如何一動不動地坐上幾個小時。不過話說回來，聽學院裡Cloud教授的執法課其實也跟乾坐著差不多無聊了。
Notation走後五分鐘，鎖發出了一聲響亮的卡嚓聲。隨後，銹跡斑斑的大門隨著巨大的噪聲慢慢地打開了。隨著搜索算法順利完成，地上寫著的列表也漸漸消失掉了。
「1111。」Frank說道，他看起來一點都不驚訝。畢竟密碼必須設得足夠簡單，那些小嘍囉們才能記住。
他用棍子把密碼寫在了地上的一塊泥土上，又圍著它畫了兩個圈。再怎麼新手的警察也應該能看得出來這是留給她的消息。接著，他轉向Socks，說道：「我們走吧。」
警用算法導論：廣度優先搜索
節選自Drecker教授講義
廣度優先搜索是一個按順序依次嘗試可能的搜索選項的算法。換句話說，它每次都會選擇嘗試最先發現的但還沒有嘗試過的選項。
你可以想像一個列表（更具體地說，是一個隊列），上面存著所有已知的但還沒有嘗試過的狀態（選項）。每一步，算法都會選擇從當前隊列的第一個狀態開始進行嘗試。當發現新的可能性時，就將其加到隊列的最後，以確保算法在嘗試完所有先前已經發現的可能狀態後才會去嘗試這個新發現的狀態。
讓我們想像一下廣度優先搜索算法是怎麼搜索一個圖的。一個圖是一種由點和邊組成的數據結構。如果兩個點由一條邊相連，我們就可以說這兩個點是相鄰的。在警用算法課上你已經見識到了一個圖：Kingdom HighwayMap。這個圖裡的每個點代表一個城市，而每條邊則代表一條連接兩個城市的高速公路。罪犯們一般都傾向於逃離他們所在城市，而你則需要找出他們最可能逃到哪些相鄰的城市。
搜索Kingdom HighwayMap是一個經典的圖上搜索問題。我們搜索的狀態是圖上的點，也就是地圖上的城市。假設現在有人在A城市犯了罪，而你的目標是找到罪犯在哪。
廣度優先搜索會沿著一個不斷延伸的邊界展開。這個算法會先檢查所有離起點X步的點，然後才會繼續檢查離起點X+1步的點。當你檢查完A城市後，它的兩個相鄰城市B和D會被加到隊列的最後。此時的隊列中沒有別的城市了，所以接下來算法會檢查B城市。
如果每個點都有很多相鄰的點的話，維護這個隊列就會佔用大量的內存空間。在搜索一個大規模的問題時，這個內存需求會變得相當巨大。這時，作為警官的你就會打算多買一些質量好的筆記本。
在廣度優先搜索的每一步，我們都需要先看看當前的點是不是我們的最終目標。在這個具體的例子當中，我們需要把當前點對應的城市仔細搜查一遍，看看罪犯是不是藏在這個城市中。如果當前的點還不是我們想找的目標，就把與它相鄰的點中還未被檢查過的點（也就是我們之前從來沒有加到列表中的點）加到列表中。如此一來，我們可以避免重複添加已經檢查過的點，以及雖然還未檢查過但已經在列表裡的點。在這個具體的例子中，檢查過城市B後，我們將不會重複添加城市A（雖然它和B城市是相鄰的，但我們已經檢查過它了）。
請注意，如果我們想要檢查一個點在之前是否已經被添加過，將需要更多的內存，因為我們需要記錄下所有已經被加入過列表中的點。不過這樣做會給我們帶來巨大的好處——可以避免重複多次檢查同一個點。重申一遍，仔細地記錄下已經檢查過的點會給你帶來巨大的好處。
在這個具體的例子中，我們在H城市找到了要找的罪犯。至此我們可以在H城市逮捕他，結束搜索。
在搜索問題中，如果任意相鄰的兩個點之間移動的代價（例如所需的時間、體力，等等）是相等的，那麼廣度優先搜索可以保證找到一條花費最小代價的路徑。這是因為它在檢查完所有離起點距離X步的點後，才會開始檢查那些更遠的，例如離起點距離X+1步的點。
如果對於每個點都記下它是由哪一個點走來的，我們就可以很容易地追溯到這條最短路徑。我們只要從終點開始，不斷地回溯到它之前的一個點，直到回到起點就好了。
不過，值得注意的是，廣度優先搜索只有在相鄰點之間移動的代價都一樣時才會給出最優的方案。一般來說，找出兩點之間步數最少的路徑和找出兩點之間代價最小的路徑是不一樣的。舉個例子，如果一群遠足者想要盡量節省體力的話，他們寧願會走一條相對較長但可以避開山路的路，即使穿山而過可能會使整個路程更短，也會更有觀光價值，但走這段山路無疑會耗費更多的體力。
