搜尋

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

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

搜索方式

按是否使用啟發式信息分

• 啟發式搜索
• 盲目搜索

按問題的表示方式分

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

搜索策略

寬度優先搜索

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

深度優先搜索

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

迭代加深搜索（ID搜索）

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

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

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

啟發式OR圖搜索算法

• 爬山算法
• 模擬退火算法
• 最好優先
• 通用圖
• A*

AND-OR圖啟發式搜索

一個特殊問題：博弈論

約束滿足搜索

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

評價準則

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