搜索
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)=2c(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表的节点顺序按的节点代价排列（从小到大）搜索过程1.将初始节点s0放入OPEN表,令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺序），然后转（2）步。•例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用代宽演示.pptSADEBFTC344525443•代价树的广度优先搜索（例）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•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))14T1(13)为目标节点，结束。算法讨论•存在问题•改进方法动态规划法•基本思想•搜索过程•实例基本思想•当有多条到达某一公共节点的路径，只保留代价最小的路径搜索过程1.将初始节点s0放入OPEN表,令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，若新出现的节点是多条路径都到达的节点，则只选代价最小的路径，其余删去，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺），然后转（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))5(F1(10),C1(11),E2(12))6(C1(11),T1(13))7(T1(13))8结束代价树的深度优先搜索•基本思想•搜索过程•实例•算法讨论•基本思想：在刚扩展的子节点中选择一个代价最小的节点进行扩展，即表的首部存放刚扩展的所有子节点（按代价从小到大排序）•搜索过程：1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，退出3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展转（2）步。6.扩展节点n，将其子节点按代价从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。•例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用SADEBFTC344525443•代价树的深度优先搜索（例）123456789S(0)D1(4)A1(3)B1(7)D2(8)C1(11)E1(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))8T1(19）为目标节点结束283147652831476523184765283147652831647583214765283714651（0）3(1)4(1)5(1)7(2)例2代价树的深度优先搜索（括号中为代价）2（1）6(2)832147659(4)832147658132476510(4)8(3)8132476513824765813724651238476515(6)（例2续）11(5)解的路径：1-2-6-8-10-11-14-16-1814(6)1382476517(8)1382476516(7)813247658132647512(5)13(5)18(8)28314765283147652318476528314765283164751（0）3(1)4(1)5(1)例2换一条路径2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)算法讨论•存在的问题•解决方法代价树的有界深度优先搜索•基本思想•搜索过程•实例基本思想•当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。代价树的有界深度优先搜索过程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）步。•例如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用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)代价树搜索的总结•优点•不足：局限性28314765283147652318476528314765283164751（0）3(1)4(1)5(1)九宫问题使用代价的局限性2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)2.4.2A算法•启发性函数•A算法•A*算法•算法讨论启发性函数的表示•含义：用于估价节点重要性的函数称为估价函数•表示：f(x)=g(x)+h(x)–g(x)是从初始结点S0到x实际代价–h(x)是从x到目标结点Sg的最佳路径的估计代价,启发性信息的函数描述。•例重排九宫问题例：重排九宫问题例：重排九宫问题。在3×3的方格棋盘上放置八张牌，初始状态和目标状态如右图•算符有：–R1:如果满足条件则空格左移–R2:如果满足条件则空格上移–R3:如果满足条件则空格右移–R4:如果满足条件则空格下移–注：条件指有位置并且不重复•冲突解决方法：算符序号2831476512384765解：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=32831476512384765S0Sg希望：•引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。A算法概述概念：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。全局择优：从Open表的所有节点中选择一个估价函数值最小的一个进行扩展。局部择优：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。局部择优A算法•基本思想：当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。•搜索过程：1.将初始节点放入OPEN表，令g(s0)=02.如果OPEN表为空，则问题无解，