搜尋演算法
 |
在電腦科學中，搜尋演算法是解決搜尋問題的任何演算法，即檢索儲存在某個資料結構中的資訊，或者在問題的可行域中計算的資訊。這種結構的例子包括但不限於鏈結串列，陣列或搜尋樹。合適的搜尋演算法通常取決於正在搜尋的資料結構，並且還可能包括有關資料的先前知識。搜尋還包含查詢資料結構的演算法，例如SQL SELECT命令[1]。
搜尋演算法可以根據搜尋機制進行分類。線性搜尋演算法以線性方式檢查每個與目標關鍵字關聯的記錄。二分或折半搜尋（二分尋找演算法）重複定位搜尋結構的中心，並將搜尋空間分成兩半。比較搜尋演算法通過基於鍵的比較相繼地消除記錄來改進線性搜尋，直到找到目標記錄為止，並且可以按照定義的順序應用於資料結構。數字搜尋演算法基於使用數字鍵的資料結構中的數字屬性工作。最後，雜湊根據雜湊函式直接將鍵對映到記錄。線上性搜尋之外進行搜尋需要以某種方式對資料進行排序。此外，使用了啟發式資訊的方法稱為啟發式搜尋。
搜尋功能常根據其複雜性或最大理論執行時間進行評估。例如，二分尋找演算法的最大複雜度為，即對數時間複雜度，這意味著尋找搜尋目標所需的最大操作次數是搜尋空間大小的對數函式。其它評估方式包括完備性、空間複雜性、最佳性。
應用
[編輯]搜尋演算法的具體應用包括：
- 組合最佳化中的問題，例如：
- 約束滿足問題，例如：
- 在博弈論中，尤其是組合博弈論中，選擇下一步的最佳行動（例如極小化極大演算法）
- 從一整套可能性中找到組合或密碼
- 整數的因子分解（密碼學中的一個重要問題）
- 搜尋引擎最佳化（SEO）和網路爬蟲的內容最佳化
- 通過改變工藝參數（如溫度、壓力和pH）來最佳化包括如化學反應在內的工業工藝
- 從資料庫中檢索記錄
- 在列表或陣列中尋找最大值或最小值
- 檢查給定值是否存在於一組值中
搜尋策略
[編輯]寬度優先搜尋演算法是沿著樹的寬度遍歷樹的節點，如果發現目標，則演算法中止。屬於盲目搜尋。
深度優先搜尋沿著樹的最大深度方向生成節點並與目標節點進行比較，只有當上次訪問的節點不是目標節點，而且沒有其他節點可以生成的時候，才轉到上次訪問節點的父節點，然後搜尋該節點的其他子節點。因此深度優先搜尋也稱為回溯搜尋。它既不是完備的，也不是最佳的。有時候，某些特定的問題會產生大量重複的節點。例如「八數位」問題就是這樣的，當每次運用向上、向下、向左、向右移動空格的算符時，可能產生與已經產生的節點重複的節點。當再次搜尋到這個重複節點時，由於應用的算符基本一致，還會產生重複，所以為了節約時間和儲存空間，往往在深度優先演算法中設立一個機制，用來刪除這些重複的節點，以提高效率。
對深度優先搜尋進行了一定改進，對搜尋樹的深度進行控制，即有界深度優先搜尋。
在程式找到目標之前，通過迭代不斷增大以保證完備性和最佳性。雖然會有不少重複搜尋，但是鑑於每增加一次d，則搜尋的時間複雜度會以指數級別增加，所以重複搜尋的時間可以忽略，亦可以與A*演算法結合（即IDA*搜尋演算法）來剪枝。
迭代加深搜尋通常用於那種搜尋樹又深又寬、但是解並不是很深的情況，這時廣度優先搜尋會超空間，而深度優先搜尋會逾時。這時迭代加深搜尋很有用，可是說是在用遞迴方法在實現廣度優先搜尋。
啟發式OR圖搜尋演算法
[編輯]AND-OR圖啟發式搜尋
[編輯]一個特殊問題：博弈論
約束滿足搜尋
[編輯]搜尋策略還可以指在使用搜尋引擎中所使用的策略，它通常是搜尋之母，一個好的搜尋過程必定有一個好的搜尋策略來支援。
分類
[編輯]對於虛擬搜尋空間
[編輯]求解器在約束滿足問題中使用搜尋虛擬空間的演算法，其目標是找到一組賦值給某些變數的值賦值，以滿足特定的數學方程和不等式。當目標是找到一個可以最大化或最小化這些變數的某個函式的變數賦值時，也會使用它們。針對這些問題的演算法包括基本的強力搜尋（也稱為「天真」或「非資訊」搜尋）以及嘗試利用關於該空間結構的部分知識的各種啟發式演算法，如線性鬆弛，約束生成，和約束傳播。
一個重要的子類是局部搜尋方法，它將搜尋空間的元素視為圖的頂點，其邊由適用於該案例的一組啟發法定義; 並且通過沿著邊緣從物品移動到物品來掃描空間，例如根據最速下降或最佳優先標準，或者在隨機搜尋中。這一類包括各種通用的啟發式方法，如類比退火，禁忌搜尋，A-團隊和遺傳編程，它們以特定的方式結合了任意的啟發式方法。該類還包括各種樹搜尋演算法，將元素視為樹的頂點，並以某種特定順序遍歷樹。後者的例子包括深度優先搜尋和廣度優先搜尋等詳盡的方法，以及各種基於啟發式的搜尋樹修剪方法，如回溯和分支定界。與一般的metaheuristics不同，後者至多只能以概率的方式工作，如果給予足夠的時間，許多這些樹搜尋方法都能保證找到確切的或最佳的解決方案。這被稱為「 完整性 」。
另一個重要的子類包括用於探索多玩家遊戲（例如西洋棋或西洋雙陸棋）的遊戲樹的演算法，其中節點包括可能由當前情況導致的所有可能的遊戲情況。這些問題的目標是找到提供最佳贏球機會的舉措，同時考慮到對手的所有可能舉措。當人類或機器必須作出連續的決定，其結果不完全在其控制之下時，例如在機器人指導或行銷，財務或軍事戰略規劃中，就會出現類似的問題。這種問題 - 組合搜尋- 在人工智慧的背景下進行了廣泛的研究。這個類的演算法的例子是極小極大演算法，alpha-beta修剪，*資訊搜尋和A *演算法。
對於給定結構的子結構
[編輯]名稱「組合搜尋」通常用於尋找給定離散結構的特定子結構的演算法，例如圖形，字串，有限組等。術語組合最佳化通常用於當目標是找到具有某個參數的最大值（或最小值）的子結構時。（由於子結構通常在電腦中用一組帶有約束的整數變數來表示，所以這些問題可以看作是約束滿足或離散最佳化的特例;但它們通常是在一個更抽象的情況下制定和解決的，內部表示沒有明確提及。）
一個重要且廣泛研究的子類是圖演算法，特別是圖遍歷演算法，用於尋找給定圖中的特定子結構 - 例如子圖，路徑，電路等。例子包括Dijkstra演算法，Kruskal演算法，最近鄰演算法和Prim演算法。
這個類別的另一個重要子類是字串搜尋演算法，它搜尋字串內的模式。兩個著名的例子是Boyer-Moore和Knuth-Morris-Pratt演算法，以及一些基於字尾樹資料結構的演算法。
對於量子電腦
[編輯]還有為量子電腦設計的搜尋方法，如Grover演算法，即使沒有資料結構或啟發式的幫助，它在理論上也比線性或強力搜尋更快。
參照
[編輯]- ^ Shares, 1 7k. How Search Engine Algorithms Work: Everything You Need to Know. Search Engine Journal. [2022-05-05]. （原始內容存檔於2022-06-11） （英語）.