前言

很多算法問題都可以用搜索解決：將所有可能的方案列出來，一一嘗試。雖然笨，但行之有效。比如170多年前的八皇后問題，大數學家高斯也曾回答錯誤，而今天即使一個入門程序員，都可以利用計算機的強大計算能力，獲得正確答案。

互聯網行業，程序員技術面試少不了算法題，算法反映的是程序員的內功。原始的搜索即“一一嘗試”，可能打敗100年前的數學家，但絕對不能通過今天的算法面試。

本文是作者刷完14道搜索相關算法題總結出來的, 希望對大家算法提升有幫助:

• 首先通過迷宮可視化動畫，引入深度優先搜索和廣度優先搜索兩種策略
• 接著分析何種情況下，採用哪種策略會更好，並指出在遍歷時要儘可能提前剪枝
• 然後給到三個具體案例
• 最後給到搜索算法總結和刷題建議

如何用搜索策略破解迷宮？

迷宮在遊戲領域中很常見，在《最強大腦》中的大型蜂巢迷宮道具也吸引了眾多眼球。談到迷宮，不得不提到搜索策略。

下面兩張圖，分別是小B和小D兩個人探索並走出同一迷宮的過程。其中左上角是迷宮起點，右下角是終點。

第一張圖中，小B遇到分叉路口後，會在每個路口都嘗試走一步，由內向外，像波紋一樣層層推進，是一種地毯式搜索，不放過遇到的任意一個路口。最後的綠色方格，表示重建出來的一條可行路徑。

第二張圖中，小D遇到分叉路口後，逐個嘗試，如果遇到死衚衕表示失敗，立即返回，返回的途徑用紅色標出來，表示此路不通。綠色表示當前可行的路徑。一直按上述的策略嘗試，直到找出一條路徑走出迷宮。有點孤軍深入的味道，運氣好的話，可很快走出迷宮，運氣差的話，可能之前走的某條路全部標紅，要全部放棄掉，重新嘗試其他路徑。

小B的全局指揮能力強，有點像《火影忍者》中的鳴人，利用影分身術，遇到分叉洛口，分身就變多，多個分身，按部就班，層層推進，最終只要一個分身走出迷宮，即完成任務。

小D的毅力很強，即使多次失敗，仍然不停嘗試。只有不怕失敗的人，靠毅力和記憶力（失敗路徑標紅）走出迷宮。

人生何嘗不是一座迷宮？每個人都在為自己的夢想奔波著。你才取哪種策略呢？像小B一樣穩妥的層層推進, 還是像小D一樣賭一把?

最短路徑問題: 應採用廣度優先搜索策略

廣度優先搜索(BFS)按照層次順序遍歷，想象一下將一個石子投入水中，波紋一圈一圈往外擴展的樣子。搜索過程中遇到的第一個解一定是距離起始位置最近的，所以第一個解，一定就是一個最優解，此時搜索算法可以終止。因此，廣度優先搜索可以用來求解最短路徑問題，當題目中出現

最短，最少的等字眼時，常用BFS來求解。比如：

• 完成任務所需的最少時間
• 輸出最少的變換步數

深度優先搜索搜索到的的解不一定是離起始位置最近的，只有將所有方案全局搜索完畢，即將所有的解決方案都試完，最優進一步比較，才能從所有解中找出最優的解。而BFS不需要搜索完，就能找到最短路徑。

故相對於深度優先搜索，廣度優先搜索適合解決最短路徑問題。

具體實現時，通常用藉助隊列這種數據結構來實現，廣度優先搜索偽代碼如下:

人生中的廣度優先有需要有全局觀，眼界開闊，按部就班，升職加薪，水到渠成，似乎指日可待。

連通性問題：應採用深度優先搜索策略

深度優先搜索(DFS)是一條路走到黑，走不通後，退回一步重試。

有點碰運氣的味道，快速試錯，快速迭代。所以找到的這條路不一定是最短路徑，不適合解決最短路徑問題。深度優先搜索，適合求解有沒有的問題(比如是否連通)或找出一個解的問題。當題目中出現是否、一個解等字眼時，通常用深度優先搜索求解。

