人工智能第二章下课件.ppt

《人工智能第二章下课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第二章下课件.ppt（90页珍藏版）》请在三一办公上搜索。

1、2.4启发式搜索,搜索技术的应用智能搜索引擎启发式搜索涉及的基本概念基本的启发式搜索方法代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索(局部优先搜索)代价树有界深度优先搜索局部择优A算法A算法(全局优先搜索),启发式搜索概念,启发式搜索与无信息搜索无信息（盲目）搜索：按预定的控制策略进行搜索，在搜索过程中 获得的中间信息并不改变控制策略。 81 启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导 搜索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。 启发性信息评估函数,评估函数的表示,含义：用于估价节点重要性的函数称为估价函数表示： f(x)=

2、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=2g(C)=g(A)+c(A,C)=2+4=6代价树：边上标有代价的搜索树,s0,A,C,B,3,2,4,s0,A,B,C,2,3,

3、4,2.4.1 代价驱动的搜索策略,代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索,代价树的广度优先搜索,基本思想搜索过程实例存在问题解决方法(动态规划法）,基本思想,open表的节点顺序按的节点代价排列（从小到大）,搜索过程,1.将初始节点s0放入OPEN表,令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子

4、节点的代价，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺序），然后转（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(1

5、4),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)

6、,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)

7、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)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都

8、配置指向父节点的指针；计算各个子节点的代价，若新出现的节点是多条路径都到达的节点，则只选代价最小的路径，其余删去，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺），然后转（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

9、,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)=02.如果OPE

10、N表为空，则问题无解，退出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(1

11、1),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 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 3

12、1 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,1（0）,3(1),4(1),5(1),7(2),例2代价树的深度优先搜索（括号中为代价）,2（1）,6(2),8 32 1 47 6 5,9(4),8 32 1 47 6 5,8 1 32 47 6 5,10(4),8(3),8 1 3 2 47 6 5,1 38 2 47 6 5,8 1 37 2 4 6 5,1 2 38 47 6 5,15(6),（例2续）,11(5),解的路径：1-2-6-8-10-11-14-16-18,14(6),1 38 2 47 6 5,17(8),1 38

13、 2 47 6 5,16(7),8 1 32 47 6 5,8 1 32 6 47 5,12(5),13(5),18(8),2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,1（0）,3(1),4(1),5(1),例2 换一条路径,2（1）,2 31 8 47 6 5,2 31 8 47 6 5,6(2),1 2 3 8 47 6 5,1 2 38 47 6 5,1 2 37 8 4 6 5,7(2),10(4),8(3),9(4),算法讨论,存在的问题解决方法,代价树的有界深度优先搜索,基本思想搜索过

14、程实例,基本思想,当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。,代价树的有界深度优先搜索过程,1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.IF d(n)=规定深度 THEN GO (2) 7.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。,例 如图是

15、八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从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),代价树搜索的总结,优点不足：局

16、限性,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,1（0）,3(1),4(1),5(1),九宫问题使用代价的局限性,2（1）,2 31 8 47 6 5,2 31 8 47 6 5,6(2),1 2 3 8 47 6 5,1 2 38 47 6 5,1 2 37 8 4 6 5,7(2),10(4),8(3),9(4),2.4.2 A算法,启发性函数A算法A*算法算法讨论,启发性函数的表示,含义：用于估价节点重要性的函数称为估价函数表示： f(x)=g(x)+h(x) g(x)是从初始结点S0到x

17、实际代价h(x)是从x到目标结点Sg的最佳路径的估计代价, 启发性信息的函数描述。例 重排九宫问题,例：重排九宫问题,例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有： R1: 如果满足条件 则 空格左移R2: 如果满足条件 则 空格上移R3: 如果满足条件 则 空格右移R4: 如果满足条件 则 空格下移注：条件指有位置并且不重复冲突解决方法：算符序号,2 8 31 47 6 5,1 2 3 8 47 6 5,解：f(n)=d(n)+W(n) 取g(n)=d(n)，h(n)=W(n)。 d(n)表示节点n在搜索树中的深度它说明是用从S0到n的路径上的单位代价表示实

