状态空间搜索

• 搜索：一种问题求解方法
• 动机：理解AI中的静和变

状态空间搜索 - GOFAI的主要推断模型

状态空间表示

• 状态空间图：节点$N$和连接（弧）$A$
• 初始状态：$S$是$N$的非空子集
• 目标状态：$G$是$N$的非空子集
• 状态空间搜索：寻找从初始状态到目标状态的解路径

例子：

• 井字棋
• 8-puzzle

要点：

• 搜索方向：
  • 前向搜索 vs 后向搜索
  • 数据驱动 vs 目标驱动
• 回溯技术

方法：

• 宽度优先搜索
• 深度优先搜索
• 最佳优先搜索（启发式）