搜尋

在人工智慧中，搜尋問題一般包括兩個重要的問題：

1. 搜尋什麼：通常指目標
2. 在哪裡搜尋：即搜尋空間，通常指一系列狀態的匯集，因此也稱為狀態空間

搜尋方式

按是否使用啟發式資訊分

• 啟發式搜尋
• 盲目搜尋

按問題的表示方式分

• 狀態空間搜尋
• 與/或樹搜尋

搜尋策略

寬度優先搜尋

寬度優先搜尋演算法是沿著樹的寬度遍歷樹的節點，如果發現目標，則演算法中止。屬於盲目搜尋。

深度優先搜尋

深度優先搜尋沿著樹的最大深度方向生成節點並與目標節點進行比較，只有當上次訪問的節點不是目標節點，而且沒有其他節點可以生成的時候，才轉到上次訪問節點的父節點，然後搜尋該節點的其他子節點。因此深度優先搜尋也稱為回溯搜尋。它既不是完備的，也不是最佳的。有時候，某些特定的問題會產生大量重複的節點。例如「八數位」問題就是這樣的，當每次運用向上、向下、向左、向右移動空格的算符時，可能產生與已經產生的節點重複的節點。當再次搜尋到這個重複節點時，由於應用的算符基本一致，還會產生重複，所以為了節約時間和儲存空間，往往在深度優先演算法中設立一個機制，用來刪除這些重複的節點，以提高效率。

迭代加深搜尋（ID搜尋）

對深度優先搜尋進行了一定改進，對搜尋樹的深度進行控制，即有界深度優先搜尋。

在程式找到目標之前，通過迭代不斷增大以保證完備性和最佳性。雖然會有不少重複搜尋，但是鑑於每增加一次d，則搜尋的時間複雜度會以指數級別增加，所以重複搜尋的時間可以忽略，亦可以與A*演算法結合（即IDA*搜尋演算法）來剪枝。

迭代加深搜尋通常用於那種搜尋樹又深又寬、但是解並不是很深的情況，這時廣度優先搜尋會超空間，而深度優先搜尋會逾時。這時迭代加深搜尋很有用，可是說是在用遞迴方法在實現廣度優先搜尋。

啟發式OR圖搜尋演算法

• 爬山演算法
• 類比退火演算法
• 最好優先
• 通用圖
• A*

AND-OR圖啟發式搜尋

一個特殊問題：博弈論

約束滿足搜尋

搜尋策略還可以指在使用搜尋引擎中所使用的策略，它通常是搜尋之母，一個好的搜尋過程必定有一個好的搜尋策略來支援。

評價準則

• 完備性
• 時間複雜性
• 空間複雜性
• 最佳性