說到搜索算法，它是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。搜索過程實際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的節(jié)點的過程。搜索算法在路徑規(guī)劃、行為決策、語句識別、語義分析等多個領(lǐng)域都發(fā)揮著非常重要的作用，下面會給大家做一些介紹，便于大家學(xué)習(xí)和理解。

一、搜索算法介紹

搜索算法就是窮舉出一個問題的部分或所有可能情況，從中找出求解方法。但是搜索相比于單純的枚舉算法有了一定的方向性和目標(biāo)性。搜索從解的所有可能中從一個狀態(tài)轉(zhuǎn)移到其他狀態(tài)（按照要求向解的方向拓展），這樣一直進(jìn)行下去，直到找到答案（目標(biāo)狀態(tài)）為止。

二、搜索分類

搜索分為廣度優(yōu)先搜索（BFS）與深度優(yōu)先搜索（DFS）

（1）廣度優(yōu)先搜索：

基本思想：從初始狀態(tài)S開始，利用規(guī)則，生成所有可能的狀態(tài)。構(gòu)成的下一層節(jié)點，檢查是否出現(xiàn)目標(biāo)狀態(tài)G，若未出現(xiàn)，就對該層所有狀態(tài)節(jié)點，分別順序利用規(guī)則。

生成再下一層的所有狀態(tài)節(jié)點，對這一層的所有狀態(tài)節(jié)點檢查是否出現(xiàn)G，若未出現(xiàn)，繼續(xù)按上面思想生成再下一層的所有狀態(tài)節(jié)點，這樣一層一層往下展開。直到出現(xiàn)目標(biāo)狀態(tài)為止?！诼窂降膶ふ覇栴}上用得比較多

這種思路可以用隊列來模擬該過程：

具體實現(xiàn)過程：

1. 每次取出隊列首元素（初始狀態(tài)），進(jìn)行拓展；

2. 然后把拓展所得到的可行狀態(tài)都放到隊列里面；

3. 將初始狀態(tài)刪除；

4. 一直進(jìn)行以上三步直到求出可行解或隊列為空。

（2）深度優(yōu)先搜索:（回溯法）

基本思想：從初始狀態(tài)，利用規(guī)則生成搜索樹下一層任一個結(jié)點，檢查是否出現(xiàn)目標(biāo)狀態(tài)，若未出現(xiàn)，以此狀態(tài)利用規(guī)則生成再下一層任一個結(jié)點，再檢查，重復(fù)過程一直到葉節(jié)點（即不能再生成新狀態(tài)節(jié)點），當(dāng)它仍不是目標(biāo)狀態(tài)時，回溯到上一層結(jié)果，取另一可能擴(kuò)展搜索的分支。采用相同辦法一直進(jìn)行下去，直到找到目標(biāo)狀態(tài)為止。

這種思路可以用棧來模擬該過程：

具體實現(xiàn)過程：

1. 次取出棧頂元素，對其進(jìn)行拓展。

2. 若棧頂元素?zé)o法繼續(xù)拓展，則將其從棧中彈出。繼續(xù)1過程。

3. 不斷重復(fù)直到獲得目標(biāo)狀態(tài)（取得可行解）或棧為空（無解）。