人工智能第二章上优秀课件.ppt

《人工智能第二章上优秀课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第二章上优秀课件.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能第二章上第1页，本讲稿共50页2.1搜索问题搜索问题问题提出人工智能要解决的问题是非结构化问题；人工智能要解决的问题是非结构化问题；难以获得求解所需的全部信息；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。更没有现成的算法可供求解使用。应用第2页，本讲稿共50页搜索需要解决的问题知识表示（状态空间表示）搜索策略（如何搜索，知识的使用）最优搜索(如何找到最优路径）第3页，本讲稿共50页2.2状态空间表示法状态空间表示法表示方法(1)状态(State):Sk=Sk1,Sk2,Skn(2)操作(Operator):操作描述了状态之间的关系 表示：F:f1,f2,fn(3)状态空间

2、(State Space)三元组表示S,F,G 其中：S初始状态集 G：目标状态集合 F：操作的集合。第4页，本讲稿共50页状态空间图可有相应的赋值有向图节点表示状态，有向边表示操作 问题求解过程转化为在图中寻找从初始状态S出发到达目标状态G的路径问题，也就是寻找操作序列的问题第5页，本讲稿共50页举 例（用 状 态 空 间 方 法）2阶“梵 塔”问 题(Tower of Hanoi Problem):有三个柱子(1，2和3)和两个不同尺寸的圆盘(A，B)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上,最初,全部两个圆盘都堆在柱子1上(最大的在底部,最小的在顶部)。要求把所有 圆盘都移到另

3、一个柱子上，搬动规则为：(1)一次只能搬一个圆盘(2)不能将大圆盘放在小圆盘上(3)可以利用空柱子。(example,hono)第6页，本讲稿共50页用状态空间方法来描述问题用状态空间方法来描述问题：状态的表示柱的编号用i,j来代表(i,j)表示问题的状态其中:i代表A(小）所在的柱子,j 代表B（大）所在的柱子状态集合（可能的）s0=(1,1),s1=(1,2),s2=(1,3)s3=(2,1),s4=(2,2),s5=(2,3)s6=(3,1),s7=(3,2),s8=(3,3)第7页，本讲稿共50页初始状态S=s0，目标状态G=s4,s8S0=(1,1)A132BS4=(2,2)123A

4、BS8=(3,3)123AB第8页，本讲稿共50页操作（算符）定义操作A(i,j),B(i,j)操作集合(12种操作）：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)约束：不能将大圆盘（B）放在小圆盘（A）上第9页，本讲稿共50页状态空间图S0(1,1)S3(2,1)S6(3,1)S5(2,3)S7(3,2)S8(3,3)S2(1,3)S1(1,2)S4(2,2)A(1,3)B(1,2)A(3,2)目标目标初始A(1,2)B(1,3)A(2,3)第10页，本讲稿共50页搜索要解

5、决的问题搜索策略搜索策略：如何找到解的路径即如何生成进一步的状态约定约定：不可走回头路搜索图搜索图：问题求解过程中经过的所有路径最优解：使用操作（算符）最少的解最优解：使用操作（算符）最少的解例例第11页，本讲稿共50页搜索策略1：宽度优先S0(1,1)S 3(2,1)S6(3,1)S5(2,3)S7(3,2)012S8(3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13第12页，本讲稿共50页搜索策略2：深度优先S0(1,1)S 3(2,1)S6(3,1)S5(2,3)012S8(3,3)S6

6、(3,1)34S2(1,3)56第13页，本讲稿共50页状态空间法求解问题的基本过程状态空间法求解问题的基本过程首先为问题选择适当的首先为问题选择适当的“状态状态”及及“操作操作”的形式化描述方法；的形式化描述方法；然后从某个初始状态出发，每次使用一个然后从某个初始状态出发，每次使用一个“操作操作”，递增，递增地建立起操作序列，直到达到目标状态为止；地建立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。问题的一个解。第14页，本讲稿共50页状态空间求解问题的关键状态空间求解问题的关键选择合适的状态描

7、述形式选择合适的状态描述形式定义一组算符（操作）定义一组算符（操作）搜索策略：决定算符生成进一步状态的顺序搜索策略：决定算符生成进一步状态的顺序第15页，本讲稿共50页状态空间表示方法的应用状态空间表示方法的应用语法分析a:The dogs kick the ball.b:The small dogs kick the ball.c:The small black dogs kick the ball.d:The small black dogs kick the red ball.第16页，本讲稿共50页搜索策略分类搜索策略分类无信息搜索过程无信息搜索过程宽度优先宽度优先深度优先深度优先启发

8、式搜索过程启发式搜索过程代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索(局部优先搜索)代价树有界深度优先搜索局部择优A算法A算法(全局优先搜索)第17页，本讲稿共50页2.3 无信息搜索基本术语基本术语广（宽）度优先搜索广（宽）度优先搜索深度优先搜索深度优先搜索有界深度优先搜索有界深度优先搜索第18页，本讲稿共50页基本术语图搜索：实现从一个隐含图中,生成出一部分确实含有一个目标节点的显式表示子图的搜索过程.例：2阶“梵塔”问题第19页，本讲稿共50页状态空间图S0(1,1)S3(2,1)S6(3,1)S5(2,3)S7(3,2)S8(3,3)S2(1,3)S1

9、(1,2)S4(2,2)A(1,3)B(1,2)A(3,2)目标目标初始A(1,2)B(1,3)A(2,3)第20页，本讲稿共50页搜索树：由初始状态出发进行试探，以期找到一条通往目标状态的路径.记录这搜索过程的状态的树初始节点，目标节点，子节点节点深度路径例：2阶“梵塔”问题第21页，本讲稿共50页基本术语S0(1,1)S 3(2,1)S6(3,1)S5(2,3)S7(3,2)012S8(3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13初始节点终止节点路径第22页，本讲稿共50页数据结构记录

10、搜索过程：OPEN表，CLOSED表lOPEN表:存放刚生成的节点OPEN表形式：状态节点，父节点lCLOSED表:存放将要扩展或已扩展的节点CLOSED表形式：编号，状态节点，父节点例：2阶“梵塔”问题第23页，本讲稿共50页搜索树：宽度优先S0(1,1)S 3(2,1)S6(3,1)S5(2,3)S7(3,2)012S8(3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13第24页，本讲稿共50页初始Open表 CLOSE表状态节点 父节点 S0(1,1)编号状态节点 父节点第25页，本讲稿共

11、50页第一次扩展Open表 CLOSE表状态节点 父节点 S3(2,1)S0(1,1)S6(3,1)S0(1,1)编号 状态结点父结点1S0(1,1)第26页，本讲稿共50页第二次扩展OPEN表 CLOSED表编号 状态结点父结点1S0(1,1)2S3(2,1)S0(1,1)第27页，本讲稿共50页广（宽）度优先搜索广（宽）度优先搜索基本思想搜索过程实例算法讨论第28页，本讲稿共50页宽度优先搜索基本思想从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层节点没有全部扩展并考察前，不对第n+1层的节点进行扩展。节点按进入open表的先后顺序排列第29页，本讲稿共50页广（宽

12、）度优先搜索过程(1)把初始节点把初始节点S0放入放入Open表中；表中；(2)如果如果Open表为空，则问题无解，失败退出；表为空，则问题无解，失败退出；(3)把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表，并记该节点为表，并记该节点为n；(4)考察节点考察节点n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步；(6)扩展节点扩展节点n，将其子节点放入将其子节点放入Open表的尾部表的尾部，并为每一个子节点设，并为每一个子节点设置指向父节点的指针，然后转第置

13、指向父节点的指针，然后转第(2)步。步。第30页，本讲稿共50页例1 宽度优先（2级梵塔）S0(1,1)S 3(2,1)S6(3,1)S5(2,3)S7(3,2)012S8(3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13第31页，本讲稿共50页例2：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件 则 空格左移R2:如果满足条件 则 空格上移R3:如果满足条件 则 空格右移R4:如果满足条件 则 空格下移注：条件指有位置并且不重复

14、冲突解决方法：算符序号2 8 31 47 6 5 1 2 3 8 47 6 5第32页，本讲稿共50页宽度优先搜索演示宽度优先搜索演示演示演示.ppt（九宫图）2 8 31 47 6 51 2 38 47 6 5初始状态目标状态第33页，本讲稿共50页算法讨论存在问题吗？如何改进？算法特点第34页，本讲稿共50页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 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4

15、 57 6 8 32 1 47 6 52 8 37 1 46 51 2 3 8 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 513452 8 31 6 4 7 52 8 31 6 47 567891011121314151617181920212223242526宽度优先搜索图宽度优先搜索图(改进改进)2解的路径：1381626第35页，本讲稿共50页Open表的变化

16、(改进的宽度优先搜索法）初始(1)1 (2,3,4,5)2 (3,4,5,6,7)3 (4,5,6,7,8,9)4 (5,6,7,8,9,10,11)5 (6,7,8,9,10,11,12,13)6 (7,8,9,10,11,12,13,14)7 (8,9,10,11,12,13,14,15,)8 (9,10,11,12,13,14,15,16)9 (10,11,12,13,14,15,16,17)10 (11,12,13,14,15,16,17,18)11 (12,13,14,15,16,17,18,19)12 (13,14,15,16,17,18,19,20)13 (14,15,16,17

17、,18,19,20,21)14 (15,16,17,18,19,20,21,22,23)15 (16,17,18,19,20,21,22,23,24,25)16 (17,18,19,20,21,22,23,24,25,)26第36页，本讲稿共50页 深度优先搜索深度优先搜索基本思想搜索过程实例算法讨论第37页，本讲稿共50页深度优先搜索基本思想从初始节点S0开始，在其子节点中选择一个节点进行扩展并考察它是否为目标节点，若不是目标节点，则在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索。当到达某个子节点，且该子节点即不是目标节点又不能继续扩展时，才选择其兄弟节点进行扩展。节点按后进入o

18、pen表的顺序排列，即后进入的节点排在表的最前面第38页，本讲稿共50页深度优先搜索过程(1)(1)把初始节点把初始节点S0放入放入Open表中；表中；(2)(2)如果如果OpenOpen表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出；(3)(3)把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n；(4)(4)考察节点考察节点n n是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)(5)若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；步

19、；(6)(6)扩展节点扩展节点n n，将其子节点放入将其子节点放入OpenOpen表的首部表的首部，并为每一个子节点设置，并为每一个子节点设置 指向指向父节点的指针，然后转第父节点的指针，然后转第(2)(2)步。步。第39页，本讲稿共50页例1 深度优先（2级梵塔）S0(1,1)S 3(2,1)S6(3,1)S5(2,3)012S8(3,3)S6(3,1)34S2(1,3)56第40页，本讲稿共50页例2：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件 则 空格左移R2:如果满足条件 则 空格上移R3:如果满足条件 则 空格右移R

20、4:如果满足条件 则 空格下移注：条件指有位置并且不重复冲突解决方法：算符序号2 8 31 47 6 5 1 2 3 8 47 6 5第41页，本讲稿共50页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 58 32 1 47 6 58 32 1 47 6 58 1 32 47 6 513456789102深度优先搜索图深度优先搜索图第42页，本讲稿共50页8 3 42 17 6 5118 3 42 17 6 58 3 42 1 57 6 8 3 4 2 1

21、7 6 58 42 3 17 6 58 3 42 6 17 5 3 48 2 17 6 58 3 47 2 1 6 5121314191815163 48 2 17 6 517深度优先搜索图（续）深度优先搜索图（续）第43页，本讲稿共50页Open表初始（1）1（2,3,4,5）2 (6,7,3,4,5)3 (8,7,3,4,5)4 (9,10,7,3,4,5)5 (11,10,7,3,4,5)6 (12,13,10,7,3,4,5)7 (14,15,16,13,10,7,3,4,5)8 (17,18,15,16,13,10,7,3,4,5)9 (19,18,15,16,13,10,7,3,4

22、,5).第44页，本讲稿共50页算法讨论存在问题改进方法第45页，本讲稿共50页有界深度优先搜索有界深度优先搜索基本思想搜索过程实例第46页，本讲稿共50页有界深度优先搜索基本思想对深度优先搜索引入搜索深度的限制（设为dm），当搜索深度达到深度界限时，尚未出现目标节点，就选择其兄弟节点进行扩展。节点按后进入open表的顺序排列，即后进入的节点排在前面深度的确定：固定深度 可变深度 第47页，本讲稿共50页有界深度搜索过程1.将初始节点将初始节点S0S0放入放入OPENOPEN表表,置置S0S0的深度的深度d(S0)=0d(S0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空

23、，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，退出。是否为目标节点。若是，则求得了问题的解，退出。5.5.若节点若节点n n的深度的深度d(d(节点节点n)=dm,n)=dm,转（转（2 2）步。）步。6.6.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。7.7.扩扩展展节节点点n n，将将其其子子节节点点放放入入OPENOPEN表表的的首首部部，并并为为每每一一个个子节点都配置指向父节点的指针，然后转（子节点

24、都配置指向父节点的指针，然后转（2 2）步。）步。第48页，本讲稿共50页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 5 2 31 8 47 6 58 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 58 32 1 47 6 58 1 32 47 6 52 8 37 46 1 52 8 37 1 46 51 2 38 47 6 51345671481116910121317有界深度优先搜索图有界深度优先搜索图 dm=42解的路径：13141617第49页，本讲稿共50页Open表初始（1）1（2,3,4,5）2 (6,7,3,4,5)3 (8,7,3,4,5)4 (9,10,7,3,4,5)dm=55 (10,7,3,4,5)dm=56 (7,3,4,5)7 (11,3,4,5)8 (12,13,3,4,5)dm=59 (13,3,4,5)dm=510(3,4,5)11 (14,4,5)12 (15,4,5)13 (16,4,5)14 16 为目标节点.第50页，本讲稿共50页