搜索算法
姚金宇
Outline
• 产生式系统
• 剪枝
• 博弈问题
最简单or最困难的算法
• 最简单
– 入门算法
– 所需基本知识不多，算法描述简单，思考直白
• 最困难
– 搜索不难，时间不够
– 如何选择搜索方法，如何选择顺序，如何剪枝
– 难以举一反三
搜索问题
• 搜索问题：在一个空间中寻找目标
– 搜索什么（目标）
– 在哪里搜索（状态空间）
• 在搜索中，如何扩展状态空间是关键性问
题
• 搜索可以根据是否使用启发式信息分成
– 盲目搜索：只能区分当前状态是否为目标状态
– 启发式搜索：在搜索过程中加入与问题相关的
启发信息，指导搜索的方向
产生式系统
• 知识单元之间存在着因果关系，或者说前
提和结论，一般用产生式（或者称为规则）
来表示。
• 把一组产生式放在一起，让它们互相配合，
协同作用，一个产生式生成的结论可以供
另一个产生式作为前提使用，以这种方法
求得问题的解决，这就叫做产生式系统。
- 1
- 2
- 3
前往页