18、际代价， W(n)表示节点n中“不在位”的数码个数，作为启发信息。 一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。 对初始节点S0，由于d(S0)=0，W(S0)=3，因此有 f(S0)=0+3=3,2 8 31 47 6 5,1 2 38 47 6 5,S0 Sg,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,A算法概述,概念： 在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。 由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法

19、。类型： 可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。 全局择优： 从Open表的所有节点中选择一个估价函数值最小的一个进行扩展。 局部择优：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。,局部择优A算法,基本思想：当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。搜索过程：1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2

20、）步。6.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。,局部择优A算法例：重排九宫问题,例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有： R1: 如果满足条件 则 空格左移R2: 如果满足条件 则 空格上移R3: 如果满足条件 则 空格右移R4: 如果满足条件 则 空格下移注：条件指有位置并且不重复冲突解决方法：算符序号,2 8 31 47 6 5,1 2 3 8 47 6 5,f(n)=d(n)+W(n) 。 d(n)表示节点n在搜索树中的深度它

21、说明是用从S0到n的路径上的单位代价表示实际代价， W(n)表示节点n中“不在位”的数码个数，作为启发信息。对初始节点S0，由于d(S0)=0，W(S0)=3，因此有 f(S0)=0+3=3,2 8 31 47 6 5,1 2 38 47 6 5,S0 Sg,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,1（3）,3(4),4(5),5(5),7(6),局部择优A算法，例,2（4）,6(5),8 32 1 47 6 5,9(8),8 32 1

