资源预览内容
第1页 / 共90页
第2页 / 共90页
第3页 / 共90页
第4页 / 共90页
第5页 / 共90页
第6页 / 共90页
第7页 / 共90页
第8页 / 共90页
第9页 / 共90页
第10页 / 共90页
亲,该文档总共90页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2.4启发式搜索,搜索技术的应用智能搜索引擎 启发式搜索涉及的基本概念 基本的启发式搜索方法 代价树的广度优先搜索 动态规划法(改进的代价树广度优先搜索) 代价树的深度优先搜索(局部优先搜索) 代价树有界深度优先搜索 局部择优A算法 A算法(全局优先搜索),启发式搜索概念,启发式搜索与无信息搜索 无信息(盲目)搜索:按预定的控制策略进行搜索,在搜索过程中 获得的中间信息并不改变控制策略。 81 启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导 搜索朝着最有希望的方向前进,加速问题的求解过程并 找到最优解。 启发性信息 评估函数,评估函数的表示,含义:用于估价节点重要性的函数称为估价函数 表示: f(x)=g(x)+h(x) g(x)是从初始结点S0到x实际代价 h(x)是从x到目标结点Sg的最佳路径的估计代价, 启发性信息的函数描述。 例 重排九宫问题 f(x)=d(x)+h(x),代价的计算,边代价:从父节点到子节点的代价 表示:c(x1,x2)表示从父节点x1到子节点x2的代价 例:c(s0,A)=2 c(A,C)=4 代价:从一个节点经过一条支路到另一个节点所支付的代价。 表示:g(x)表示从初始节点s0到节点x的代价 例: g(A)=g(s0)+c(s0,A)=0+2=2 g(C)=g(A)+c(A,C)=2+4=6 代价树:边上标有代价的搜索树,s0,A,C,B,3,2,4,s0,A,B,C,2,3,4,2.4.1 代价驱动的搜索策略,代价树的广度优先搜索 动态规划法(改进的代价树广度优先搜索) 代价树的深度优先搜索,代价树的广度优先搜索,基本思想 搜索过程 实例 存在问题 解决方法(动态规划法),基本思想,open表的节点顺序按的节点代价排列(从小到大),搜索过程,1.将初始节点s0放入OPEN表,令g(s0)=0 2.如果OPEN表为空,则问题无解,退出 3.把OPEN表的第一个节点(记为n节点)取出放入CLOSED表 4.考察节点n是否为目标节点。若是,则求得了问题的解,退出。 5.若节点n不可扩展转(2)步。 6.扩展节点n,将其子节点放入OPEN表中,并为每一个子节点都配置指向父节点的指针;计算各个子节点的代价,并按各个节点的代价对表的全部节点进行排序(按从小到大的顺序),然后转(2)步。,例 如图是八城市间的交通图,两城市间的交通费用(代价)如图中数字所示。求从S到T的最小交通费用代宽演示.ppt,S,A,D,E,B,F,T,C,3,4,4,5,2,5,4,4,3,代价树的广度优先搜索(例),1,2,3,4,5,6,7,10,11,12,13,8,9,19,20,21,15,17,18,14,S(0),D1(4),A1(3),B1( 7 ),D2(8),A2(9),E1(6),F1(10),T1(13),C1(11),B2(11),B3(13),E3(10),E2(12),16,D3(14),F3(16),B4(15),F2(14),C3(17),A3(15),C2(15),3,4,4,4,5,5,5,2,4,5,4,2,2,4,5,4,4,4,4,3,Open表(代价树的广度优先搜索) 初始 (S(0) 1 (A1(3), D1(4) 2 (D1(4), B1(7),D2(8) 3 (E1(6),B1(7),D2(8),A2(9) 4 (B1(7),D2(8),A2(9),F1(10),B2(11) 5 (D2(8),A2(9),F1(10),B2(11),C1(11),E2(12) 6 (A2(9),F1(10),E3(10),B2(11),C1(11),E2(12) 7 (F1(10),E3(10),B2(11),C1(11),E2(12),B3(13) 8 (E3(10),B2(11),C1(11),E2(12),B3(13),T1(13) 9 (B2(11),C1(11),E2(12),B3(13),T1(13),F2(14),B4(15) 10 (C1(11),E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15) 11 (E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15) 12 (B3(13),T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16) 13 (T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16),C3(17) 14 T1(13)为目标节点,结束。,算法讨论,存在问题 改进方法,动态规划法,基本思想 搜索过程 实例,基本思想,当有多条到达某一公共节点的路径,只保留代价最小的路径,搜索过程,1.将初始节点s0放入OPEN表,令g(s0)=0 2.如果OPEN表为空,则问题无解,退出 3.把OPEN表的第一个节点(记为n节点)取出放入CLOSED表 4.考察节点n是否为目标节点。若是,则求得了问题的解,退出。 5.若节点n不可扩展转(2)步。 6.扩展节点n,将其子节点放入OPEN表中,并为每一个子节点都配置指向父节点的指针;计算各个子节点的代价,若新出现的节点是多条路径都到达的节点,则只选代价最小的路径,其余删去,并按各个节点的代价对表的全部节点进行排序(按从小到大的顺),然后转(2)步。,例 如图是八城市间的交通图,两城市间的交通费用(代价)如图中数字所示。求从S到T的最小交通费用动态规划.ppt,S,A,D,E,B,F,T,C,3,4,4,5,2,5,4,4,3,动态规划法(例),1,2,3,4,5,6,7,10,11,8,9,14,S(0),D1(4),A1(3),B1( 7 ),D2(8),A2(9),E1(6),F1(10),T1(13),C1(11),E2(12),3,4,4,4,5,5,5,5,4,2,3,B2(11),Open表(动态规划法) 初始 (S(0) 1 (A1(3), D1(4) 2 (D1(4), B1(7),D2(8) (删除) 3 (E1(6),B1(7),A2(9) 4 (B1(7),F1(10),B2(11) ) 5 (F1(10),C1(11),E2(12) ) 6 (C1(11),T1(13) 7 (T1(13) 8 结束,代价树的深度优先搜索,基本思想 搜索过程 实例 算法讨论,基本思想:在刚扩展的子节点中选择一个代价最小的节点进行扩展,即表的首部存放刚扩展的所有子节点(按代价从小到大排序) 搜索过程: 1.将初始节点放入OPEN表,令g(s0)=0 2.如果OPEN表为空,则问题无解,退出 3.把OPEN表的第一个节点(记为n节点)取出放入CLOSED表 4.考察节点n是否为目标节点。若是,则求得了问题的解,退出。 5.若节点n不可扩展转(2)步。 6.扩展节点n,将其子节点按代价从小到大放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,然后转(2)步。,例 如图是八城市间的交通图,两城市间的交通费用(代价)如图中数字所示。求从S到T的最小交通费用,S,A,D,E,B,F,T,C,3,4,4,5,2,5,4,4,3,代价树的深度优先搜索(例),1,2,3,4,5,6,7,8,9,S(0),D1(4),A1(3),B1( 7 ),D2(8),C1(11),E 1(12),D3(14),F1(16),3,4,4,4,5,5,2,4,10,T1(19),Open表(代价树的深度优先搜索) 初始 (S(0) 1 (A1(3), D1(4) 2 (B1(7),D2(8),D1(4) ) 3 (C1(11),E2(12),D2(8),D1(4) 4 (E1(12),D2(8),D1(4) ) 5 (D3(14),F1(16),D2(8),D1(4) ) 6 (F1(16),D2(8),D1(4) 7 (T1(19),D2(8),D1(4) 8 T1(19)为目标节点结束,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,1(0),3(1),4(1),5(1),7(2),例2代价树的深度优先搜索 (括号中为代价),2(1),6(2),8 3 2 1 4 7 6 5,9(4),8 3 2 1 4 7 6 5,8 1 3 2 4 7 6 5,10(4),8(3),8 1 3 2 4 7 6 5,1 3 8 2 4 7 6 5,8 1 3 7 2 4 6 5,1 2 3 8 4 7 6 5,15(6),(例2续),11(5),解的路径:1-2-6-8-10-11-14-16-18,14(6),1 3 8 2 4 7 6 5,17(8),1 3 8 2 4 7 6 5,16(7),8 1 3 2 4 7 6 5,8 1 3 2 6 4 7 5,12(5),13(5),18(8),2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,1(0),3(1),4(1),5(1),例2 换一条路径,2(1),2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,6(2),1 2 3 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,7(2),10(4),8(3),9(4),算法讨论,存在的问题 解决方法,代价树的有界深度优先搜索,基本思想 搜索过程 实例,基本思想,当一个节点被扩展后,按f(x)对每一个子节点计算估值,并选择其中最小的先扩展。,代价树的有界深度优先搜索过程,1.将初始节点放入OPEN表,令g(s0)=0 2.如果OPEN表为空,则问题无解,退出 3.把OPEN表的第一个节点(记为n节点)取出放入CLOSED表 4.考察节点n是否为目标节点。若是,则求得了问题的解,退出。 5.若节点n不可扩展转(2)步。 6.IF d(n)=规定深度 THEN GO (2) 7.扩展节点n,用估价函数f(x)计算每个子节点的估价值,并将其子节点按估价值从小到大放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,然后转(2)步。,例 如图是八城市间的交通图,两城市间的交通费用(代价)如图中数字所示。求从S到T的最小交通费用,S,A,D,E,B,F,T,C,3,4,4,5,2,5,4,4,3,代价树的有界深度优先搜索(例) dm=4,1,2,3,4,5,13,14,6,7,10,15,16,8,9,11,14,S(0),D1(4),A1(3),B1( 7 ),D2(8),A2(9),E3(6),F3(10),T1(13),C1(11),E2(10),E1(12),12,D3(14),F1(16),B2(15),F2(14),3,4,4,4,5,5,5,2,5,4,2,2,4,5,4,3,B3(11),代价树搜索的总结,优点 不足:局限性,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,1(0),3(1),4(1),5(1),九宫问题使用代价的局限性,2(1),2 3 1 8 4 7 6 5,2 3 1 8 4 7
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号