人工智能第二章下.ppt

《人工智能第二章下.ppt》由会员分享，可在线阅读，更多相关《人工智能第二章下.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.4启发式搜索搜索技术的应用智能搜索引擎搜索技术的应用智能搜索引擎启发式搜索涉及的基本概念启发式搜索涉及的基本概念基本的启发式搜索方法基本的启发式搜索方法代价树的广度优先搜索代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索代价树的深度优先搜索(局部优先搜索局部优先搜索)代价树代价树有界深度优先搜索有界深度优先搜索局部择优局部择优A算法算法A算法算法(全局优先搜索全局优先搜索)启发式搜索概念启发式搜索与无信息搜索无信息（盲目）搜索：按预定的控制策略进行搜索，在搜索过程中无信息（盲目）搜索：按预定的控制策略进行搜索，在搜索过程中

2、获得的中间信息并不改变控制策略。获得的中间信息并不改变控制策略。81 启发式搜索：在搜索中加入了启发式搜索：在搜索中加入了与问题有关的启发性信息与问题有关的启发性信息，用于指导，用于指导 搜索朝着搜索朝着最有希望的方向前进最有希望的方向前进，加速问题的求解过程并，加速问题的求解过程并 找到最优解。找到最优解。启发性信息评估函数评估函数的表示含义：用于估价节点重要性的函数称为估价函数表示：f(x)=g(x)+h(x)g(x)是从初始结点S0到x实际代价h(x)是从x到目标结点Sg的最佳路径的估计代价,启发性信息的函数描述。例 重排九宫问题 f(x)=d(x)+h(x)代价的计算边代价：从父节点到

