搜尋演算法

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

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

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

對於虛擬搜索空間

主條目：Solver

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

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

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

對於給定結構的子結構

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

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

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

搜索功能的最大值

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

對於量子計算機

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