一般而言，廣度優先搜索層層遍歷保存的信息較多，需要保存搜索過程中的狀態（通過一個隊列來記錄）；而深度優先搜索任意時刻，只需維護一條路徑的狀態，故從空間複雜度上說，深度優先搜索比廣度優先搜索有優勢。

在不需要找出最優解，只需一個解的時候，深度優先搜索比較合適。

深度優先搜索的核心邏輯:

• 遞歸下去：利用遞歸函數，深入搜索
• 回溯上來：不再滿足條件，停止遞歸調用，返回上一層調用

人生中的深度優先，會造就專家，比如談判專家、算法專家等, 都是在很多次的經驗教訓練出來的。

需要遍歷全部路徑的問題：DFS/BFS均可，但注意剪枝

當需要遍歷全部路徑時，DFS/BFS均可，個人覺得采用沒有明確的界限。但此時，因為需要遍歷所有路徑，需要一些技巧，來過濾掉沒有必要搜索的路徑，以提高搜索速度。

常用的技巧有:

• 記憶化搜索，將重複利用的結果記錄下來，下次用時直接取結果，而不是再次搜索
• 試探法: 限將當前節點放入路徑後，根據數據規律計算上下限，看結點是否滿足，儘可能提前預判路徑是否有效

總之，充分利用題目的限定條件，儘可能的提前結束掉路徑(即剪枝)。

正所謂: 小樹不修不直溜，人不修理哏赳赳。不要等長成大樹後再糾正，成本太高，要從小教育。

案例

八皇后問題

八皇后作為經典古老的問題，數學家高斯曾認為有76種方案，與真實答案92 相比漏掉了16種方案。

問題描述:

將八位皇后放在8ｘ8的棋盤上，要求任意兩皇后不能處於同一橫線、豎線、斜線上。否則，兩個皇后會打架。輸出方案數及前三種方案（字典序)

分析:

• 輸出方案總數，需要遍歷所有可能路徑。與最短路徑無關，用深度優先搜索

解決方案如下:

滑雪尋找最長滑坡問題

問題描述：

給定一個區域（二維數組），數組的值為該點的高度，找到最長滑坡長度。其中一個點可以從上下左右滑向相鄰的4個點之一。

分析:

• 搜索所有可能的滑坡，找到最大值; 跟最短路徑無關，採用深度優先搜索
• 利用記憶化搜索，剪枝：
• 即當某個點A作為起始點的最長滑坡已知時，滑坡B-A-End的A-END部分，直接取結果，而不用重複結算。

解決方案：

小結

注意上述兩個深度優先搜索案例中, 雖然均為深度優先搜索，但solve()函數中:

• 八皇后調用一次dfs()即可
• 而滑雪問題在兩重for循環中調用多次dfs()

原因如下:

• 八皇后: 相當於構造了一個哨兵根節點
• 滑雪問題: 無法構造哨兵根節點

參照下面的兩張圖理解：

象棋跳馬遍歷問題

問題描述:

給定nｘm的棋盤，和馬的座標，計算出馬到達棋盤任意一點最少要走多少步

分析:

• 看到“最少”字言，在進一步分析確定，可通過廣度優先搜索解決

解決方案:

總結

• 對於最短路徑問題，採用廣度優先搜索，層層推進
• 對於是否連通或找出一個解的問題，採用深度優先搜索，孤軍深入
• 對於遍歷全部路徑的問題, 深度優先或廣度優先搜索都可以，但注意剪枝，降低搜索複雜度，避免不必要的搜索。

最後，大家如果有人在刷題，留心下刷題攻略，建議：

• 不要走極端：一味的深度優先，雖然某專題上功力深厚，但技術面上會很窄；一味的廣度優先，深度上不夠
• 廣度、深度兩者要權衡好： 深度達到一定指標的情況下，廣度優先；廣度達到一定指標的情況下，深度優先
• 剩下的就是一次又一次的迭代和堅持，加深對算法的理解

• luogu 14道題目列表: p1032, p1126, p1141, p1162, p1143, p1092, p1019, p1101, p1219, p1605, p1118, P1434, p1433, p1074
• 《算法導論》第22章
• 《算法競賽入門經典》，第二版，第7章

題目列表