第1章　搜索

引言

搜索是人工智能的一個關鍵領域。人工智能所面臨的許多問題都非常復雜，往往無法一步完成，而是需要通過一組動作（action）序列來達到目標（goal）。這個尋找達到目標的動作序列的求解過程，就稱為搜索。解決搜索問題的方法稱為搜索策略，其主要任務是確定選取動作的方式和順序。

現實中許多規劃問題都可以描述成搜索問題，且都已得到很好的解決。如圖1.1所示，自動駕駛或導航系統中的路徑規劃以及使機器人完成抓取任務的運動規劃，就是典型的搜索問題。許多智力游戲的求解，比如尋找魔方的復原方法，本質也是搜索問題。還有，擊敗前國際象棋冠軍卡斯帕羅夫的深藍程序，以及擊敗世界圍棋冠軍李世石的谷歌Deep Mind AlphaGo，它們的核心也都是搜索算法。

圖1.1　常見的搜索問題

在本章中將介紹兩大類搜索算法：單智能體（single-agent）搜索和多智能體（multi-agent）對抗搜索（adversarial search）。

單智能體搜索針對在單個智能體環境中的決策問題。即使有其他智能體存在，這類搜索也只是簡單地把它們的行為視為環境的一部分。前面例子中的自動駕駛與導航路徑規劃以及機器人抓取規劃均為單智能體搜索。單智能體的搜索策略有兩種基本方式。一種是盲目搜索，也稱為無信息搜索策略，即不考慮除問題定義本身之外的知識，根據事先確定好的某種固定排序，依次調用動作，以探求最優的動作序列。另一種是啟發式搜索，或稱為有信息引導的搜索策略，即考慮具體問題的可用知識，有目的地動態確定排序的規則，優先搜索最可能的動作，從而加快搜索速度。

多智能體對抗搜索主要針對存在多個智能體競爭的環境。此時，每一個智能體都需要考慮其他智能體的決策帶來的影響，因而導致了博弈問題和對抗搜索的產生。對抗搜索算法在每一步中尋找在對手最優選擇下使己方收益最大化的步驟，并不斷迭代，直到最終找到雙方策略的均衡點。在均衡點，雙方都無法通過改變自己的策略來提高收益。在對抗搜索中，可以通過剪枝來避免搜索必然不優的策略，從而提高效率。

在本章中，首先介紹單智能體搜索問題的定義，然后詳細介紹盲目搜索和啟發式搜索兩種主要的方法；隨后，將介紹多智能體對抗搜索。為方便讀者理解，我們會穿插介紹一些必要的數據結構知識及例子。