05 搜索技术.png

搜索技术

图搜索策略

路径就是给出一个状态序列

• 序列第一个状态是初始状态
• 最后一个状态是目标状态
• 序列中任意两个相邻的状态之间通过一个连线连接

为了提高搜索效率，图搜索并不是先生成所有状态的连接图再进行搜索，而是边搜索边生成图，知道找到一个符合条件的解，即路径为止

生成的无用状态越少，搜索的效率越高，对应的搜索策略就越好

盲目搜索

在搜索过程中没有利用任何与问题有关的知识或者启发信息，称为盲目搜索

无信息引导的搜索策略

常用的盲目搜索方法

• 深度优先搜索

  • 基本思想是优先扩展深度最深的节点

• 广度优先搜索

  • 优先搜索深度浅的节点

启发式搜索

对比盲目搜索能够减少搜索范围，引入启发信息

常用算法A算法和A*算法

博弈搜索

约翰·麦卡锡提出α-β剪枝算法

• 利用已经搜索过的状态对搜索进行剪枝，以提高搜索速度

蒙特卡洛方法

• 选择：以当前起居为根节点，自上而下的选择一个落子点
• 扩展：向选定的节点添加一个或多个子节点
• 模拟：对扩展出的节点用蒙特卡洛方法进行模拟
• 回传：根据模拟结果依次向上更新祖先节点的估计值

本章小结

通常搜索策略的主要任务式确定如何选取规则的方式

两种基本方式

• 盲目式搜索
• 启发式搜索