22、 47 6 5,8 1 32 47 6 5,10(7),8(6),8 1 3 2 47 6 5,1 38 2 47 6 5,8 1 37 2 4 6 5,1 2 38 47 6 5,15(10),局部择优A算法，例(续）,11(8),解的路径：1-2-6-8-10-11-14-16-18,14(9),1 38 2 47 6 5,17(10),1 38 2 47 6 5,16(8),8 1 32 47 6 5,8 1 32 6 47 5,12(9),13(9),18(8),算法讨论,局部择优A算法存在的问题解决方法,限界局部择优A算法法,1.将初始节点放入OPEN表，令g(s0)=02.如果OP

23、EN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.IF d(n)=规定深度 THEN GO (2) 7.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。,限界局部择优：重排九宫问题,例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有： R1: 如果满足条件 则 空格左移R2: 如果满足条件 则 空格上移R3: 如果满足条

24、件 则 空格右移R4: 如果满足条件 则 空格下移注：条件指有位置并且不重复冲突解决方法：算符序号f(x)=d(x)+h(x) d(x):节点x的深度，深度=4h(x):节点x的格局与目标节点格局不相同的牌数。,2 8 31 47 6 5,1 2 3 8 47 6 5,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,1（3）,3(4),4(5),5(5),7(6),限界局部择优搜索（例）d=4,2（4）,6(5),8 32 1 47 6 5,9

25、(9),8 32 1 47 6 5,8 1 32 47 6 5,10(8),8(6),2 31 8 47 6 5,2 31 8 47 6 5,14(4),1 2 3 8 47 6 5,1 2 38 47 6 5,1 2 37 8 4 6 5,2 8 37 1 46 5,11(8),2 8 37 46 1 5,2 8 37 1 46 5,12(9),13(10),15(6),18(6),16(4),17(4),Open表的变化(限界局部择优搜索法）初始 (1(3) 1 (2(4),3(4),4(5),5(5) 2 (6(5),7(6), 3(4),4(5),5(5) 3 (8(6), 7(6),

26、 3(4),4(5),5(5) 4 (10(8),9(9), 7(6), 3(4),4(5),5(5) d=4 5 ( 7(6), 3(4),4(5),5(5) d=2 6 (11(8), 3(4),4(5),5(5) d=3 7 ( 12(9),13(10), 3(4),4(5),5(5) d=4 8 ( 3(4),4(5),5(5) d=1 9 ( 14(4),15(6), 4(5),5(5) d=2 7 (16(4), 15(10), 3(4),4(5),5(5) d=3 8 (17(4),18(6), 15(10), 3(4),4(5),5(5) d=4 9 17(4)为目标节点，结束

27、,算法讨论,局部择优搜索方法评价与深度优先搜索比较缺陷,全局择优搜索A算法描述,(1)把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)； (2)如果Open表为空，则问题无解 ，失败退出； (3)把Open表的第一个节点取出放入Closed表，并记该节点为n； (4)考察节点n是否为目标节点。若是，则找到问题的解，成功退出； (5)若节点n不可扩展，则转第(2)步； (6)扩展节点n，生成其子节点ni(i=1, 2, )，计算每一个子节点的估价值f(ni)(i=1, 2, )，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中； (7)根据各节点的估价函数

28、值，对Open表中的全部节点按从小到大的顺序重新进行排序； (8)转第(2)步。,例：重排九宫问题,例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有： R1: 如果满足条件 则 空格左移R2: 如果满足条件 则 空格上移R3: 如果满足条件 则 空格右移R4: 如果满足条件 则 空格下移注：条件指有位置并且不重复冲突解决方法：算符序号f(x)=d(x)+h(x) d(x):节点x的深度，h(x):节点x的格局与目标节点格局不相同的牌数。,2 8 31 47 6 5,1 2 3 8 47 6 5,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8

29、 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,2 31 8 47 6 5,2 31 8 47 6 5,1 2 3 8 47 6 5,1 2 38 47 6 5,1（3）,3(4),4(5),5(5),7(6),A算法（例）,2（4）,解的路径：1381011,6(5),8(4),9(6),10(4),1 2 37 8 4 6 5,11(4),12(6),Open表的变化(A算法）初始 (1(3) 1 (2(4),3(4),4(5),5(5) 2 (3(4),4(5),5(5) ,6(5),7(6) 3 (8(4

30、), 4(5),5(5) ,6(5), 7(6) ,9(6) ) 4 (10(4),4(5),5(5) ,6(5), 7(6) ,9(6) ) 5 (11(4),4(5),5(5) ,6(5), 7(6) ,9(6) ,12(6) 6 11(4)为目标节点，结束,算法讨论,全局择优搜索A算法评价：如何找到最优解.,目标,寻找最佳全局搜索算法A*A*算法总能找到最优解使扩展结点数尽量少方法：对启发式函数进行限制,目标1：算法的可采纳性,在问题有解的情况下，若一个搜索过程总能找到最优解，则称该算法具有可采纳性。可采纳性的衡量：f*(n)=g*(n)+h*(n)例 重排九宫问题 f(x)=d(x)+

31、h(x) h1(x)=0 h2(x):错位棋牌的个数h3(x):每个将牌与其目标位置之间的距离和,2 8 31 47 6 5,1 2 38 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,2 31 8 47 6 5,2 31 8 47 6 5,2 8 1 4 37 6 5,2 8 31 4 57 6,8 32 1 47 6 5,2 8 37 1 46 5,1 2 3 8 47 6 5,2 3 41 87 6 5,2 8 1 4 37 6 5,2 8 31 4 57 6,2 8 3 6 4

32、1 7 5,2 8 31 67 5 4,8 32 1 47 6 5,8 1 32 47 6 5,2 8 37 46 1 5,2 8 37 1 46 5,1 2 38 47 6 5,3,4,5,2 8 31 6 4 7 5,2 8 31 6 47 5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,23,24,25,26,22,2 3 41 8 57 6,2 3 41 87 6 5,2 8 1 4 37 6 5,2 4 8 1 37 6 5,2 8 31 4 5 7 6,2 8 31 57 4 6,2 8 1 4 37 6 5,2 4 8 1 37 6 5

33、,2 8 31 67 5 4,2 8 1 6 3 7 5 4,8 3 42 1 7 6 5,8 1 3 2 47 6 5,8 32 1 47 6 5,8 1 32 47 6 5,2 8 3 7 46 1 5,2 37 8 46 1 5,2 8 37 46 1 5,2 8 37 1 6 5 4,解的路径：1381626,2 8 3 1 47 6 5,2,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,2 8 31 47 6 5,1,A*算法（例 h1(x)=0=h*(n),扩展节点数：25生成节点数：44,2 8 31 47 6 5,2

34、 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,2 31 8 47 6 5,2 31 8 47 6 5,1 2 3 8 47 6 5,1 2 38 47 6 5,1（3）,3(4),4(5),5(5),7(6),A*算法(例 )h2(x)=w(x）=h*(n),2（4）,解的路径：1381011,6(5),8(4),9(6),10(4),1 2 37 8 4 6 5,11(4),12(6),扩展节点数：10生成节点数：12,2 8 31 47 6 5,2 8 3 1 47

35、6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,2 31 8 47 6 5,2 31 8 47 6 5,1 2 3 8 47 6 5,1 2 38 47 6 5,1（4）,3(4),4(6),5(6),A*算法(例 )h3(x)=p(x)=h(n),2（6）,解的路径：13689,6(4),7(6),8(4),1 2 37 8 4 6 5,9(4),10(6),扩展节点数：4生成节点数：10,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,2 31 8 47

36、 6 5,2 31 8 47 6 5,1 2 3 8 47 6 5,1 2 38 47 6 5,1,h*=4,g*=1W=3P=3,f=4,启发式函数比较(例 )h2(x)=w(x)h3(x)=p(x),W=3P=5,f=6,h*=2,g*=2W=3 P=2 f=4,h*=1,g*=3W=1P=1,f=4,1 2 37 8 4 6 5,h*=4,g*=0W=3P=4,f=4,3,6,2,8,9,h*=0,g*=4W=0P=0,f=4,4,W=4P=5,f=6,5,W=4P=5,f=6,7,W=4P=4,f=6,10,W=2P=2,f=6,扩展节点数：4生成节点数：9,看出规律了吗？,最佳全局搜

37、索算法A*,A*算法含义在A算法中，如果满足条件：h(n)h*(n)则A算法称为A*算法。,A*算法的采纳性证明,定理 (可采纳性定理)：若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。证明见书定理4.1、定理4.2、定理4.3,A*算法效率问题,A*算法评价如何设计搜索算法找到最优解并使扩展的节点数尽可能少.,另一个例子(有h(n)h*(n)函数）：,s(10),s(10),SA(7) SB(8) SC(9),SA(7) s(10),SB(8) SC(9) SAG(14),SBA(5) SC(9) SAG(14),SC(9) SBAG(12) SAG(14),SCB(7) S

38、BAG(12) SAG(14),SCBA(4) SBAG(12) SAG(14),SCBAG(11) SBAG(12) SAG(14),SB(8) SA(7)s(10),SBA(5) SB(8) SA(7) s(10),SC(9) SBA(5) SA(7) s(10),SCB(7) SC(9) SBA(5) SA(7) s(10),SCBA(4)SCB(7) SC(9) SBA(5) SA(7) s(10),SCBAG(11),一个例子(无H函数）：,s(10),s(10),SC(1) SB(3) SA(6),SC(1) s(10),SCB(2) SB(3) SA(6),SCBA(3) SB(

39、3) SA(6),SB(3) SA(6) SCBAG(11),SBA(4) SA(6) SCBAG(11),SA(6) SCBAG(11) SBAG(12),SCBAG(11) SBAG(12) SAG(14),SCB(2) SC(1)s(10),SCBA(3) SCB(2) SC(1) s(10),SB(3) SCBA(3) SCB(2)SC(1) s(10),SBA(4) SB(3) SCBA(3) SCB(2)SC(1) s(10),SA(6) SBA(4) SB(3) SCBA(3) SCB(2)SC(1) s(10),目标2：A*算法效率讨论,A*算法评价如何设计搜索算法找到最优解并

40、使扩展的节点数尽可能少.,出现多次扩展节点的原因,在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。,解决的途径,对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。,改进的条件,可采纳性不变不多扩展节点不增加算法的复杂性,对h加以限制,定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足h(ni) - h(nj) c(ni, nj)h(t) = 0(t为目标节点）或 h(ni) c(ni, nj) + h(nj) h(t) = 0 则称h是单调的。,实例证明：例1修改h(n),C(9),B(8),A(7),G

41、(0),一个例子(修改后h(n) )：,s(10),s(10),SC(10) SB(11) SA(13),SC(10) s(10),SCB(10) SB(11) SA(13),SCBA(10) SB(11) SA(13),SCBAG(11) SB(11) SA(13),SCBAG(11),SCB(10) SC(10) s(10),SCBA(10) SCB(10) SC(10) s(10),C(9),A(7),B(8),理论证明,定理4.5 如果h满足单调条件，则当A*算法扩展节点n时，该节点就已经找到了通往它的最佳路径，即g(n)=g*(n)。在h(n)满足单调性限制下的A*算法常被称为改进的

42、A*算法。,例2：修改h(n),h=19,h=18,h=17,h=16,h=0,总结：实现启发式搜索的关键,算法的完备性算法的可采纳性启发函数强弱对结果的影响,算法的完备性,对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题得解，则称该搜索过程为完备的，否则为不完备的。,算法的可采纳性,可纳性的含义： 对任一状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。,启发函数强弱对结果的影响1,启发函数强弱的衡量：h(n)接近h*(n)的程度理想情况：h(n)h*(n)，实

43、际上: h(n)=h*(n) (越接近越好)原因：A*算法的搜索效率很大程度上取决于估价函数h(n)。一般来说，在满足h(n) h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。,启发函数强弱对结果的影响2,h(n)满足单调性限制下的A*算法更好原因：能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径。在h(n)满足单调性限制下的A*算法常被称为改进的A*算法。,2.5图搜索策略总结,基本思想图搜索分类,状态空间搜索的基本思想,先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检

44、查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。,图搜索分类,无信息搜索搜索按预定的规则进行，不使用与问题有关的启发式信息启发式搜索搜索中使用与问题有关的启发式信息,并以这些启发式信息指导搜索过程(可以提高效率),本章小结,搜索策略状态空间搜索无信息搜索启发式搜索搜索方法的关系参考第4.1,4.2,4.3节,2 8 31 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8

45、32 1 47 6 5,2 8 37 1 4 6 5,2 31 8 47 6 5,2 31 8 47 6 5,2 8 1 4 37 6 5,2 8 31 4 57 6,8 32 1 47 6 5,2 8 37 1 46 5,1 2 3 8 47 6 5,2 3 41 87 6 5,2 8 1 4 37 6 5,2 8 31 4 57 6,2 8 3 6 41 7 5,2 8 31 67 5 4,8 32 1 47 6 5,8 1 32 47 6 5,2 8 37 46 1 5,2 8 37 1 46 5,1 2 38 47 6 5,1,3,4,5,2 8 31 6 4 7 5,2 8 31 6

46、 47 5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,23,24,25,26,宽度优先搜索图,22,2 3 41 8 57 6,2 3 41 87 6 5,2 8 1 4 37 6 5,2 4 8 1 37 6 5,2 8 31 4 5 7 6,2 8 31 57 4 6,2 8 1 4 37 6 5,2 4 8 1 37 6 5,2 8 31 67 5 4,2 8 1 6 3 7 5 4,8 3 42 1 7 6 5,8 1 3 2 47 6 5,8 32 1 47 6 5,8 1 32 47 6 5,2 8 3 7 46 1 5,2 37 8

47、46 1 5,2 8 37 46 1 5,2 8 37 1 6 5 4,解的路径：1381626,2 8 3 1 47 6 5,2,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,8 32 1 47 6 5,8 32 1 47 6 5,8 1 32 47 6 5,1,3,4,5,6,7,8,9,10,2,深度优先搜索图,8 3 42 17

48、 6 5,11,8 3 42 17 6 5,8 3 42 1 57 6,8 3 4 2 17 6 5,8 42 3 17 6 5,8 3 42 6 17 5,3 48 2 17 6 5,8 3 47 2 1 6 5,12,13,14,19,18,15,16,3 48 2 17 6 5,17,深度优先搜索图（续）,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,8 32 1 47 6 5,2 8 37 1 4 6 5,2 31 8 47 6 5,8 32 1 47 6 5,2 8 37 1 46 5,1 2 3 8 47 6 5,8 32 1 47 6 5,8 1 32 47 6 5,2 8 37 46 1 5,2 8 37 1 46 5,1 2 38 47 6 5,1,3,4,5,6,7,14,8,11,16,9,10,12,13,17,有界深度优先搜索图 dm=4 go2,2,解的路径：13141617,