搜尋演算法
 |
在計算機科學中，搜索算法是解決搜索問題的任何算法，即檢索存儲在某個數據結構中的信息，或者在問題的可行域中計算的信息。這種結構的例子包括但不限於鍊表，數組或搜索樹。合適的搜索算法通常取決於正在搜索的數據結構，並且還可能包括有關數據的先前知識。搜索還包含查詢數據結構的算法，例如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） （英語）.