资源描述：
《人工智能第二章节下》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2.4启发式搜索搜索技术的应用－智能搜索引擎启发式搜索涉及的基本概念基本的启发式搜索方法代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索(局部优先搜索)代价树有界深度优先搜索局部择优A算法A算法(全局优先搜索)启发式搜索概念启发式搜索与无信息搜索无信息（盲目）搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。81启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。启发性信息评估函数评估函数的表示含义：用于估价节点重要性的函数称为估价
2、函数表示：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=2 g(C)=g(A)+c(A,C)=2+4=6代价树：边上标有代价的搜索树s0ACB
3、324s0ABC2342.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的最小交通费用代宽演示.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)F
5、2(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(10),B2(11),C1(11),E2
6、(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
7、(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表中
8、，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，若新出现的节点是多条路径都到达
