text: 在計算機科學中，搜尋演算法是解決搜尋問題的任何演算法，即檢索儲存在某個資料結構中的資訊，或者在問題域的搜尋空間中計算的資訊。這種結構的例子包括但不限於連結串列，陣列資料結構或搜尋樹。合適的搜尋演算法通常取決於正在搜尋的資料結構，並且還可能包括有關資料的先前知識。搜尋還包含查詢資料結構的演算法，例如SQL SELECT命令。搜尋演算法可以根據搜尋機制進行分類。線性搜尋演算法以線性方式檢查每個與目標關鍵字關聯的記錄。二進位制或半間隔搜尋，重複定位搜尋結構的中心，並將搜尋空間分成兩半。比較搜尋演算法透過基於鍵的比較相繼地消除記錄來改進線性搜尋，直到找到目標記錄為止，並且可以按照定義的順序應用於資料結構。數字搜尋演算法基於使用數字鍵的資料結構中的數字屬性工作。最後，雜湊根據雜湊函式直接將鍵對映到記錄。線上性搜尋之外進行搜尋需要以某種方式對資料進行排序。搜尋功能也根據其複雜性或最大理論執行時間進行評估。例如，二進位制搜尋函式的最大複雜度為formula_1或對數時間。這意味著查詢搜尋目標所需的最大操作次數是搜尋空間大小的對數函式。對於虛擬搜尋空間.在約束滿足問題中使用搜索虛擬空間的演算法，其目標是找到一組賦值給某些變數的值賦值，以滿足特定的數學方程和不等式 。當目標是找到一個可以最大化或最小化這些變數的某個函式的變數賦值時，也會使用它們。針對這些問題的演算法包括基本的強力搜尋以及嘗試利用關於該空間結構的部分知識的各種啟發式演算法，如線性鬆弛，約束生成，和約束傳播。一個重要的子類是區域性搜尋方法，它將搜尋空間的元素視為圖的頂點，其邊由適用於該案例的一組啟發法定義; 並且透過沿著邊緣從物品移動到物品來掃描空間，例如根據最速下降或最佳優先標準，或者在隨機搜尋中。這一類包括各種通用的啟發式方法，如模擬退火，禁忌搜尋，A-團隊和遺傳程式設計，它們以特定的方式結合了任意的啟發式方法。該類還包括各種樹搜尋演算法，將元素視為樹的頂點，並以某種特定順序遍歷樹。後者的例子包括深度優先搜尋和廣度優先搜尋等詳盡的方法，以及各種基於啟發式的搜尋樹修剪方法，如回溯和分支定界。與一般的metaheuristics不同，後者至多隻能以機率的方式工作，如果給予足夠的時間，許多這些樹搜尋方法都能保證找到確切的或最優的解決方案。這被稱為“ 完整性 ”。另一個重要的子類包括用於探索多玩家遊戲的遊戲樹的演算法，其中節點包括可能由當前情況導致的所有可能的遊戲情況。這些問題的目標是找到提供最佳贏球機會的舉措，同時考慮到對手的所有可能舉措。當人類或機器必須作出連續的決定，其結果不完全在其控制之下時，例如在機器人指導或營銷，財務或軍事戰略規劃中，就會出現類似的問題。這種問題 - 組合搜尋- 在人工智慧的背景下進行了廣泛的研究。這個類的演算法的例子是極小極大演算法，alpha-beta修剪，*資訊搜尋和A *演算法。對於給定結構的子結構.名稱“組合搜尋”通常用於查詢給定離散結構的特定子結構的演算法，例如圖形，字串，有限組等。術語組合最佳化通常用於當目標是找到具有某個引數的最大值一個重要且廣泛研究的子類是圖演算法，特別是圖遍歷演算法，用於查詢給定圖中的特定子結構 - 例如子圖，路徑，電路等。例子包括Dijkstra演算法，Kruskal演算法，最近鄰演算法和Prim演算法。這個類別的另一個重要子類是字串搜尋演算法，它搜尋字串內的模式。兩個著名的例子是Boyer-Moore和Knuth-Morris-Pratt演算法，以及一些基於字尾樹資料結構的演算法。搜尋功能的最大值.1953年，美國統計學家傑克基弗設計了斐波納契搜尋，它可以用來找到單峰函式的最大值，並且在計算機科學中有很多其他應用。對於量子計算機.還有為量子計算機設計的搜尋方法，如Grover演算法，即使沒有資料結構或啟發式的幫助，它在理論上也比線性或強力搜尋更快。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 搜尋演算法
metadata: https://zh.wikipedia.org/wiki?curid=6097630