1. 问题的定义

一、搜索问题四要素

• 状态/状态空间
  • 状态描述一个具体的场景
  • 状态空间包含了所有的可能状态
• 后继函数（动作、损耗）
  • 状态通过动作选择而产生连接的关系
  • 动作空间表示某一个状态下可以采取的动作集合
• 开始状态
  • 问题开始的状态
• 结束测试
  • 问题结束的条件

二、吃豆人小游戏

搜索问题建模 - 吃豆人 （已3*3的大小为例）

• 状态空间

• 后继函数

  • 动作空间：上、下、左、右
  • 损耗：单步损耗为1

• 开始状态

• 目标测试

  • 移动到某一个特定位置

三、八数码问题

你可以将一个数码移动到它旁边的空格中。

• 状态空间
  • 8个数码的位置。每一个都可以用二维数组表示(x, y)。
• 后继函数
  • 移动空白格子：上、下、左、右
• 开始状态（游戏初始的状态）
• 目标状态

四、八皇后问题

• 在8*8的棋盘上，陆续摆上8个皇后，并且保证皇后之间两两不互相攻击。

• 攻击：皇后可以攻击到同一行，同一列，同一正对角线/反对角线的棋子。

• 在图示的例子中，我们还需要摆放3个皇后。

• 状态空间

  • 0 - 8个皇后摆在棋盘上
  • 使用一个8*8的矩阵，布尔值。

• 后继函数

  • 增加一个皇后到棋盘上

• 开始状态：空白的棋盘

• 目标测试：8个皇后在棋盘上，两两不攻击

五、罗马尼亚旅行者问题

• 地图上的每一个节点代表一个城市。
• 边表示城市和城市之间可直接达到，边上的数字是两个城市的距离。
• 在途中寻找一个最短的从出发城市到目标城市的路径。
• 在这个例子中，我们希望从Arad到Bucharest。