一些基礎搜尋算法的思想

ps：此部落格是蒟蒻寫的，可能并不是很正确。

再ps：該部落格長期施工。

搜尋

是暴力求解法的一種重要方法。就是通過不停的搜尋将部分（甚至所有）情況找出，然後選出題目中需要的最優解。

ps：因為搜尋算法好像沒什麼模闆可言，是以下面隻講思想（其實就是我懶）。

BFS

BFS，廣度優先搜尋，是按照廣度優先的一種搜尋方法。

思想

利用隊列，先把初始狀态入隊，然後每次取出隊首，用隊首搜尋出所有由隊首能夠一步到達的狀态并将之前沒有出現過的狀态入隊。隊列為空時，搜尋完畢。到達某狀态的步數就是該狀态的最優解。因為隻求最優解，是以不能搜尋出所有情況。

BFS正确的前提是上面說的“一步”全部相同，是以BFS不能求有不同邊權的最短路。而且BFS也不能走回之前的狀态。

效率

O(n) ，n表示狀态數。

DFS

DFS，深度優先搜尋，是按照深度優先的一種搜尋方法。

思想

利用棧（通常用系統棧，當然也可以用手工棧），從初始狀态開始不停遞歸，有沒走過的地方就去走（防止無限遞歸），這樣就可以搜尋出所有情況，但是不能在第一時間找到最優解（因為這麼走不滿足走到一處就一定是最優解）。

DFS必然是正确的（搜尋了所有狀态），但是狀态數可能非常大，是以效率不是很高。

效率

O(S) ，S表示情況數。

IDDFS

IDDFS，疊代加深搜尋，有種BFS和DFS結合的感覺。

思想

思想是很簡單的，IDDFS枚舉了一個深度depth，然後進行樸素DFS搜尋，但有一個限制，就是DFS深度不能超過depth，一旦超過depth就不繼續處理了。這樣處理的話，一旦目前depth驗證成功了，就不用繼續處理depth+1了（像BFS一樣立刻得到最優解）。IDDFS在答案大小不能完全确定，狀态數比較多（BFS隊列的空間複雜度為 O(n) ，n較大就扛不住了）的時候能發揮非常大的作用。

效率

玄學，但是由于depth最大為n，當depth小的時候DFS不會搜尋太多情況（遠小于S），是以效率還是很可觀的。

IDA*

IDA*，IDDFS+A*，感覺想法比A*簡單（雖然是IDDFS和A*的綜合）。

思想

還是枚舉深度depth，進行樸素IDDFS搜尋，但是和A*一樣，有估價函數（感覺估價函數到DFS裡就變成剪枝了:P），就是在目前狀态加上“最好”情況（這個“最好”情況通常不是實際最好情況），如果加上之後還不可能到達目标狀态，這條路肯定就走不通了。

效率

玄學，複雜度取決于估價函數的好壞。

A*

因為比較神奇，專門寫了一下，傳送門。

折半搜尋

因為比較神奇，專門寫了一下，傳送門。

雙向BFS

雙向BFS，顧名思義，是雙向的廣度優先搜尋。

思想

就是用兩個廣度優先搜尋，一個從起點開始，一個從終點開始，走到一起時搜尋完畢。

顯然BFS需要周遊到的格子是很多的。如果用雙向BFS，那麼就可以減少需要便利到的格子數。這看起來并沒有什麼很明顯的作用，因為效率還是 O(n) 的，但是實際上前面所說的 O(n) 忽略掉了一個“常數”X，也就是每次拓展的狀态數。當這個“常數”X比較大的時候，雙向BFS就會明顯展現出它的優勢。

效率

O(n) 。