3、子节点的代价表示：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代价树：边上标有代价的搜索树s0ACB324s0ABC2342.4.1 代价驱动的搜索策略代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索代价树的广度优先搜索基本思想搜索过程实例存在问题解决方法(动态规划法）基本思想open表的节点顺序按的节点代价排列（从小到大）搜

4、索过程1.将初始节点将初始节点s0s0放入放入OPENOPEN表表,令令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.5.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。6.6.扩展节点扩展节点n n，将其子节点放入将其子节点放入OPENOPEN表中，并为每一个子表中，

5、并为每一个子节点都配置指向父节点的指针；节点都配置指向父节点的指针；计算各个子节点的代计算各个子节点的代价，并按各个节点的代价对表的全部节点进行排序价，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺序），（按从小到大的顺序），然后转（然后转（2 2）步。）步。例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用代宽演示.pptSADEBFTC344525443代价树的广度优先搜索（例）1234567101112138919202115171814S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(

6、11)B2(11)B3(13)E3(10)E2(12)16D3(14)F3(16)B4(15)F2(14)C3(17)A3(15)C2(15)34445552454224544443Open表（代价树的广度优先搜索）初始(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

7、(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

8、),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16),C3(17)14 T1(13)为目标节点，结束。算法讨论存在问题改进方法动态规划法动态规划法基本思想搜索过程实例基本思想当有多条到达某一公共节点的路径，只保留代价最小的路径搜索过程1.将初始节点将初始节点s0s0放入放入OPENOPEN表表,令令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n

9、n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.5.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。6.6.扩展节点扩展节点n n，将其子节点放入将其子节点放入OPENOPEN表中，并为每一个子表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代节点都配置指向父节点的指针；计算各个子节点的代价，价，若新出现的节点是多条路径都到达的节点，则只若新出现的节点是多条路径都到达的节点，则只选代价最小的路径，其余删去，选代价最小的路径，其余删去，并按各个节点的代价并按各个节点的代价对表的全部节点进行排序（按从小到大的顺），然后对表

10、的全部节点进行排序（按从小到大的顺），然后转（转（2 2）步。）步。例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用动态规划.pptSADEBFTC344525443动态规划法（例）123456710118914S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(11)E2(12)34445555423B2(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)

11、5(F1(10),C1(11),E2(12)6(C1(11),T1(13)7(T1(13)8 结束 代价树的深度优先搜索基本思想搜索过程实例算法讨论基本思想基本思想：在刚扩展的子节点中选择一个代价最小的在刚扩展的子节点中选择一个代价最小的节点进行扩展，即表的首部存放刚扩展的所有子节点节点进行扩展，即表的首部存放刚扩展的所有子节点（按代价从小到大排序）（按代价从小到大排序）搜索过程：搜索过程：1.将初始节点放入将初始节点放入OPENOPEN表，令表，令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个

12、节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.5.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。6.6.扩展节点扩展节点n n，将其子节点将其子节点按代价从小到大放入按代价从小到大放入OPENOPEN表的表的首部，首部，并为每一个子节点都配置指向父节点的指针，并为每一个子节点都配置指向父节点的指针，然后转（然后转（2 2）步。）步。例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T

13、的最小交通费用SADEBFTC344525443代价树的深度优先搜索（例）123456789S(0)D1(4)A1(3)B1(7)D2(8)C1(11)E 1(12)D3(14)F1(16)3444552410T1(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

14、 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 51（0）3(1)4(1)5(1)7(2)例例2代价树的深度优先搜索（括号中为代价）2（1）6(2)8 32 1 47 6 59(4)8 32 1 47 6 58 1 32 47 6 510(4)8(3)8 1 3 2 47 6 5 1 38 2 47 6 58 1 37 2 4 6 51 2 38 47 6 515(6)（例（例2续）续）11(5)解的路径：1-2-6-8-10-11-14-16-1814(6)1

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

16、思想当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。代价树的有界深度优先搜索过程1.将初始节点放入将初始节点放入OPENOPEN表，令表，令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（表的第一个节点（记为记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.5.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。6

17、.IF 6.IF d(n)=d(n)=规定深度规定深度 THEN GO(2)THEN GO(2)7.7.扩展节点扩展节点n n，用估价函数用估价函数f(x)f(x)计算计算每个子节点的估价值，每个子节点的估价值，并将其子节点按估价值从小到大放入并将其子节点按估价值从小到大放入OPENOPEN表的首部，表的首部，并为每一个子节点都配置指向父节点的指针，然后转并为每一个子节点都配置指向父节点的指针，然后转（2 2）步）步。例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用SADEBFTC344525443代价树的有界深度优先搜索（例）dm=4123451

18、31467101516891114S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E3(6)F3(10)T1(13)C1(11)E2(10)E1(12)12D3(14)F1(16)B2(15)F2(14)3444555254224543B3(11)代价树搜索的总结优点不足：局限性2 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 51（0）3(1)4(1)5(1)九宫问题使用代价的九宫问题使用代价的局限性局限性2（1）2 31 8 47 6 52 31 8 47 6 56(2)1 2 3 8 47 6 51

19、 2 38 47 6 51 2 37 8 4 6 57(2)10(4)8(3)9(4)2.4.2 A算法启发性函数A算法算法A*算法算法讨论启发性函数的表示含义：用于估价节点重要性的函数称为估价函数表示：f(x)=g(x)+h(x)g(x)是从初始结点S0到x实际代价h(x)是是从从x到到目目标标结结点点Sg的的最最佳佳路路径径的的估估计计代价代价,启发性信息的函数描述。启发性信息的函数描述。例 重排九宫问题例：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件 则 空格左移R2:如果满足条件 则 空格上移R3:如果满足条件 则 空格

20、右移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的的路路径径上上的单位代价表示实际代价，的单位代价表示实际代价，W(n)表示节点表示节点n中中“不在位不在位”的数码个数，作为启发信息。的数码个数，作为启发信息。一一般般来来说说，某某节节点点中中的的“不不在在位位”的的数数码码个个数数越越多多，说说明明它它离目标节点越远。离目标节点越

21、远。对初始节点对初始节点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

22、算法也被算法也被称为启发式搜索算法。称为启发式搜索算法。类型：类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。全局择优搜索算法和局部择优搜索算法。全局择优：全局择优：从从Open表的所有节点中选择一个估价函数值最小的表的所有节点中选择一个估价函数值最小的一个进行扩展。一个进行扩展。局部择优：局部择优：仅从刚生成的子节点中选择一个仅从刚生成的子节点中选择一个估价函数值最小的一估价函数值最小的一个进行扩展。个进行扩展。局部择优A算法基本思想基本思想：当一个节点被扩展后，按当一个节点被扩展后，按

23、f(x)对每一个子节点对每一个子节点计算估值，并选择其中最小的先扩展。计算估值，并选择其中最小的先扩展。搜索过程：搜索过程：1.1.将初始节点放入将初始节点放入OPENOPEN表，令表，令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.5.若节点若节点n n不可扩展转（不可扩展转（2

24、 2）步。）步。6.6.扩展节点扩展节点n n，用估价函数用估价函数f(x)f(x)计算计算每个子节点的估价值，每个子节点的估价值，并将其子节点按估价值从小到大放入并将其子节点按估价值从小到大放入OPENOPEN表的首部表的首部，并，并为每一个子节点都配置指向父节点的指针，然后转（为每一个子节点都配置指向父节点的指针，然后转（2 2）步步。局部择优A算法例：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件 则 空格左移R2:如果满足条件 则 空格上移R3:如果满足条件 则 空格右移R4:如果满足条件 则 空格下移注：条件指有位置并且

25、不重复冲突解决方法：算符序号2 8 31 47 6 5 1 2 3 8 47 6 5 f(n)=d(n)+W(n)。d(n)表表示示节节点点n在在搜搜索索树树中中的的深深度度它它说说明明是是用用从从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 Sg2 8 31 47 6 52 8 3 1 47 6 52 3

26、1 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 51（3）3(4)4(5)5(5)7(6)局部择优局部择优A算法，例算法，例2（4）6(5)8 32 1 47 6 59(8)8 32 1 47 6 58 1 32 47 6 510(7)8(6)8 1 3 2 47 6 5 1 38 2 47 6 58 1 37 2 4 6 51 2 38 47 6 515(10)局部择优局部择优A算法，例算法，例(续）续）11(8)解的路径：1-2-6-8-10-11-14-16-1814(9)1 38 2 47 6 517(10)

27、1 38 2 47 6 516(8)8 1 32 47 6 58 1 32 6 47 512(9)13(9)18(8)算法讨论局部择优A算法存在的问题解决方法限界局部择优A算法法1.将初始节点放入将初始节点放入OPENOPEN表，令表，令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（表的第一个节点（记为记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5

28、.5.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。6.IF 6.IF d(n)=d(n)=规定深度规定深度 THEN GO(2)THEN GO(2)7.7.扩展节点扩展节点n n，用估价函数用估价函数f(x)f(x)计算计算每个子节点的估价值，每个子节点的估价值，并将并将其子节点按估价值从小到大放入其子节点按估价值从小到大放入OPENOPEN表的首部表的首部，并为每一个子节点都配置指向父节点的指针，然后转并为每一个子节点都配置指向父节点的指针，然后转（2 2）步）步。限界局部择优：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:

29、如果满足条件 则 空格左移R2:如果满足条件 则 空格上移R3:如果满足条件 则 空格右移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 52 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 51（3）3(4)4(5)5(5)7(6)限界局部择优搜索限界局部择优搜索（例

30、）（例）d=42（4）6(5)8 32 1 47 6 59(9)8 32 1 47 6 58 1 32 47 6 510(8)8(6)2 31 8 47 6 52 31 8 47 6 514(4)1 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 52 8 37 1 46 511(8)2 8 37 46 1 52 8 37 1 46 512(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

31、),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)为目标节点，结束 算法讨论局部择优搜索方法评价与深度优先搜索

32、比较缺陷全局择优搜索全局择优搜索A A算法描述算法描述(1)(1)把初始节点把初始节点S0放入放入Open表中，表中，f(S0)=g(S0)+h(S0)；(2)(2)如果如果Open表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点表，并记该节点为为n；(4)(4)考察节点考察节点n是否为目标节点。若是，则找到问题的解，成功退出；是否为目标节点。若是，则找到问题的解，成功退出；(5)(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)(6)扩展节点扩展节点n，生成其子节点

33、生成其子节点ni(i=1,2,)，计算每一个子节点的计算每一个子节点的估价值估价值f(ni)(i=1,2,)，并为每一个子节点设置指向父节点的指并为每一个子节点设置指向父节点的指针，然后将这些子节点放入针，然后将这些子节点放入Open表中；表中；(7)(7)根据各节点的估价函数值，根据各节点的估价函数值，对对Open表中的全部节点按从小到大表中的全部节点按从小到大的顺序重新进行排序；的顺序重新进行排序；(8)(8)转第转第(2)步。步。例：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件 则 空格左移R2:如果满足条件 则 空格上移

34、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 52 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51（3）3(4)4(5)5(5)7

35、(6)A算法（例）算法（例）2（4）解的路径：13810116(5)8(4)9(6)10(4)1 2 37 8 4 6 511(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),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算法评价：如何找到最优解.目标寻找最佳全局搜索算法寻找最佳

36、全局搜索算法A*A*算法总能找到最优解算法总能找到最优解使扩展结点数尽量少使扩展结点数尽量少方法：方法：对启发式函数进行限制对启发式函数进行限制目标1：算法的可采纳性在问题有解的情况下，若一个搜索过程总能找在问题有解的情况下，若一个搜索过程总能找到最优解，则称该算法具有可采纳性。到最优解，则称该算法具有可采纳性。可采纳性的衡量：可采纳性的衡量：f*(n)=g*(n)+h*(n)f*(n)=g*(n)+h*(n)例例 重排九宫问题重排九宫问题 f(x)=d(x)+h(x)f(x)=d(x)+h(x)h1(x)=0 h2(x):错位棋牌的个数错位棋牌的个数h3(x):h3(x):每个将牌与其目标位

37、置之间的距离和每个将牌与其目标位置之间的距离和 2 8 31 47 6 51 2 38 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 6 8 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 1 4 37 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 58 1 32 4

38、7 6 52 8 37 46 1 52 8 37 1 46 51 2 38 47 6 53452 8 31 6 4 7 52 8 31 6 47 5678910111213141516171819202123242526222 3 41 8 57 62 3 41 87 6 5 2 8 1 4 37 6 52 4 8 1 37 6 52 8 31 4 5 7 62 8 31 57 4 6 2 8 1 4 37 6 52 4 8 1 37 6 52 8 31 67 5 42 8 1 6 3 7 5 48 3 42 1 7 6 58 1 3 2 47 6 58 32 1 47 6 58 1 32 4

39、7 6 52 8 3 7 46 1 52 37 8 46 1 52 8 37 46 1 52 8 37 1 6 5 4解的路径：13816262 8 3 1 47 6 522728293031323334353637383940414243442 8 31 47 6 51A*算法（例算法（例 h1(x)=0=h*(n)扩展节点数：25生成节点数：442 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 51 2

40、 3 8 47 6 51 2 38 47 6 51（3）3(4)4(5)5(5)7(6)A*算法算法(例例)h2(x)=w(x）=h*(n)2（4）解的路径：13810116(5)8(4)9(6)10(4)1 2 37 8 4 6 511(4)12(6)扩展节点数：10生成节点数：122 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51（4）3(4)4(6)5(6)A*算法算法(例例)h3(x)=p(x)=

41、h(n)2（6）解的路径：136896(4)7(6)8(4)1 2 37 8 4 6 59(4)10(6)扩展节点数：4生成节点数：102 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51h*=4,g*=1W=3P=3,f=4启发式函数比较启发式函数比较(例例)h2(x)=w(x)h3(x)=p(x)W=3P=5,f=6h*=2,g*=2W=3 P=2 f=4h*=1,g*=3W=1P=1,f=41 2 3

42、7 8 4 6 5h*=4,g*=0W=3P=4,f=436289h*=0,g*=4W=0P=0,f=44W=4P=5,f=65W=4P=5,f=67W=4P=4,f=610W=2P=2,f=6扩展节点数：4生成节点数：9最佳全局搜索算法A*A*算法含义算法含义在在A算法中，如果满足条件：算法中，如果满足条件：h(n)h*(n)则则A算法称为算法称为A*算法。算法。A*算法的采纳性证明定理(可采纳性定理)：若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。证明见书证明见书定理定理4.1、定理、定理4.2、定理、定理4.3A*算法效率问题A*算法评价如何设计搜索算法找到最优解并使扩

43、展的节点数尽可能少.s(10)A(1)B(5)C(8)G 目标目标631118另一个例子另一个例子(有有h(n)h*(n)函数）：函数）：OPEN表表CLOSED表表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)SBAG(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

44、(7)SC(9)SBA(5)SA(7)s(10)SCBA(4)SCB(7)SC(9)SBA(5)SA(7)s(10)SCBAG(11)sABCG 目标目标631118一个例子一个例子(无无H函数）：函数）：OPEN表表CLOSED表表s(10)s(10)SC(1)SB(3)SA(6)SC(1)s(10)SCB(2)SB(3)SA(6)SCBA(3)SB(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)S

45、C(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*算法评价如何设计搜索算法找到最优解并使扩展的节点数尽可能少.出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。s(10)A(1)B(5)C(8)G 目标631118解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。改进的条件可采纳性不变不多扩展节点不增加算法

46、的复杂性对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是单调的。njh(nj)h(ni)nic(ni,nj)h(n)t实例证明：例1修改h(n)s(10)A(1)B(5)C(8)G 目标631118C(9)B(8)A(7)G(0)s(10)A(1)B(5)C(8)G 目标631118一个例子(修改后h(n)：OPEN表CLOSED表s(10)s(10)SC(10)SB(11)SA(13)SC(10)s(10)SCB(10)SB

47、(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*算法常被算法常被称为改进的称为改进的A*算法。算法。例2：修改h(n)SADBTC1119163146181h

48、=20h=14h=8h=1h=4h=19h=18h=17h=16h=0总结：实现启发式搜索的关键算法的完备性算法的可采纳性启发函数强弱对结果的影响算法的完备性 对于一类对于一类可解的可解的问题和一个搜索过程，问题和一个搜索过程，如果运用该搜索过程如果运用该搜索过程一定能求得该类问一定能求得该类问题得解题得解，则称该搜索过程为完备的，否，则称该搜索过程为完备的，否则为不完备的。则为不完备的。算法的可采纳性可纳性的含义：可纳性的含义：对任一状态空间图，当从初始节点到目标节点对任一状态空间图，当从初始节点到目标节点有路径存在有路径存在时，如果搜索算法总能在时，如果搜索算法总能在有限步骤有限步骤内内找

49、到一条从初始节点到目标节点的找到一条从初始节点到目标节点的最佳路径最佳路径，并在此路径上结束，则称该搜索算法是可采纳并在此路径上结束，则称该搜索算法是可采纳的。的。启发函数强弱对结果的影响1 启发函数强弱的衡量：h(n)接近h*(n)的程度理想情况：h(n)h*(n)，实际上:h(n)=h*(n)(越接近越好)原因：A*算法的搜索效率很大程度上取决于估算法的搜索效率很大程度上取决于估价函数价函数h(n)。一般来说，在满足。一般来说，在满足h(n)h*(n)的的前提下，前提下，h(n)的值越大越好。的值越大越好。h(n)的值越大，的值越大，说明它携带的启发性信息越多，说明它携带的启发性信息越多，

50、A*算法搜索时算法搜索时扩展的节点就越少，搜索效率就越高。扩展的节点就越少，搜索效率就越高。启发函数强弱对结果的影响2 h(n)满足单调性限制下的满足单调性限制下的A*算法更好算法更好原因：原因：能够保证，每当扩展一个节点时能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径。就已经找到了通往这个节点的最佳路径。在在h(n)满足单调性限制下的满足单调性限制下的A*算法常被算法常被称为改进的称为改进的A*算法。算法。2.5图搜索策略总结基本思想图搜索分类状态空间搜索的基本思想状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点对其进行扩先把问题的初始状态作为当前扩展节点对其进行扩