深度優先搜索

出自 MBA智库百科(https://wiki.mbalib.com/)

　　深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇後，被鏈接的HTML文件將執行深度優先搜索，即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束。

　　深度優先遍歷圖的方法是，從圖中某頂點v出發：

　　（1）訪問頂點v；

　　（2）依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；

　　（3）若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。　當然，當人們剛剛掌握深度優先搜索的時候常常用它來走迷宮.事實上我們還有別的方法，那就是廣度優先搜索(BFS)。

　　在我們遇到的一些問題當中，有些問題我們不能夠確切的找出數學模型，即找不出一種直接求解的方法，解決這一類問題，我們一般採用搜索的方法解決。搜索就是用問題的所有可能去試探，按照一定的順序、規則，不斷去試探，直到找到問題的解，試完了也沒有找到解，那就是無解，試探時一定要試探完所有的情況（實際上就是窮舉）；

　　對於問題的第一個狀態，叫初始狀態，要求的狀態叫目標狀態。

　　搜索就是把規則應用於實始狀態，在其產生的狀態中，直到得到一個目標狀態為止。

　　產生新的狀態的過程叫擴展（由一個狀態，應用規則，產生新狀態的過程）

　　搜索的要點：

　　（1）初始狀態；

　　（2）重覆產生新狀態；

　　（3）檢查新狀態是否為目標，是結束，否轉（2）；

　　如果搜索是以接近起始狀態的程式依次擴展狀態的，叫寬度優先搜索。

　　如果擴展是首先擴展新產生的狀態，則叫深度優先搜索。

　　深度優先搜索

　　深度優先搜索用一個數組存放產生的所有狀態。

　　（1）把初始狀態放入數組中，設為當前狀態；

　　（2）擴展當前的狀態，產生一個新的狀態放入數組中，同時把新產生的狀態設為當前狀態；

　　（3）判斷當前狀態是否和前面的重覆，如果重覆則回到上一個狀態，產生它的另一狀態；

　　（4）判斷當前狀態是否為目標狀態，如果是目標，則找到一個解答，結束演算法。

　　（5）如果數組為空，說明無解。

　　對於pascal語言來講，它支持遞歸，在遞歸時可以自動實現回溯（利用局部變數）所以使用遞歸編寫深度優先搜索程式相對簡單，當然也有非遞歸實現的演算法。

　　搜索是人工智慧中的一種基本方法，是一項非常普遍使用的演算法策略，能夠解決許許多多的常見問題，在某些情況下我們很難想到高效的解法時，搜索往往是可選的唯一選擇。按照標準的話來講：搜索演算法是利用電腦的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。

　　搜索雖然簡單易學易於理解，但要掌握好並寫出速度快效率高優化好的程式卻又相當困難，總而言之，搜索演算法靈活多變，一般的框架很容易寫出，但合適的優化卻要根據實際情況來確定。在搜索演算法中，深度優先搜索（也可以稱為回溯法）是搜索演算法里最簡單也最常見的，今天我們就從這裡講起，下麵的內容假設讀者已經知道最基本的程式設計和簡單的遞歸演算法。

　　所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。

　　我們將所要解答的問題劃分成若幹個階段或者步驟，當一個階段計算完畢，下麵往往有多種可選選擇，所有的選擇共同組成了問題的解空間，對搜索演算法而言，將所有的階段或步驟畫出來就類似是樹的結構（如圖）。

　　從根開始計算，到找到位於某個節點的解，回溯法（深度優先搜索）作為最基本的搜索演算法，其採用了一種“一隻向下走，走不通就掉頭”的思想（體會“回溯”二字），相當於採用了先根遍歷的方法來構造搜索樹。

　　上面的話可能難於理解，沒關係，我們通過基本框架和例子來闡述這個演算法，你會發現其中的原理非常簡單自然。