人工智能第二章下课件

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

启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导 搜索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。启发性信息评估函数启发式搜索概念启发式搜索与无信息搜索2评估函数的表示含义：用于估价节点重要性的函数称为估价函数表示：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)=2c(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代价树：边上标有代价的搜索树s0ACB324s0ABC234代价的计算边代价：从父节点到子节点的代价s0ACB324s042.4.1代价驱动的搜索策略代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索2.4.1代价驱动的搜索策略代价树的广度优先搜索5代价树的广度优先搜索基本思想搜索过程实例存在问题解决方法(动态规划法）代价树的广度优先搜索基本思想6基本思想open表的节点顺序按的节点代价排列（从小到大）基本思想open表的节点顺序按的节点代价排列（从小到大）7搜索过程1.将初始节点s0放入OPEN表,令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺序），然后转（2）步。搜索过程1.将初始节点s0放入OPEN表,令g(s0)=08例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用代宽演示.pptSADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中9代价树的广度优先搜索（例）1234567101112138919202115171814S(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)16D3(14)F3(16)B4(15)F2(14)C3(17)A3(15)C2(15)34445552454224544443代价树的广度优先搜索（例）1234567101112138910Open表（代价树的广度优先搜索）初始(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))14T1(13)为目标节点，结束。Open表（代价树的广度优先搜索）11算法讨论存在问题改进方法算法讨论存在问题12动态规划法基本思想搜索过程实例动态规划法基本思想13基本思想当有多条到达某一公共节点的路径，只保留代价最小的路径基本思想当有多条到达某一公共节点的路径，只保留代价最小的路径14搜索过程1.将初始节点s0放入OPEN表,令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，若新出现的节点是多条路径都到达的节点，则只选代价最小的路径，其余删去，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺），然后转（2）步。搜索过程1.将初始节点s0放入OPEN表,令g(s0)=015例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用动态规划.pptSADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中16动态规划法（例）123456710118914S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(11)E2(12)34445555423B2(11)动态规划法（例）123456710118914S(0)D1(17Open表（动态规划法）初始(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结束Open表（动态规划法）18代价树的深度优先搜索基本思想搜索过程实例算法讨论代价树的深度优先搜索基本思想19基本思想：在刚扩展的子节点中选择一个代价最小的节点进行扩展，即表的首部存放刚扩展的所有子节点（按代价从小到大排序）搜索过程：1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点按代价从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。基本思想：在刚扩展的子节点中选择一个代价最小的节点进行扩展，20例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用SADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中21代价树的深度优先搜索（例）123456789S(0)D1(4)A1(3)B1(7)D2(8)C1(11)E1(12)D3(14)F1(16)3444552410T1(19)代价树的深度优先搜索（例）123456789S(0)D1(422Open表（代价树的深度优先搜索）初始(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))8T1(19）为目标节点结束Open表（代价树的深度优先搜索）23283147652831476523184765283147652831647583214765283714651（0）3(1)4(1)5(1)7(2)例2代价树的深度优先搜索（括号中为代价）2（1）6(2)832147659(4)832147658132476510(4)8(3)283283232832838248132476513824765813724651238476515(6)（例2续）11(5)解的路径：1-2-6-8-10-11-14-16-1814(6)1382476517(8)1382476516(7)813247658132647512(5)13(5)18(8)8131381312315(6)（例2续2528314765283147652318476528314765283164751（0）3(1)4(1)5(1)例2换一条路径2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）26算法讨论存在的问题解决方法算法讨论存在的问题27代价树的有界深度优先搜索基本思想搜索过程实例代价树的有界深度优先搜索基本思想28基本思想当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。基本思想当一个节点被扩展后，按f(x)对每一个子节点计算估值29代价树的有界深度优先搜索过程1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.IFd(n)=规定深度THENGO(2)7.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。代价树的有界深度优先搜索过程1.将初始节点放入OPEN表，令30例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用SADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中31代价树的有界深度优先搜索（例）dm=412345131467101516891114S(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)代价树的有界深度优先搜索（例）dm=4123451314632代价树搜索的总结优点不足：局限性代价树搜索的总结优点3328314765283147652318476528314765283164751（0）3(1)4(1)5(1)九宫问题使用代价的局限性2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）342.4.2A算法启发性函数A算法A*算法算法讨论2.4.2A算法启发性函数35启发性函数的表示含义：用于估价节点重要性的函数称为估价函数表示：f(x)=g(x)+h(x)g(x)是从初始结点S0到x实际代价h(x)是从x到目标结点Sg的最佳路径的估计代价,启发性信息的函数描述。例重排九宫问题启发性函数的表示含义：用于估价节点重要性的函数称为估价函数36例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件则空格左移R2:如果满足条件则空格上移R3:如果满足条件则空格右移R4:如果满足条件则空格下移注：条件指有位置并且不重复冲突解决方法：算符序号28314765

12384765例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八37解：f(n)=d(n)+W(n)取g(n)=d(n)，h(n)=W(n)。d(n)表示节点n在搜索树中的深度它说明是用从S0到n的路径上的单位代价表示实际代价，W(n)表示节点n中“不在位”的数码个数，作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。对初始节点S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=32

831476512384765S0Sg解：f(n)=d(n)+W(n)取g(n)=d(38希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。希望：39A算法概述概念：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。

由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。全局择优：从Open表的所有节点中选择一个估价函数值最小的一个进行扩展。局部择优：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。A算法概述概念：40局部择优A算法基本思想：当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。搜索过程：1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。局部择优A算法基本思想：当一个节点被扩展后，按f(x)对每一41局部择优A算法例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件则空格左移R2:如果满足条件则空格上移R3:如果满足条件则空格右移R4:如果满足条件则空格下移注：条件指有位置并且不重复冲突解决方法：算符序号28314765

12384765局部择优A算法例：重排九宫问题例：重排九宫问题。在3×3的方42

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=32

831476512384765S0Sgf(n)=d(n)+W(n)。2843283147652831476523184765283147652831647583214765283714651（3）3(4)4(5)5(5)7(6)局部择优A算法，例2（4）6(5)832147659(8)832147658132476510(7)8(6)283283232832838448132476513824765813724651238476515(10)局部择优A算法，例(续）11(8)解的路径：1-2-6-8-10-11-14-16-1814(9)1382476517(10)1382476516(8)813247658132647512(9)13(9)18(8)8131381312315(10)局部择45算法讨论局部择优A算法存在的问题解决方法算法讨论局部择优A算法存在的问题46限界局部择优A算法法1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.IFd(n)=规定深度THENGO(2)7.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。限界局部择优A算法法1.将初始节点放入OPEN表，令g(s047限界局部择优：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件则空格左移R2:如果满足条件则空格上移R3:如果满足条件则空格右移R4:如果满足条件则空格下移注：条件指有位置并且不重复冲突解决方法：算符序号f(x)=d(x)+h(x)d(x):节点x的深度，深度=4h(x):节点x的格局与目标节点格局不相同的牌数。28314765

12384765限界局部择优：重排九宫问题例：重排九宫问题。在3×3的方格棋48283147652831476523184765283147652831647583214765283714651（3）3(4)4(5)5(5)7(6)限界局部择优搜索（例）d=42（4）6(5)832147659(9)832147658132476510(8)8(6)231847652318476514(4)1238476512384765123784652837146511(8)283746152837146512(9)13(10)15(6)18(6)16(4)17(4)28328323283283849Open表的变化(限界局部择优搜索法）初始(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),3(4),4(5),5(5))4(10(8),9(9),7(6),3(4),4(5),5(5))d=45(7(6),3(4),4(5),5(5))d=26(11(8),3(4),4(5),5(5))d=37(12(9),13(10),3(4),4(5),5(5))d=48(3(4),4(5),5(5))d=19(14(4),15(6),4(5),5(5))d=27(16(4),15(10),3(4),4(5),5(5))d=38(17(4),18(6),15(10),3(4),4(5),5(5))d=4917(4)为目标节点，结束

Open表的变化(限界局部择优搜索法）50算法讨论局部择优搜索方法评价与深度优先搜索比较缺陷算法讨论局部择优搜索方法评价51全局择优搜索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)根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；

(8)转第(2)步。

全局择优搜索A算法描述(1)把初始节点S0放入Open表中，52例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件则空格左移R2:如果满足条件则空格上移R3:如果满足条件则空格右移R4:如果满足条件则空格下移注：条件指有位置并且不重复冲突解决方法：算符序号f(x)=d(x)+h(x)d(x):节点x的深度，h(x):节点x的格局与目标节点格局不相同的牌数。28314765

12384765例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八5328314765283147652318476528314765283164758321476528371465231847652318476512384765123847651（3）3(4)4(5)5(5)7(6)A算法（例）2（4）解的路径：1－3－8－10－116(5)8(4)9(6)10(4)1237846511(4)12(6)28328323283283854Open表的变化(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))611(4)为目标节点，结束

Open表的变化(A算法）55算法讨论全局择优搜索A算法评价：如何找到最优解.算法讨论全局择优搜索A算法评价：56目标寻找最佳全局搜索算法A*A*算法总能找到最优解使扩展结点数尽量少方法：对启发式函数进行限制目标寻找最佳全局搜索算法A*57目标1：算法的可采纳性在问题有解的情况下，若一个搜索过程总能找到最优解，则称该算法具有可采纳性。可采纳性的衡量：f*(n)=g*(n)+h*(n)例重排九宫问题f(x)=d(x)+h(x)

h1(x)=0

h2(x):错位棋牌的个数h3(x):每个将牌与其目标位置之间的距离和2831476512384765目标1：算法的可采纳性在问题有解的情况下，若一个搜索过程总能5823184765283147652831647583214765283714652318476523184765281437652831457683214765283714651238476523418765281437652831457628364175283167548321476581324765283746152837146512384765345283164752831647567891011121314151617181920212324252622234185762341876528143765248137652831457628315746281437652481376528316754281637548342176581324765832147658132476528374615237846152837461528371654解的路径：1－3－8－16－26283147652272829303132333435363738394041424344283147651A*算法（例h1(x)=0<=h*(n))扩展节点数：25生成节点数：44232832838328325928314765283147652318476528314765283164758321476528371465231847652318476512384765123847651（3）3(4)4(5)5(5)7(6)A*算法(例)h2(x)=w(x）<=h*(n)2（4）解的路径：1－3－8－10－116(5)8(4)9(6)10(4)1237846511(4)12(6)扩展节点数：10生成节点数：12283283232832838602831476528314765231847652831476528316475231847652318476512384765123847651（4）3(4)4(6)5(6)A*算法(例)h3(x)=p(x)<=h(n)2（6）解的路径：1－3－6－8－96(4)7(6)8(4)123784659(4)10(6)扩展节点数：4生成节点数：10283283232832832612831476528314765231847652831476528316475231847652318476512384765123847651h*=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=2f=4h*=1,g*=3W=1P=1,f=412378465h*=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生成节点数：928328323283283262看出规律了吗？看出规律了吗？63最佳全局搜索算法A*A*算法含义在A算法中，如果满足条件： h(n)≤h*(n) 则A算法称为A*算法。最佳全局搜索算法A*A*算法含义64A*算法的采纳性证明定理(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。证明见书定理4.1、定理4.2、定理4.3A*算法的采纳性证明定理(可采纳性定理)：65A*算法效率问题A*算法评价如何设计搜索算法找到最优解并使扩展的节点数尽可能少.A*算法效率问题A*算法评价66s(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(7)SC(9)SBA(5)SA(7)s(10)SCBA(4)SCB(7)SC(9)

SBA(5)SA(7)s(10)SCBAG(11)s(10)A(1)B(5)C(8)G目标631118另一个67sABCG目标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)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)sABCG目标631118一个例子(无H函数）：OPEN表68目标2：A*算法效率讨论A*算法评价如何设计搜索算法找到最优解并使扩展的节点数尽可能少.目标2：A*算法效率讨论A*算法评价69出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。s(10)A(1)B(5)C(8)G目标631118出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到70解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。解决的途径对h加以限制71改进的条件可采纳性不变不多扩展节点不增加算法的复杂性改进的条件可采纳性不变72对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对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，73实例证明：例1修改h(n)s(10)A(1)B(5)C(8)G目标631118C(9)B(8)A(7)G(0)实例证明：例1修改h(n)s(10)A(1)B(5)C(8)74s(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(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)s(10)A(1)B(5)C(8)G目标631118一个例75理论证明定理4.5如果h满足单调条件，则当A*算法扩展节点n时，该节点就已经找到了通往它的最佳路径，即g(n)=g*(n)。在h(n)满足单调性限制下的A*算法常被称为改进的A*算法。理论证明定理4.5如果h满足单调条件，则当A*算法扩展节点76例2：修改h(n)SADBTC1119163146181h=20h=14h=8h=1h=4h=19h=18h=17h=16h=0例2：修改h(n)SADBTC1119163146181h=77总结：实现启发式搜索的关键算法的完备性算法的可采纳性启发函数强弱对结果的影响总结：实现启发式搜索的关键算法的完备性78算法的完备性

对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题得解，则称该搜索过程为完备的，否则为不完备的。算法的完备性对于一类可解的问题和一个搜索过程，如果运用79算法的可采纳性可纳性的含义：对任一状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。算法的可采纳性可纳性的含义：80启发函数强弱对结果的影响1

启发函数强弱的衡量：h(n)接近h*(n)的程度理想情况：h(n)＝h*(n)，实际上:h(n)<=h*(n)(越接近越好)原因：A*算法的搜索效率很大程度上取决于估价函数h(n)。一般来说，在满足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。启发函数强弱对结果的影响1启发函数强弱的衡量：h(n)接近81启发函数强弱对结果的影响2

h(n)满足单调性限制下的A*算法更好原因：能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径。在h(n)满足单调性限制下的A*算法常被称为改进的A*算法。启发函数强弱对结果的影响2h(n)满足单调性限制下的A*算822.5图搜索策略总结基本思想图搜索分类2.5图搜索策略总结基本思想83状态空间搜索的基本思想先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。状态空间搜索的基本思想先把问题的初始状态作为当前扩展节点84图搜索分类无信息搜索搜索按预定的规则进行，不使用与问题有关的启发式信息启发式搜索搜索中使用与问题有关的启发式信息,并以这些启发式信息指导搜索过程(可以提高效率)图搜索分类无信息搜索85本章小结搜索策略状态空间搜索无信息搜索启发式搜索搜索方法的关系参考第4.1,4.2,4.3节本章小结搜索策略86283147652318476528314765283164758321476528371465231847652318476528143765283145768321476528371465123847652341876528143765283145762836417528316754832147658132476528374615283714651238476513452831647528316475678910111213141516171819202123242526宽度优先搜索图22234185762341876528143765248137652831457628315746281437652481376528316754281637548342176581324765832147658132476528374615237846152837461528371654解的路径：1－3－8－16－26283147652272829303132333435363738394041424344283232832838328872831476528314765231847652831476528316475832147652837146583214765832147658132476513456789102深度优先搜索图28328323283283888834217651183421765834215768342176584231765834261753482176583472165121314191815163482176517深度优先搜索图（续）8341183483483484889283147652831476523184765283147652831647583214765283714652318476583214765283714651238476583214765813247652837461528371465123847651345671481116910121317有界深度优先搜索图dm=4go22解的路径：1－3－14－16－17283283232832838902.4启发式搜索搜索技术的应用－智能搜索引擎启发式搜索涉及的基本概念基本的启发式搜索方法代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索(局部优先搜索)代价树有界深度优先搜索局部择优A算法A算法(全局优先搜索)2.4启发式搜索搜索技术的应用－智能搜索引擎91启发式搜索概念启发式搜索与无信息搜索无信息（盲目）搜索：按预定的控制策略进行搜索，在搜索过程中 获得的中间信息并不改变控制策略。81

启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导 搜索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。启发性信息评估函数启发式搜索概念启发式搜索与无信息搜索92评估函数的表示含义：用于估价节点重要性的函数称为估价函数表示：f(x)=g(x)+h(x)g(x)是从初始结点S0到x实际代价h(x)是从x到目标结点Sg的最佳路径的估计代价,启发性信息的函数描述。例重排九宫问题f(x)=d(x)+h(x)评估函数的表示含义：用于估价节点重要性的函数称为估价函数93代价的计算边代价：从父节点到子节点的代价表示：c(x1,x2)表示从父节点x1到子节点x2的代价例：c(s0,A)=2c(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代价树：边上标有代价的搜索树s0ACB324s0ABC234代价的计算边代价：从父节点到子节点的代价s0ACB324s0942.4.1代价驱动的搜索策略代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索2.4.1代价驱动的搜索策略代价树的广度优先搜索95代价树的广度优先搜索基本思想搜索过程实例存在问题解决方法(动态规划法）代价树的广度优先搜索基本思想96基本思想open表的节点顺序按的节点代价排列（从小到大）基本思想open表的节点顺序按的节点代价排列（从小到大）97搜索过程1.将初始节点s0放入OPEN表,令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺序），然后转（2）步。搜索过程1.将初始节点s0放入OPEN表,令g(s0)=098例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用代宽演示.pptSADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中99代价树的广度优先搜索（例）1234567101112138919202115171814S(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)16D3(14)F3(16)B4(15)F2(14)C3(17)A3(15)C2(15)34445552454224544443代价树的广度优先搜索（例）12345671011121389100Open表（代价树的广度优先搜索）初始(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))14T1(13)为目标节点，结束。Open表（代价树的广度优先搜索）101算法讨论存在问题改进方法算法讨论存在问题102动态规划法基本思想搜索过程实例动态规划法基本思想103基本思想当有多条到达某一公共节点的路径，只保留代价最小的路径基本思想当有多条到达某一公共节点的路径，只保留代价最小的路径104搜索过程1.将初始节点s0放入OPEN表,令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，若新出现的节点是多条路径都到达的节点，则只选代价最小的路径，其余删去，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺），然后转（2）步。搜索过程1.将初始节点s0放入OPEN表,令g(s0)=0105例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用动态规划.pptSADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中106动态规划法（例）123456710118914S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(11)E2(12)34445555423B2(11)动态规划法（例）123456710118914S(0)D1(107Open表（动态规划法）初始(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结束Open表（动态规划法）108代价树的深度优先搜索基本思想搜索过程实例算法讨论代价树的深度优先搜索基本思想109基本思想：在刚扩展的子节点中选择一个代价最小的节点进行扩展，即表的首部存放刚扩展的所有子节点（按代价从小到大排序）搜索过程：1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点按代价从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。基本思想：在刚扩展的子节点中选择一个代价最小的节点进行扩展，110例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用SADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中111代价树的深度优先搜索（例）123456789S(0)D1(4)A1(3)B1(7)D2(8)C1(11)E1(12)D3(14)F1(16)3444552410T1(19)代价树的深度优先搜索（例）123456789S(0)D1(4112Open表（代价树的深度优先搜索）初始(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))8T1(19）为目标节点结束Open表（代价树的深度优先搜索）113283147652831476523184765283147652831647583214765283714651（0）3(1)4(1)5(1)7(2)例2代价树的深度优先搜索（括号中为代价）2（1）6(2)832147659(4)832147658132476510(4)8(3)2832832328328381148132476513824765813724651238476515(6)（例2续）11(5)解的路径：1-2-6-8-10-11-14-16-1814(6)1382476517(8)1382476516(7)813247658132647512(5)13(5)18(8)8131381312315(6)（例2续11528314765283147652318476528314765283164751（0）3(1)4(1)5(1)例2换一条路径2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）116算法讨论存在的问题解决方法算法讨论存在的问题117代价树的有界深度优先搜索基本思想搜索过程实例代价树的有界深度优先搜索基本思想118基本思想当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。基本思想当一个节点被扩展后，按f(x)对每一个子节点计算估值119代价树的有界深度优先搜索过程1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.IFd(n)=规定深度THENGO(2)7.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。代价树的有界深度优先搜索过程1.将初始节点放入OPEN表，令120例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用SADEBFTC344525443例如图是八城市间的交通图，两城市间的交通费用（代价）如图中121代价树的有界深度优先搜索（例）dm=412345131467101516891114S(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)代价树的有界深度优先搜索（例）dm=41234513146122代价树搜索的总结优点不足：局限性代价树搜索的总结优点12328314765283147652318476528314765283164751（0）3(1)4(1)5(1)九宫问题使用代价的局限性2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）1242.4.2A算法启发性函数A算法A*算法算法讨论2.4.2A算法启发性函数125启发性函数的表示含义：用于估价节点重要性的函数称为估价函数表示：f(x)=g(x)+h(x)g(x)是从初始结点S0到x实际代价h(x)是从x到目标结点Sg的最佳路径的估计代价,启发性信息的函数描述。例重排九宫问题启发性函数的表示含义：用于估价节点重要性的函数称为估价函数126例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件则空格左移R2:如果满足条件则空格上移R3:如果满足条件则空格右移R4:如果满足条件则空格下移注：条件指有位置并且不重复冲突解决方法：算符序号28314765

12384765例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八127解：f(n)=d(n)+W(n)取g(n)=d(n)，h(n)=W(n)。d(n)表示节点n在搜索树中的深度它说明是用从S0到n的路径上的单位代价表示实际代价，W(n)表示节点n中“不在位”的数码个数，作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。对初始节点S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=32

831476512384765S0Sg解：f(n)=d(n)+W(n)取g(n)=d(128希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。希望：129A算法概述概念：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。

由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。全局择优：从Open表的所有节点中选择一个估价函数值最小的一个进行扩展。局部择优：仅从刚生成的子节点中选择一个估价函数值最小的一个