最新启发式图搜索ppt课件精品课件.ppt
《最新启发式图搜索ppt课件精品课件.ppt》由会员分享,可在线阅读,更多相关《最新启发式图搜索ppt课件精品课件.ppt(28页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、启发式搜索启发式搜索 定义:为减小搜索范围而需要利用某些已知的、有关具体问题领域的特性信息。此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。 特点:重排OPEN表,选择最有希望的节点加以扩展 种类:最佳优先搜索、A*算法等开始开始把把S放入放入OPEN表,表,计算估价函数计算估价函数 f (s)OPEN表为空表?表为空表?把把OPEN表中的第一个节点表中的第一个节点n放入放入CLOSED表表n为目标节点吗?为目标节点吗?扩展扩展n,计算所有子节点的估价函数值,计算所有子节点的估价函数值,并提供它们返回节点并提供它们返回节点n的指针。的指针。失败失败成功成功最佳优先搜索算法框图最
2、佳优先搜索算法框图是是否否是是否否把子节点送入把子节点送入OPEN表,并对其中的所有表,并对其中的所有节点按估价函数值由小到大重排。节点按估价函数值由小到大重排。迷宫问题如下,F是入口,B是出口,试采用最佳优先搜索算法进行求解。举例:迷宫问题举例:迷宫问题0123x123yFGHECADB22241111解:估价函数f(n)采用每个节点与目标节点在坐标系上的距离来表示。例如,E点与目标节点B之间的空间距离是2+2=4,两个2分别是E与B在x轴及y轴上的距离。注:每个节点小括号内的数值表示该节点到目标的空间距离,即该点的估价函数值。搜索得到的路径如黄线所示。F(6)G(5)H(3)E(4)A(2
3、)B(0)12345C(3)6 举例:八数码魔方(8-puzzle problem)12384567(目标状态)12384567(初始状态)57123845671238456712384567 (3) (5) (5)123845671238456712384567 (4) (3) (3)1238456712 384567 (2) (4)1238456712384567 (3) (4)12384567 (1)813245671 2384567 (0)(2)八数码魔方的最八数码魔方的最佳优先搜索树佳优先搜索树123846(4)75搜索得到的路径如黄线所示搜索得到的路径如黄线所示 本题采用了简单的估
4、价函数 f(n)=W(n)其中:W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此,初始节点棋局的f(n)值等于4。12384567 第步有三种情况,我们选择其中f(n)最小的: 其它依次类推.最后用了7步得出了结果. 123845671238456712384567 (3)(5)(5) A算法最佳优先算法有时无法得到最优解,因为它的估价函数f的选取时,忽略了从初始节点到目前节点的代价值。所以,可考虑每个节点n的估价函数f(n)分为两个分量:从起始节点到节点n的代价g(n)以及从节点n到达目标节点代价的估算值h(n)。 f(n)=g(n)+h(n) f(n)节点n的估价函数; g(n)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新 启发式 搜索 ppt 课件 精品
限制150内