第1章　搜索

引言

搜索是人工智能的一个关键领域。人工智能所面临的许多问题都非常复杂，往往无法一步完成，而是需要通过一组动作（action）序列来达到目标（goal）。这个寻找达到目标的动作序列的求解过程，就称为搜索。解决搜索问题的方法称为搜索策略，其主要任务是确定选取动作的方式和顺序。

现实中许多规划问题都可以描述成搜索问题，且都已得到很好的解决。如图1.1所示，自动驾驶或导航系统中的路径规划以及使机器人完成抓取任务的运动规划，就是典型的搜索问题。许多智力游戏的求解，比如寻找魔方的复原方法，本质也是搜索问题。还有，击败前国际象棋冠军卡斯帕罗夫的深蓝程序，以及击败世界围棋冠军李世石的谷歌Deep Mind AlphaGo，它们的核心也都是搜索算法。

图1.1　常见的搜索问题

在本章中将介绍两大类搜索算法：单智能体（single-agent）搜索和多智能体（multi-agent）对抗搜索（adversarial search）。

单智能体搜索针对在单个智能体环境中的决策问题。即使有其他智能体存在，这类搜索也只是简单地把它们的行为视为环境的一部分。前面例子中的自动驾驶与导航路径规划以及机器人抓取规划均为单智能体搜索。单智能体的搜索策略有两种基本方式。一种是盲目搜索，也称为无信息搜索策略，即不考虑除问题定义本身之外的知识，根据事先确定好的某种固定排序，依次调用动作，以探求最优的动作序列。另一种是启发式搜索，或称为有信息引导的搜索策略，即考虑具体问题的可用知识，有目的地动态确定排序的规则，优先搜索最可能的动作，从而加快搜索速度。

多智能体对抗搜索主要针对存在多个智能体竞争的环境。此时，每一个智能体都需要考虑其他智能体的决策带来的影响，因而导致了博弈问题和对抗搜索的产生。对抗搜索算法在每一步中寻找在对手最优选择下使己方收益最大化的步骤，并不断迭代，直到最终找到双方策略的均衡点。在均衡点，双方都无法通过改变自己的策略来提高收益。在对抗搜索中，可以通过剪枝来避免搜索必然不优的策略，从而提高效率。

在本章中，首先介绍单智能体搜索问题的定义，然后详细介绍盲目搜索和启发式搜索两种主要的方法；随后，将介绍多智能体对抗搜索。为方便读者理解，我们会穿插介绍一些必要的数据结构知识及例子。