人工智能

1 - 搜索

2020-09-08 09:00 CST
2020-09-15 17:05 CST
CC BY-NC 4.0

状态空间搜索

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

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

状态空间表示

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

例子:

  • 井字棋
  • 8-puzzle

要点:

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

方法:

  • 宽度优先搜索
  • 深度优先搜索
  • 最佳优先搜索(启发式)