基本介紹
- 中文名：搜尋算法
- 外文名：search algorithm
- 領域：計算機定址或尋值
- 分類：枚舉、回溯、深(廣)度優先等
運算原理,主要分類,深度優先搜尋,廣度優先搜尋,雙向廣度優先搜尋,A*算法,散列函式,最佳化,套用案例,
運算原理
搜尋算法實際上是根據初始條件和擴展規則構造一棵“解答樹”並尋找符合目標狀態的節點的過程。所有的搜尋算法從最終的算法實現上來看，都可以劃分成兩個部分——控制結構（擴展節點的方式）和產生系統（擴展節點），而所有的算法最佳化和改進主要都是通過修改其控制結構來完成的。其實，在這樣的思考過程中，我們已經不知不覺地將一個具體的問題抽象成了一個圖論的模型——樹，即搜尋算法的使用第一步在於搜尋樹的建立。
搜尋樹模型
搜尋樹模型由圖一可以知道，這樣形成的一棵樹叫搜尋樹。初始狀態對應著根節點，目標狀態對應著目標結點。排在前的結點叫父結點，其後的結點叫子結點，同一層中的結點是兄弟結點，由父結點產生子結點叫擴展。完成搜尋的過程就是找到一條從根結點到目標結點的路徑，找出一個最優的解。這種搜尋算法的實現類似於圖或樹的遍歷，通常可以有兩種不同的實現方法，即深度優先搜尋（DFS——Depth First search）和廣度優先搜尋（BFS——Breadth First Search）。
主要分類
深度優先搜尋
如算法名稱那樣，深度優先搜尋所遵循的搜尋策略是儘可能“深”地搜尋樹。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前（子結點）探索，在探索過程中，一旦發現原來的選擇不符合要求，就回溯至父親結點重新選擇另一結點，繼續向前探索，如此反覆進行，直至求得最優解。深度優先搜尋的實現方式可以採用遞歸或者棧來實現。由此可見，把通常問題轉化為樹的問題是至關重要的一步，完成了樹的轉換基本完成了問題求解。
(1)減少節點數，思想：儘可能減少生成的節點數
(2)定製回溯邊界，思想：定製回溯邊界條件，剪掉不可能得到最優解的子樹
在很多情況下，我們已經找到了一組比較好的解。但是計算機仍然會義無返顧地去搜尋比它更“劣”的其他解，搜尋到後也只能回溯。為了避免出現這種情況，我們需要靈活地去定製回溯搜尋的邊界。
在深度優先搜尋的過程當中，往往有很多走不通的“死路”。假如我們把這些“死路”排除在外，不是可以節省很多的時間嗎？打一個比方，前面有一個路徑，別人已經提示：“這是死路，肯定不通”，而你的程式仍然很“執著”地要繼續朝這個方向走，走到頭來才發現，別人的提示是正確的。這樣，浪費了很多的時間。針對這種情況，我們可以把“死路”給標記一下不走，就可以得到更高的搜尋效率。
廣度優先搜尋
類似樹的按層遍歷，其過程為：首先訪問初始點Vi，並將其標記為已訪問過，接著訪問Vi的所有未被訪問過可到達的鄰接點Vi1、Vi2……Vit，並均標記為已訪問過，然後再按照Vi1、Vi2……Vit的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依此類推，直到圖中所有和初始點Vi有路徑相通的頂點都被訪問過為止。
遍歷方式 | 深度優先搜尋遍歷 | 廣度優先搜尋遍歷 |
所用數據結構 | 棧 | 佇列 |
一般最佳化 | 最優性剪枝 可行性剪枝 | Hash判重 雙向搜尋 |
雙向廣度優先搜尋
在廣度優先搜尋的基礎上進行最佳化，採用雙向搜尋的方式，即從起始節點向目標節點方向搜尋，同時從目標節點向起始節點方向搜尋。
特點：1.雙向搜尋只能用於廣度優先搜尋中。
2.雙向搜尋擴展的節點數量要比單向少的多。
A*算法
A*算法是利用問題的規則和特點來制定一些啟發規則，由此來改變節點的擴展順序，將最有希望擴展出最優解的節點優先擴展，使得儘快找到最優解。
對每一個節點，有一個估價函式F來估算起始節點經過該節點到達目標節點的最佳路徑的代價。
每個節點擴展的時候，總是選擇具有最小的F的節點。
F=G+B×H：G為從起始節點到當前節點的實際代價，已經算出，H為從該節點到目標節點的最優路徑的估計代價。F要單調遞增。
B最好隨著搜尋深度成反比變化，在搜尋深度淺的地方，主要讓搜尋依靠啟發信息，儘快的逼近目標，而當搜尋深的時候，逐漸變成廣度優先搜尋。
散列函式
散列函式（或散列算法，又稱哈希函式，英語：Hash Function）是一種從任何一種數據中創建小的數字“指紋”的方法。散列函式把訊息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函式將數據打亂混合，重新創建一個叫做散列值（hash values，hash codes，hash sums，或hashes）的指紋。散列值通常用一個短的隨機字母和數字組成的字元串來代表。好的散列函式在輸入域中很少出現散列衝突。在散列表和數據處理中，不抑制衝突來區別數據，會使得資料庫記錄更難找到。
Rabin-Karp字元串搜尋算法是一個相對快速的字元串搜尋算法，它所需要的平均搜尋時間是O(n).這個算法是創建在使用散列來比較字元串的基礎上的。
最佳化
利用回溯算法進行最佳化：回溯和深度優先相似，不同之處在於對一個節點擴展的時候，並不將所有的子節點擴展出來，而只擴展其中的一個。因而具有盲目性，但記憶體占用少。
在搜尋中的最佳化：1.在搜尋前，根據條件降低搜尋規模。2.廣度優先搜尋中，被處理過的節點，充分釋放空間。3.給據問題的約束條件進行剪枝。
在剪枝時應遵循以下原則：
(1)正確性：剪去的“枝條”不包含最優答案；
我們知道，剪枝方法之所以能夠最佳化程式的執行效率，是因為它能夠“剪去”搜尋樹中的一些“枝條”。然而，如果在剪枝的時候，將“長有”我們所需要的解的枝條也剪掉了，那么，一切最佳化也就都失去了意義。所以，對剪枝的第一個要求就是正確性，即必須保證不丟失正確的結果，這是剪枝最佳化的前提。
(2)準確性：在保證第一條原則的情況下，儘可能的剪去更多不包含最優答案的枝條；
在保證了正確性的基礎上，對剪枝判斷的第二個要求就是準確性，即能夠儘可能多的剪去不能通向正解的枝條。剪枝方法只有在具有了較高的準確性的時候，才能真正收到最佳化的效果。因此，準確性可以說是剪枝最佳化的生命。
(3)高效性：通過剪枝要能夠更快的接近到達最優解。
一般說來，設計好剪枝判斷方法之後，我們對搜尋樹的每個枝條都要執行一次判斷操作。然而，由於是利用出解的“必要條件”進行判斷，所以，必然有很多不含正解的枝條沒有被剪枝。這些情況下的剪枝判斷操作，對於程式的效率的提高無疑是具有副作用的。為了儘量減少剪枝判斷的副作用，我們除了要下功夫改善判斷的準確性外，經常還需要提高判斷操作本身的時間效率。
然而這就帶來了一個矛盾：我們為了加強最佳化的效果，就必須提高剪枝判斷的準確性，因此，常常不得不提高判斷操作的複雜度，也就同時降低了剪枝判斷的時間效率；但是，如果剪枝判斷的時間消耗過多，就有可能減小、甚至完全抵消提高判斷準確性所能帶來的最佳化效果，這恐怕也是得不償失。很多情況下，能否較好的解決這個矛盾，往往成為搜尋算法最佳化的關鍵。
套用案例
(1)題目：黑白棋遊戲
黑白棋遊戲的棋盤由4×4方格陣列構成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一种放置方案都構成一個遊戲狀態。在棋盤上擁有1條公共邊的2個方格稱為相鄰方格。一個方格最多可有4個相鄰方格。在玩黑白棋遊戲時，每一步可將任何2個相鄰方格中棋子互換位置。對於給定的初始遊戲狀態和目標遊戲狀態，編程計算從初始遊戲狀態變化到目標遊戲狀態的最短著棋序列。
(2)分析
這題我們可以想到用深度優先搜尋來做，但是如果下一步出現了以前的狀態怎么辦？直接判斷時間複雜度的可能會有點大，這題的最優解法是用廣度優先搜尋來做。我們就可以有初始狀態按照廣度優先搜尋遍歷來擴展每一個點，這樣到達目標狀態的步數一定是最優的（步數的增加時單調的）。但問題是如果出現了重複的情況我們就必須要判重，但是樸素的判重是可以達到狀態數級別的，其實我們可以考慮用hash表來判重。
Hash表：思路是根據關鍵碼值進行直接訪問。也就是說把一個關鍵碼值映射到表中的一個位置來訪問記錄的過程。在Hash表中，一般插入，查找的時間複雜度可以在O（1）的時間複雜度內搞定。對於這一題我們可以用二進制值表示其hash值，最多2^16次方，所以我們開個2^16次方的表記錄這個狀態出現沒有，這樣可以在O（1）的時間複雜度內解決判重問題。
進一步考慮：從初始狀態到目標狀態，必定會產生很多無用的狀態，那還有什麼最佳化可以減少這時間複雜度？我們可以考慮把初始狀態和目標狀態一起擴展，這樣如果初始狀態的某個被擴展的點與目標狀態所擴展的點相同時，那這兩個點不用擴展下去，而兩個擴展的步數和也就是答案。
上面的想法是雙向廣度優先搜尋：
就像圖二一樣，多擴展了很多不必要的狀態。
從上面一題可以看到我們用到了兩種最佳化方法，即Hash表最佳化和雙向廣搜最佳化。一般的廣度優先搜尋用這兩個最佳化就足以解決。
