【概述】

深度優先搜索，是從初始狀態起，利用一定的規則生成搜索樹，尋找下一層任一個結點，檢查是否出現目標狀態，若未出現，以此狀態利用規則生成再下一層任一個結點，再檢查，重復過程一直到葉節點（即不能再生成新狀態節點），當它仍不是目標狀態時，回溯到上一層結果，取另一可能擴展搜索的分支。采用相同辦法一直進行下去，直到找到目標狀態為止。

狀態必須在遍歷完所有它的子狀態之后，才能繼續進行對同一層中下一個狀態的遍歷。

由于深度優先搜索是利用規則生成搜索樹實現的，其符合棧的先進后出的性質，因此當需要搜索最深處的結點時，利用深搜較為適合。

?

在搜索的過程中，由于搜索的低效無法很好的處理重疊子問題，動態規劃雖然較好的處理了重疊子問題但再一些具拓撲關系的題前較無奈，因此可采用記憶化搜索的方法，通過記憶化記錄每個狀態的搜索結果，在重復遍歷一個狀態時直接檢索并返回。

簡單地說就是：記憶化搜索=搜索的形式+動態規劃的思想

【具體過程】

從當前元素進行拓展

若元素無法繼續拓展，則將返回上層結點元素，繼續 1 過程

不斷重復，直到獲得目標狀態即取得可行解時，或者所有結點搜索完畢無解時，結束。

????

每個方塊表示一個狀態，淺藍色的表示遍歷了該狀態黑色代表當前探索的狀態，淺藍色為已經搜索過的狀態，灰色為未搜索的狀態。在過程中遇到搜索的解則退出，找到答案。

【實現】

void dfs(答案,搜索層數,其他參數){if(層數==maxdeep){更新答案;return; }(剪枝) for(枚舉下一層可能的狀態){更新全局變量表示狀態的變量;dfs(答案+新狀態增加的價值,層數+1,其他參數);還原全局變量表示狀態的變量;} }

【例題】

全排列（信息學奧賽一本通-T1199）：點擊這里

組合的輸出（信息學奧賽一本通-T1317）：點擊這里

八皇后（洛谷-P1219）：點擊這里

八皇后問題（信息學奧賽一本通-T1213）：點擊這里

八皇后（信息學奧賽一本通-T1214）：點擊這里

馬走日（信息學奧賽一本通-T1219）：點擊這里

放蘋果（信息學奧賽一本通-T1222）：點擊這里

滑雪（洛谷-P1434）：點擊這里
同題：滑雪（信息學奧賽一本通-T1280）：點擊這里

單詞接龍（洛谷-P1019）：點擊這里
同題：單詞接龍（信息學奧賽一本通-T1220）：點擊這里

單詞方陣（洛谷-P1101）：點擊這里

Cow Picnic（POJ-3256）：點擊這里

A strange lift（HDU-1548）：點擊這里

たくさんの數式 / Many Formulas（AtCoder-2067）：點擊這里

生日蛋糕（信息學奧賽一本通-T1441）：點擊這里

Birthday Puzzle（Gym-102267K）：點擊這里

自然數的拆分（信息學奧賽一本通-T1318）(遞歸輸出+dfs)：點擊這里

分成互質組（信息學奧賽一本通-T1221）(GCD+dfs)：點擊這里

Sudoku Killer（HDU-1426）(塊、行、列的依次判斷+dfs)：點擊這里

蟲食算（洛谷-P1092）(多情況劃分+dfs)：點擊這里

Another Eight Puzzle（HDU-2514）(多情況劃分+dfs)：點擊這里

蜥蜴與地下室（51Nod-1489）(數據預處理+dfs)：點擊這里

Divide by three, multiply by two（CF-977D）(構造+dfs)：點擊這里

Prime Ring（HDU-1016）(環形dfs+判素數)：點擊這里

The magic apple tree（HDU-3290）(樹上的dfs)：點擊這里

Brexit Negotiations（Kattis-Northwestern Europe Regional Contest (NWERC) 2018）(貪心+dfs)：點擊這里

處女座和小姐姐（二）（2019牛客寒假算法基礎集訓營 Day3-F）(雙向深搜)：點擊這里

Bitonix' Patrol（CF-217D）(bitset+dfs)：點擊這里

總結

以上是生活随笔為你收集整理的搜索 —— 深度优先搜索（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。