第二章与或图搜索问题.ppt
《第二章与或图搜索问题.ppt》由会员分享,可在线阅读,更多相关《第二章与或图搜索问题.ppt(26页珍藏版)》请在三一文库上搜索。
1、1,第二章 与或图搜索问题,与或图搜索问题 对问题进行分割后进行搜索,2,梵塔难题,3,解题过程(3个圆盘问题),4,与/或(AND/OR)图表示,与图、或图、与或图,与图,或图,5,与或图,6,一些关于与或图的术语,7,梵塔问题与或图,8,2.1 基本概念,与或图是一个超图,节点间通过连接符连接。 K-连接符:,9,耗散值的计算,k(n, N) = Cn+k(n1, N)+k(ni, N) 其中:N为终节点集 Cn为连接符的耗散值,10,11,解图:,12,能解节点,终节点是能解节点 若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解。 若非终节点有“与”子节点时,
2、当且仅当其子节点均能解时,该非终节点才能解。,13,不能解节点,没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解。 若非终节点有“与”子节点时,当至少有一个子节点不能解时,该非终节点才不能解。,14,f(n) = g(n) + h(n) 对n的评价实际是对从s到n这条路径的评价,n,s,2.2 与或图的启发式搜索算法AO*,普通图搜索的情况,15,与或图: 对局部图的评价,目标,目标,初始节点,a,b,c,16,两个过程,图生成过程,即扩展节点 从最优的局部途中选择一个节点扩展 计算耗散值的过程 对当前的局部图重新新计算耗散值,17,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 搜索 问题
链接地址:https://www.31doc.com/p-2597259.html