第一章搜索问题.ppt
《第一章搜索问题.ppt》由会员分享,可在线阅读,更多相关《第一章搜索问题.ppt(19页珍藏版)》请在三一文库上搜索。
1、1,第一章 搜索问题,内容: 状态空间的搜索问题。 搜索方式: 盲目搜索 启发式搜索 关键问题: 如何利用知识,尽可能有效地找到问题的解(最佳解)。,2,搜索问题,讨论的问题: 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗? 什么情况下可以找到最佳解? 求解的效率如何。,3,1.1 回溯策略,例:皇后问题,4,( ),5,( ),Q,(1,1),6,( ),Q,Q,(1,1),(1,1) (2,3),7,( ),Q,(1,1),(1,1) (2,3),8,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),9,( ),Q,Q,(1,1),(1,1)
2、 (2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),10,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),11,( ),Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),12,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),13,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),14,( ),(1,1),(1,1) (2,3),(1
3、,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),15,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),Q,(1,2) (2,4) (3,1),16,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),Q,(1,2) (2,4) (3,1),Q,(1,2) (2,4) (3,1) (4,3),17,递归的思想,当前状态,目标状态g,18,一些深入的问题,失败原因分析、多步回溯,19,一些深入问题,回溯搜索中知识的利用 基本思想(以皇后问题为例): 尽可能选取划去对角线上位置数最少的。,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 搜索 问题
链接地址:https://www.31doc.com/p-2596987.html