人工智能第二章下课件

《人工智能第二章下课件》由会员分享，可在线阅读，更多相关《人工智能第二章下课件（90页珍藏版）》请在金锄头文库上搜索。

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)=2 c(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 代价树：边上标有代价的搜索树,s0,A,C,B

3、,3,2,4,s0,A,B,C,2,3,4,2.4.1 代价驱动的搜索策略,代价树的广度优先搜索 动态规划法（改进的代价树广度优先搜索) 代价树的深度优先搜索,代价树的广度优先搜索,基本思想 搜索过程 实例 存在问题 解决方法(动态规划法）,基本思想,open表的节点顺序按的节点代价排列（从小到大）,搜索过程,1.将初始节点s0放入OPEN表,令g(s0)=0 2.如果OPEN表为空，则问题无解，退出 3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表 4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。 5.若节点n不可扩展转（2）步。 6.扩展节点n，将其子节点放入O

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

5、1),B3(13),E3(10),E2(12),16,D3(14),F3(16),B4(15),F2(14),C3(17),A3(15),C2(15),3,4,4,4,5,5,5,2,4,5,4,2,2,4,5,4,4,4,4,3,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

6、),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(1

7、3),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) 14 T1(13)为目标节点，结束。,算法讨论,存在问题 改进方法,动态规划法,基本思想 搜索过程 实例,基本思想,当有多条到达某一公共节点的路径，只保留代价最小的路径,搜索过程,1.将初始节点s0放入OPEN表,令g(s0)=0 2.如果OPEN表为空，则问题无解，退出 3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表 4.考察节点n是否为目标节点。若是，则求得了问题的

8、解，退出。 5.若节点n不可扩展转（2）步。 6.扩展节点n，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，若新出现的节点是多条路径都到达的节点，则只选代价最小的路径，其余删去，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺），然后转（2）步。,例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用动态规划.ppt,S,A,D,E,B,F,T,C,3,4,4,5,2,5,4,4,3,动态规划法（例）,1,2,3,4,5,6,7,10,11,8,9,14,S(0),D1(4),A1(3),B1( 7 )

9、,D2(8),A2(9),E1(6),F1(10),T1(13),C1(11),E2(12),3,4,4,4,5,5,5,5,4,2,3,B2(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 结束,代价树的深度优先搜索,基本思想 搜索过程 实例 算法讨论,基本思想：在刚扩展的子节点中选择一个代价最小的节点进

10、行扩展，即表的首部存放刚扩展的所有子节点（按代价从小到大排序） 搜索过程： 1.将初始节点放入OPEN表，令g(s0)=0 2.如果OPEN表为空，则问题无解，退出 3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表 4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。 5.若节点n不可扩展转（2）步。 6.扩展节点n，将其子节点按代价从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。,例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用,S,A,D,E,B,F,T,C,3,4,4,5,2,5,

11、4,4,3,代价树的深度优先搜索（例）,1,2,3,4,5,6,7,8,9,S(0),D1(4),A1(3),B1( 7 ),D2(8),C1(11),E 1(12),D3(14),F1(16),3,4,4,4,5,5,2,4,10,T1(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 (T

12、1(19),D2(8),D1(4) 8 T1(19）为目标节点结束,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,1（0）,3(1),4(1),5(1),7(2),例2代价树的深度优先搜索 （括号中为代价）,2（1）,6(2),8 3 2 1 4 7 6 5,9(4),8 3 2 1 4 7 6 5,8 1 3 2 4 7 6 5,10(4),8(3),8 1 3 2 4 7 6 5,1 3 8 2 4 7 6 5,8

13、 1 3 7 2 4 6 5,1 2 3 8 4 7 6 5,15(6),（例2续）,11(5),解的路径：1-2-6-8-10-11-14-16-18,14(6),1 3 8 2 4 7 6 5,17(8),1 3 8 2 4 7 6 5,16(7),8 1 3 2 4 7 6 5,8 1 3 2 6 4 7 5,12(5),13(5),18(8),2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,1（0）,3(1),4(1),5(1),例2 换一条路径,2（1）,2 3 1 8 4

14、 7 6 5,2 3 1 8 4 7 6 5,6(2),1 2 3 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,7(2),10(4),8(3),9(4),算法讨论,存在的问题 解决方法,代价树的有界深度优先搜索,基本思想 搜索过程 实例,基本思想,当一个节点被扩展后，按f(x)对每一个子节点计算估值，并选择其中最小的先扩展。,代价树的有界深度优先搜索过程,1.将初始节点放入OPEN表，令g(s0)=0 2.如果OPEN表为空，则问题无解，退出 3.把OPEN表的第一个节点（记为n节点）取出放入CLOSED表 4.考察节点n是否为目标节点。若是，则求得了问

15、题的解，退出。 5.若节点n不可扩展转（2）步。 6.IF d(n)=规定深度 THEN GO (2) 7.扩展节点n，用估价函数f(x)计算每个子节点的估价值，并将其子节点按估价值从小到大放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转（2）步。,例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。求从S到T的最小交通费用,S,A,D,E,B,F,T,C,3,4,4,5,2,5,4,4,3,代价树的有界深度优先搜索（例） dm=4,1,2,3,4,5,13,14,6,7,10,15,16,8,9,11,14,S(0),D1(4),A1(3),B1( 7 ),D2(8),A2(9),E3(6),F3(10),T1(13),C1(11),E2(10),E1(12),12,D3(14),F1(16),B2(15),F2(14),3,4,4,4,5,5,5,2,5,4,2,2,4,5,4,3,B3(11),代价树搜索的总结,优点 不足：局限性,2 8 3 1 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,1（0）,3(1),4(1),5(1),九宫问题使用代价的局限性,2（1）,2 3 1 8 4 7 6 5,2 3 1 8 4 7