《人工智能及其应用》课件第5章 搜索求解策略.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《人工智能及其应用》课件第5章 搜索求解策略.pptx》由用户(momomo)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能及其应用 人工智能及其应用课件第5章 搜索求解策略 人工智能 及其 应用 课件 搜索 求解 策略
- 资源描述:
-
1、第第5 5章章 搜索搜索求解策略求解策略 技术技术日新月异,人类生活方式正在快日新月异,人类生活方式正在快速转变,这一切给人类历史带来了一系列速转变,这一切给人类历史带来了一系列不可思议的奇点。我们曾经熟悉的一切,不可思议的奇点。我们曾经熟悉的一切,都开始变得陌生。都开始变得陌生。约翰冯诺依曼,19585.1 5.1 搜索的概念搜索的概念 搜索搜索的主要过程的主要过程 从初始或目的状态出发,并将它作为当前状态。从初始或目的状态出发,并将它作为当前状态。扫描操作算子集,将适用当前状态的一些操作算子作用在其上扫描操作算子集,将适用当前状态的一些操作算子作用在其上而得到新的状态,并建立指向其父结点的
2、指针。而得到新的状态,并建立指向其父结点的指针。检查所生成的新状态是否满足结束状态,如果满足,则得到解,检查所生成的新状态是否满足结束状态,如果满足,则得到解,并可沿着有关指针从结束状态反向到达开始状态,给出一解答路并可沿着有关指针从结束状态反向到达开始状态,给出一解答路径;否则,将新状态作为当前状态,返回第步再进行搜索。径;否则,将新状态作为当前状态,返回第步再进行搜索。5.2 5.2 状态空间表示状态空间表示5.2 5.2 状态空间表示状态空间表示2 2.状态空间的图描述状态空间的图描述 状态空间状态空间可用有向图来描述,图的结点表示问题的状态,图可用有向图来描述,图的结点表示问题的状态,
3、图的弧表示状态之间的关系,就是求解问题的步骤的弧表示状态之间的关系,就是求解问题的步骤。初始状态初始状态对应于实际问题的已知信息,是图中的根结点。问对应于实际问题的已知信息,是图中的根结点。问题的状态空间描述中,寻找从一种状态转换为另一种状态的某个题的状态空间描述中,寻找从一种状态转换为另一种状态的某个操作算子序列就等价于在一个图中寻找某一路径。操作算子序列就等价于在一个图中寻找某一路径。5.2 5.2 状态空间表示状态空间表示5.3 5.3 盲目搜索盲目搜索 回溯回溯 回溯搜索是从初始状态出发,不停地试探性地寻找路径,直回溯搜索是从初始状态出发,不停地试探性地寻找路径,直到到达目的或到到达目
4、的或“不可解结点不可解结点”,即,即“死胡同死胡同”为止为止。回溯回溯策略是当遇到不可解结点时就回溯到路径中最近的父结策略是当遇到不可解结点时就回溯到路径中最近的父结点上,查看该结点是否还有其他的子结点未被扩展点上,查看该结点是否还有其他的子结点未被扩展。若若有,则沿这些子结点继续搜索;如果找到目标,就成功退有,则沿这些子结点继续搜索;如果找到目标,就成功退出搜索,返回解题路径。出搜索,返回解题路径。5.3.15.3.1回溯回溯 回溯回溯搜索的算法用三张表来保存状态空间中的不同性质结点。搜索的算法用三张表来保存状态空间中的不同性质结点。(1)(1)路径状态表路径状态表 路径状态(路径状态(Pa
5、th StatesPath States,PSPS)表保存当前搜索路径上的状态。)表保存当前搜索路径上的状态。如果找到了目的,如果找到了目的,PSPS就是解路径上的状态有序集。就是解路径上的状态有序集。(2)(2)新的路径状态表的新的路径状态表的 新的路径状态(新的路径状态(New Path StatesNew Path States,NPSNPS)表包含了等待搜索)表包含了等待搜索的状态,其后裔状态还未被搜索到,即未被生成扩展。的状态,其后裔状态还未被搜索到,即未被生成扩展。(3)(3)不可解状态表不可解状态表 不可解状态(不可解状态(No Solvable StatesNo Solvabl
6、e States,NSSNSS)表列出了找不到解)表列出了找不到解路径的状态路径的状态。如果如果在搜索中扩展出的状态是它的元素,则可立即将之排除,在搜索中扩展出的状态是它的元素,则可立即将之排除,不必沿该状态继续搜索。不必沿该状态继续搜索。5.3.15.3.1回溯回溯目标状态之一目标状态之一5.3.15.3.1回溯回溯5.3.15.3.1回溯回溯5.3.25.3.2广度优先搜索广度优先搜索5.3.35.3.3广度优先搜索广度优先搜索5.3.35.3.3广度优先搜索广度优先搜索5.3.35.3.3深度优先搜索深度优先搜索 深度优先搜索深度优先搜索(Depth-First SearchDepth-
展开阅读全文