05 搜索技术.png
搜索技术
图搜索策略
路径就是给出一个状态序列
- 序列第一个状态是初始状态
- 最后一个状态是目标状态
- 序列中任意两个相邻的状态之间通过一个连线连接
为了提高搜索效率，图搜索并不是先生成所有状态的连接图再进行搜索，而是边搜索边生成图，知道找到一个符合条件的解，即路径为止
生成的无用状态越少，搜索的效率越高，对应的搜索策略就越好
盲目搜索
在搜索过程中没有利用任何与问题有关的知识或者启发信息，称为盲目搜索
无信息引导的搜索策略
常用的盲目搜索方法
-
深度优先搜索
- 基本思想是优先扩展深度最深的节点
-
广度优先搜索
- 优先搜索深度浅的节点
启发式搜索
对比盲目搜索能够减少搜索范围，引入启发信息
常用算法A算法和A*算法
博弈搜索
约翰·麦卡锡提出α-β剪枝算法
- 利用已经搜索过的状态对搜索进行剪枝，以提高搜索速度
蒙特卡洛方法
- 选择：以当前起居为根节点，自上而下的选择一个落子点
- 扩展：向选定的节点添加一个或多个子节点
- 模拟：对扩展出的节点用蒙特卡洛方法进行模拟
- 回传：根据模拟结果依次向上更新祖先节点的估计值
本章小结
通常搜索策略的主要任务式确定如何选取规则的方式
两种基本方式
- 盲目式搜索
- 启发式搜索
