搜尋演算法

在電腦科學中，搜尋演算法是解決搜尋問題的任何演算法，即檢索儲存在某個數據結構中的資訊，或者在問題域的搜尋空間中計算的資訊。這種結構的例子包括但不限於鏈結串列，陣列數據結構或搜尋樹。合適的搜尋演算法通常取決於正在搜尋的數據結構，並且還可能包括有關數據的先前知識。搜尋還包含查詢數據結構的演算法，例如SQL SELECT命令。

搜尋演算法可以根據搜尋機制進行分類。線性搜尋演算法以線性方式檢查每個與目標關鍵字關聯的記錄。二進制或半間隔搜尋，重複定位搜尋結構的中心，並將搜尋空間分成兩半。比較搜尋演算法通過基於鍵的比較相繼地消除記錄來改進線性搜尋，直到找到目標記錄為止，並且可以按照定義的順序應用於數據結構。數字搜尋演算法基於使用數字鍵的數據結構中的數字屬性工作。最後，雜湊根據雜湊函數直接將鍵對映到記錄。線上性搜尋之外進行搜尋需要以某種方式對數據進行排序。

搜尋功能也根據其複雜性或最大理論執行時間進行評估。例如，二進制搜尋函數的最大複雜度為${\mathsf {O}}\log({\text{n}})$或對數時間。這意味着尋找搜尋目標所需的最大操作次數是搜尋空間大小的對數函數。

對於虛擬搜尋空間

主條目：Solver

在約束滿足問題中使用搜尋虛擬空間的演算法，其目標是找到一組賦值給某些變數的值賦值，以滿足特定的數學方程和不等式 。當目標是找到一個可以最大化或最小化這些變數的某個函數的變數賦值時，也會使用它們。針對這些問題的演算法包括基本的強力搜尋（也稱為「天真」或「非資訊」搜尋）以及嘗試利用關於該空間結構的部分知識的各種啟發式演算法，如線性鬆弛，約束生成，和約束傳播。

一個重要的子類是局部搜尋方法，它將搜尋空間的元素視為圖的頂點，其邊由適用於該案例的一組啟發法定義; 並且通過沿着邊緣從物品移動到物品來掃描空間，例如根據最速下降或最佳優先標準，或者在隨機搜尋中。這一類包括各種通用的啟發式方法，如模擬退火，禁忌搜尋，A-團隊和遺傳編程，它們以特定的方式結合了任意的啟發式方法。該類還包括各種樹搜尋演算法，將元素視為樹的頂點，並以某種特定順序遍歷樹。後者的例子包括深度優先搜尋和廣度優先搜尋等詳盡的方法，以及各種基於啟發式的搜尋樹修剪方法，如回溯和分支定界。與一般的metaheuristics不同，後者至多只能以概率的方式工作，如果給予足夠的時間，許多這些樹搜尋方法都能保證找到確切的或最佳的解決方案。這被稱為「 完整性 」。

另一個重要的子類包括用於探索多玩家遊戲（例如國際象棋或西洋雙陸棋）的遊戲樹的演算法，其中節點包括可能由當前情況導致的所有可能的遊戲情況。這些問題的目標是找到提供最佳贏球機會的舉措，同時考慮到對手的所有可能舉措。當人類或機器必須作出連續的決定，其結果不完全在其控制之下時，例如在機械人指導或行銷，財務或軍事戰略規劃中，就會出現類似的問題。這種問題 - 組合搜尋- 在人工智能的背景下進行了廣泛的研究。這個類的演算法的例子是極小極大演算法，alpha-beta修剪，*資訊搜尋和A *演算法。

對於給定結構的子結構

名稱「組合搜尋」通常用於尋找給定離散結構的特定子結構的演算法，例如圖形，字串，有限組等。術語組合最佳化通常用於當目標是找到具有某個參數的最大值（或最小值）的子結構時。（由於子結構通常在電腦中用一組帶有約束的整數變數來表示，所以這些問題可以看作是約束滿足或離散最佳化的特例;但它們通常是在一個更抽象的情況下制定和解決的，內部表示沒有明確提及。）

一個重要且廣泛研究的子類是圖演算法，特別是圖遍歷演算法，用於尋找給定圖中的特定子結構 - 例如子圖，路徑，電路等。例子包括Dijkstra演算法，Kruskal演算法，最近鄰演算法和Prim演算法。

這個類別的另一個重要子類是字串搜尋演算法，它搜尋字串內的模式。兩個着名的例子是Boyer-Moore和Knuth-Morris-Pratt演算法，以及一些基於字尾樹數據結構的演算法。

搜尋功能的最大值

1953年，美國統計學家傑克基弗設計了斐波納契搜尋，它可以用來找到單峰函數的最大值，並且在電腦科學中有很多其他應用。

對於量子電腦

還有為量子電腦設計的搜尋方法，如Grover演算法，即使沒有數據結構或啟發式的幫助，它在理論上也比線性或強力搜尋更快。