1.1　搜索问题的定义

一个搜索问题可以由6个组成部分<S，s₀，A，T，c，G>来形式化描述：

·　S：状态空间（state space），是所有可能的状态集合，而状态（state）表示问题中考虑系统所处的状态；

·　s₀：初始状态（initial state），描述系统的起始状态；

·　A：动作空间（action space），对于每个状态s，A（s）描述在该状态下可用的动作集合；

·　T（s，a）：转移函数（transition function），在状态s下执行动作a后达到的状态；

·　c（s，a，s'）：损耗函数（cost function），在状态s下执行动作a后达到的状态s'的损耗；

·　G（s）：目标测试函数（goal test），判断给定的状态s是否为目标状态。值得注意的是对于有些问题，目标状态s是一个集合，而不是单个状态。搜索在系统到达其中一个目标状态后结束。

将系统从初始状态带到目标状态的一系列动作称为一个解。解的好坏由路径上的总损耗来度量，其中取得最小总损耗的解称为最优解。在本章中，假定转移函数为确定性的，即在一个状态下，执行某个动作之后会确定性地到达另一个状态，不存在随机性。对于存在随机性的复杂问题，需要将问题建模成为一个马尔可夫决策过程（Markov decision process），相关内容会在第8章进行介绍。

接下来，我们举两个例子。

第一个例子是图1.2中展示的一个常见的八数字推盘游戏。在一个3×3的木板上，有编号为1~8的图块和一个空白区域，与空白区域相邻的图块可以被推入空白区域。我们的目标是从初始布局（左），通过移动图块达到指定的目标布局（右）。对于这个游戏，我们难以利用现有的信息直接计算出问题的解，而必须通过搜索，逐步找到能够达成目标的路径。在这个问题里，每个解均为一系列的数字移动动作。

对于这个八数字推盘问题，可以给出它的形式化描述：

·　状态空间：所有数字摆放的布局；

·　初始状态：左侧图的布局；

·　动作空间：将空格相邻的数字之一移动到空格处；

·　转移函数：给定上一布局和动作，转移函数返回当前数字布局；

·　损耗函数：该问题中，每移动一次数字产生一单位的损耗；

·　目标测试函数：判断当前数字布局是否与图右侧布局一致。

第二个例子是图1.3中的地图路径搜索问题。在这个问题里，可以沿着图中标出的边从一个城市移动到另一个城市，边上的数字显示了对应两座城市之间的距离。我们的目标是找到从乌鲁木齐（A）到台北（T）距离最短的一条路径。该问题的形式化描述为：

·　状态空间：地图中的城市；

·　初始状态：本问题中，我们假设智能体从乌鲁木齐出发，故初始城市为乌鲁木齐（A）；

·　动作空间：所有移动到相邻城市的动作集合，即图中的邻边；

·　转移函数：给定状态（城市）和动作（边），转移函数返回下一个到达的状态（城市）；

·　损耗函数：该问题中，每个动作的成本可以设定为从当前城市到达另一城市的距离；

·　目标测试函数：判断当前城市是不是目标城市，在本问题中为台北（T）。