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 代价驱动的搜索策略 代价树的广度优先搜索 动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索代价树的广度优先搜索 基本思想 搜索过程 实例 存在问题 解决方法(动态规划法）基本思想 ope
4、n表的节点顺序按的节点代价排列（从小到大）搜索过程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，将其子节点放入，将其子节
5、点放入OPENOPEN表中，并为每一个子表中，并为每一个子节点都配置指向父节点的指针；节点都配置指向父节点的指针；计算各个子节点的代计算各个子节点的代价，并按各个节点的代价对表的全部节点进行排序价，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺序），（按从小到大的顺序），然后转（然后转（2 2）步。）步。例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用代宽演示.pptSADEBFTC344525443代价树的广度优先搜索（例）1234567101112138919202115171814S(0)D1(4)A1(3)B1(7)D2(8)A2
6、(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)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),C
7、1(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
8、),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.将初始节点将初始节点s0s0放入放入OPENOPEN表表,令令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放
9、入CLOSEDCLOSED表表4.4.考察节点考察节点n 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
11、(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.将初始节点放入将初始节点放入OPENOPEN表，令表，令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无
12、解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.5.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。6.6.扩展节点扩展节点n n，将其子节点，将其子节点按代价从小到大放入按代价从小到大放入OPENOPEN表的表的首部，首部，并为每一个子节点都配置指向父节点的指针，并为每一个子节点都配置指向父节点的指针，然后转（然后转（2 2）步。）步。例 如图
13、是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用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(
14、T1(19),D2(8),D1(4)8 T1(19）为目标节点结束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 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(
15、5)解的路径：1-2-6-8-10-11-14-16-1814(6)1 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是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解
17、，退出。退出。5.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）步）步。例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费
18、用SADEBFTC344525443代价树的有界深度优先搜索（例）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)代价树搜索的总结 优点 不足：局限性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）
19、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)2.4.2 A算法 启发性函数 A算法算法 A*算法 算法讨论启发性函数的表示 含义：用于估价节点重要性的函数称为估价函数 表示：f(x)=g(x)+h(x)g(x)是从初始结点S0到x实际代价 h(x)是从是从x到目标结点到目标结点Sg的最佳路径的估计的最佳路径的估计代价代价,启发性信息的函数描述。启发性信息的函数描述。例 重排九宫问题例：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如
20、右图 算符有：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的路径上的路径上的单位代价表示实际代价，的单位代价表示实际代价，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表中的节点进行排序，则该搜索算法为表中的节点进行排序
22、，则该搜索算法为A算算法。法。由于估价函数中带有问题自身的启发性信息，因此，由于估价函数中带有问题自身的启发性信息，因此，A算法也被算法也被称为启发式搜索算法。称为启发式搜索算法。类型：类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。全局择优搜索算法和局部择优搜索算法。全局择优：全局择优：从从Open表的所有节点中选择一个估价函数值最小的表的所有节点中选择一个估价函数值最小的一个进行扩展。一个进行扩展。局部择优：局部择优：仅从刚生成的子节点中选择一个仅从刚生成的子节点中选择一个估价函数值最
23、小的一估价函数值最小的一个进行扩展。个进行扩展。局部择优A算法 基本思想基本思想：当一个节点被扩展后，按当一个节点被扩展后，按f(x)对每一个子节点对每一个子节点计算估值，并选择其中最小的先扩展。计算估值，并选择其中最小的先扩展。搜索过程：搜索过程：1.1.将初始节点放入将初始节点放入OPENOPEN表，令表，令g(s0)=0g(s0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若
24、是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.5.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。6.6.扩展节点扩展节点n n，用估价函数，用估价函数f(x)f(x)计算每个子节点的估价值，计算每个子节点的估价值，并将其子节点按估价值从小到大放入并将其子节点按估价值从小到大放入OPENOPEN表的首部表的首部，并，并为每一个子节点都配置指向父节点的指针，然后转（为每一个子节点都配置指向父节点的指针，然后转（2 2）步步。局部择优A算法例：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图 算符有：R1:如果满足条件
25、 则 空格左移 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在搜索树中的深度它说明是用从在搜索树中的深度它说明是用从S0到到n的路径上的路径上的单位代价表示实际代价，的单位代价表示实际代价，W(n)表示节点表示节点n中中“不在位不在位”的数码个数，作为启发信息。的数码个数，作为启发信息。对初始节点对初始节点S0，由于，由于d(S0)=0，W(S0)=3，因此有，因此有 f(S
26、0)=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 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)局部择优局部择优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)局部择优局部
27、择优A算法，例算法，例(续）续）11(8)解的路径：1-2-6-8-10-11-14-16-1814(9)1 38 2 47 6 517(10)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节点）取出放入节点）取出放入CL
28、OSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.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表的首部表的首部，并为每一个子节点都配置指向父节点的指针，然后转并为每一个子节点都配置指向
29、父节点的指针，然后转（2 2）步）步。限界局部择优：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图 算符有：R1:如果满足条件 则 空格左移 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
30、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)限界局部择优搜索限界局部择优搜索（例）（例）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表的
31、变化(限界局部择优搜索法）初始(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=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
32、=3 8 (17(4),18(6),15(10),3(4),4(5),5(5)d=4 9 17(4)为目标节点，结束 算法讨论 局部择优搜索方法评价 与深度优先搜索比较 缺陷全局择优搜索全局择优搜索A A算法描述算法描述(1)(1)把初始节点把初始节点S0放入放入Open表中，表中，f(S0)=g(S0)+h(S0)；(2)(2)如果如果Open表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点表，并记该节点为为n；(4)(4)考察节点考察节点n是否为目标节点。若是，则找到问题的解，成功退出
33、；是否为目标节点。若是，则找到问题的解，成功退出；(5)(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)(6)扩展节点扩展节点n，生成其子节点，生成其子节点ni(i=1,2,)，计算每一个子节点的，计算每一个子节点的估价值估价值f(ni)(i=1,2,)，并为每一个子节点设置指向父节点的指，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入针，然后将这些子节点放入Open表中；表中；(7)(7)根据各节点的估价函数值，根据各节点的估价函数值，对对Open表中的全部节点按从小到大表中的全部节点按从小到大的顺序重新进行排序；的顺序重新进行排序；(8)(8)转第转第(
34、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 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
35、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(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 (1
36、1(4),4(5),5(5),6(5),7(6),9(6),12(6)6 11(4)为目标节点，结束 算法讨论 全局择优搜索A算法评价：如何找到最优解.目标 寻找最佳全局搜索算法寻找最佳全局搜索算法A*A*算法总能找到最优解算法总能找到最优解使扩展结点数尽量少使扩展结点数尽量少 方法：方法：对启发式函数进行限制对启发式函数进行限制目标1：算法的可采纳性 在问题有解的情况下，若一个搜索过程总能找在问题有解的情况下，若一个搜索过程总能找到最优解，则称该算法具有可采纳性。到最优解，则称该算法具有可采纳性。可采纳性的衡量：可采纳性的衡量：f f*(n)=g(n)=g*(n)+h(n)+h*(n)(n)
37、例例 重排九宫问题重排九宫问题 f(x)=d(x)+h(x)f(x)=d(x)+h(x)h1(x)=0 h2(x):错位棋牌的个数错位棋牌的个数 h3(x):h3(x):每个将牌与其目标位置之间的距离和每个将牌与其目标位置之间的距离和 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
38、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 47 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
39、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 47 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 3
40、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 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(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 4
41、7 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)=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
42、=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 37 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*算法的采纳性证明 定理(可采纳性定理)：
43、若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。证明见书证明见书定理定理4.1、定理、定理4.2、定理、定理4.3A*算法效率问题 A*算法评价 如何设计搜索算法 找到最优解并使扩展的节点数尽可能少.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)S
44、BAG(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)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(1
45、1)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*算法评价 如何设计搜索算法 找到最优解并使扩展的节点数尽可能少.出现多次扩展节点的原因 在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A
46、。s(10)A(1)B(5)C(8)G 目标631118解决的途径 对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是单调的。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)
47、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(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时，该节点就已经找到了通往时，该节点就已经找到了通往
48、它的最佳路径，它的最佳路径，即即g(n)=g*(n)。在在h(n)满足单调性限制下的满足单调性限制下的A*算法常被算法常被称为改进的称为改进的A*算法。算法。例2：修改h(n)SADBTC1119163146181h=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*算法的搜索效率很大程度上取决于估算法的搜索效率很大程
50、度上取决于估价函数价函数h(n)。一般来说，在满足。一般来说，在满足h(n)h*(n)的的前提下，前提下，h(n)的值越大越好。的值越大越好。h(n)的值越大，的值越大，说明它携带的启发性信息越多，说明它携带的启发性信息越多，A*算法搜索时算法搜索时扩展的节点就越少，搜索效率就越高。扩展的节点就越少，搜索效率就越高。启发函数强弱对结果的影响2 h(n)满足单调性限制下的满足单调性限制下的A*算法更好算法更好 原因：原因：能够保证，每当扩展一个节点时能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径。就已经找到了通往这个节点的最佳路径。在在h(n)满足单调性限制下的满足单调性限制下的
