人工智能第二章上PPT讲稿.ppt

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

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

2、作 描 述 了 状 态 之 间 的 关 系 表示：F:f1,f2,fn(3)状态空间(State Space)三元组表示S,F,G 其中：S初始状态集 G：目标状态集合 F：操作的集合。第4页，共50页，编辑于2022年，星期四状态空间图可有相应的赋值有向图节点表示状态，有向边表示操作 问题求解过程转化为在图中寻找从初始状态S出发到达目标状态G的路径问题，也就是寻找操作序列的问题第5页，共50页，编辑于2022年，星期四举 例（用 状 态 空 间 方 法）2阶“梵塔”问题(Tower of Hanoi Problem):有三个柱子(1，2和3)和两个不同尺寸的圆盘(A，B)。在每个圆盘的中心有

3、个孔，所以圆盘可以堆叠在柱子上,最初,全部两个圆盘都堆在柱子1上(最大的在底部,最小的在顶部)。要求把所有 圆盘都移到另一个柱子上，搬动规则为：(1)一次只能搬一个圆盘(2)不能将大圆盘放在小圆盘上(3)可以利用空柱子。(example,hono)第6页，共50页，编辑于2022年，星期四用状态空间方法来描述问题用状态空间方法来描述问题：状态的表示柱的编号用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=

4、(3,2),s8=(3,3)第7页，共50页，编辑于2022年，星期四初始状态S=s0，目标状态G=s4,s8S0=(1,1)A132BS4=(2,2)123ABS8=(3,3)123AB第8页，共50页，编辑于2022年，星期四操作（算符）定义操作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页，编辑于2022年，星期四状态空间图S0(1,1)S3(2,1)S6(3,1)

5、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页，编辑于2022年，星期四搜索要解决的问题搜索策略搜索策略：如何找到解的路径即如何生成进一步的状态约定约定：不可走回头路搜索图搜索图：问题求解过程中经过的所有路径最优解：使用操作（算符）最少的解最优解：使用操作（算符）最少的解例例第11页，共50页，编辑于2022年，星期四搜索策略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)

6、3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13第12页，共50页，编辑于2022年，星期四搜索策略2：深度优先S0(1,1)S 3(2,1)S6(3,1)S5(2,3)012S8(3,3)S6(3,1)34S2(1,3)56第13页，共50页，编辑于2022年，星期四状态空间法求解问题的基本过程状态空间法求解问题的基本过程首先为问题选择适当的首先为问题选择适当的“状态状态”及及“操作操作”的形式化描述方法；的形式化描述方法；然后从某个初始状态出发，每次使用一个然后从某个初始状态出发，每次使用一个“操作操作”，递增地建，递增地建

7、立起操作序列，直到达到目标状态为止；立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该问题的一此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。个解。第14页，共50页，编辑于2022年，星期四状态空间求解问题的关键状态空间求解问题的关键选择合适的状态描述形式选择合适的状态描述形式定义一组算符（操作）定义一组算符（操作）搜索策略：决定算符生成进一步状态的顺序搜索策略：决定算符生成进一步状态的顺序第15页，共50页，编辑于2022年，星期四状态空间表示方法的应用状态空间表示方法的应用语法分析a:The dogs kick the ball.b:The

8、 small dogs kick the ball.c:The small black dogs kick the ball.d:The small black dogs kick the red ball.第16页，共50页，编辑于2022年，星期四搜索策略分类搜索策略分类无信息搜索过程无信息搜索过程宽度优先宽度优先深度优先深度优先启发式搜索过程启发式搜索过程代价树的广度优先搜索动态规划法（改进的代价树广度优先搜索)代价树的深度优先搜索(局部优先搜索)代价树有界深度优先搜索局部择优A算法A算法(全局优先搜索)第17页，共50页，编辑于2022年，星期四2.3 无信息搜索基本术语基本术语广（宽

9、）度优先搜索广（宽）度优先搜索深度优先搜索深度优先搜索有界深度优先搜索有界深度优先搜索第18页，共50页，编辑于2022年，星期四基本术语图搜索：实现从一个隐含图中,生成出一部分确实含有一个目标节点的显式表示子图的搜索过程.例：2阶“梵塔”问题第19页，共50页，编辑于2022年，星期四状态空间图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)第20页，共50页，编辑于2022年，星期四搜索树：由初始状态出发进行试探，以期找到一条通往

10、目标状态的路径.记录这搜索过程的状态的树初始节点，目标节点，子节点节点深度路径例：2阶“梵塔”问题第21页，共50页，编辑于2022年，星期四基本术语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页，编辑于2022年，星期四数据结构记录搜索过程：OPEN表，CLOSED表lOPEN表:存放刚生成的节点OPEN表形式：状态节点，父节点lCLOSED表:存放将要扩展或已扩展的节

11、点CLOSED表形式：编号，状态节点，父节点例：2阶“梵塔”问题第23页，共50页，编辑于2022年，星期四搜索树：宽度优先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页，编辑于2022年，星期四初始Open表 CLOSE表状态节点 父节点 S0(1,1)编号状态节点 父节点第25页，共50页，编辑于2022年，星期四第一次扩展Open表 CLOSE表状态节点 父节点 S3(2,1)S0(1

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

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

14、父节点的指针，然后转第(2)步。步。第30页，共50页，编辑于2022年，星期四例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页，编辑于2022年，星期四例2：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件 则 空格左移R2:如果满足条件 则 空格上移R3:如果满足条件 则 空格右移R4:如果满足条件 则

15、 空格下移注：条件指有位置并且不重复冲突解决方法：算符序号2 8 31 47 6 5 1 2 3 8 47 6 5第32页，共50页，编辑于2022年，星期四宽度优先搜索演示宽度优先搜索演示演示演示.ppt（九宫图）2 8 31 47 6 51 2 38 47 6 5初始状态目标状态第33页，共50页，编辑于2022年，星期四算法讨论存在问题吗？如何改进？算法特点第34页，共50页，编辑于2022年，星期四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

16、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 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宽度优先搜

17、索图宽度优先搜索图(改进改进)2解的路径：1381626第35页，共50页，编辑于2022年，星期四Open表的变化(改进的宽度优先搜索法）初始(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,

18、15,16,17,18,19)12 (13,14,15,16,17,18,19,20)13 (14,15,16,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页，编辑于2022年，星期四 深度优先搜索深度优先搜索基本思想搜索过程实例算法讨论第37页，共50页，编辑于2022年，星期四深度优先搜索基本思想从初始节点S0开始，在其子节点中选择一个节点进行扩展并考察它是否为目标节点，若不是目标节点，则在该

19、子节点的子节点中选择一个节点进行考察，一直如此向下搜索。当到达某个子节点，且该子节点即不是目标节点又不能继续扩展时，才选择其兄弟节点进行扩展。节点按后进入open表的顺序排列，即后进入的节点排在表的最前面第38页，共50页，编辑于2022年，星期四深度优先搜索过程(1)(1)把初始节点把初始节点S0放入放入Open表中；表中；(2)(2)如果如果OpenOpen表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出；(3)(3)把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n；(4)(4)考察节点考察节点n n

20、是否为目标节点。若是，则得到问题的解，成功退出；是否为目标节点。若是，则得到问题的解，成功退出；(5)(5)若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；步；(6)(6)扩展节点扩展节点n n，将其子节点放入将其子节点放入OpenOpen表的首部表的首部，并为每一个子节点设置，并为每一个子节点设置 指指向父节点的指针，然后转第向父节点的指针，然后转第(2)(2)步。步。第39页，共50页，编辑于2022年，星期四例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页，编辑

21、于2022年，星期四例2：重排九宫问题例：重排九宫问题。在33的方格棋盘上放置八张牌，初始状态和目标状态如右图算符有：R1:如果满足条件 则 空格左移R2:如果满足条件 则 空格上移R3:如果满足条件 则 空格右移R4:如果满足条件 则 空格下移注：条件指有位置并且不重复冲突解决方法：算符序号2 8 31 47 6 5 1 2 3 8 47 6 5第41页，共50页，编辑于2022年，星期四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

22、 6 58 32 1 47 6 58 1 32 47 6 513456789102深度优先搜索图深度优先搜索图第42页，共50页，编辑于2022年，星期四8 3 42 17 6 5118 3 42 17 6 58 3 42 1 57 6 8 3 4 2 17 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页，编辑于2022年，星期四Open表初始（1）1（2,3,4,5）2 (6,7,3,4,5)3 (8,7,3,

23、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,5).第44页，共50页，编辑于2022年，星期四算法讨论存在问题改进方法第45页，共50页，编辑于2022年，星期四有界深度优先搜索有界深度优先搜索基本思想搜索过程实例第46页，共50页，编辑于2022年，星期四有界深度优先搜索基本思想对深度优先搜索引入搜索深度的限制（设为dm），当搜索深度达到深度界限时，尚未出现目标

24、节点，就选择其兄弟节点进行扩展。节点按后进入open表的顺序排列，即后进入的节点排在前面深度的确定：固定深度 可变深度 第47页，共50页，编辑于2022年，星期四有界深度搜索过程1.将初始节点将初始节点S0S0放入放入OPENOPEN表表,置置S0S0的深度的深度d(S0)=0d(S0)=02.2.如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出3.3.把把OPENOPEN表的第一个节点（记为表的第一个节点（记为n n节点）取出放入节点）取出放入CLOSEDCLOSED表表4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，退出。是否为目标节点。若是

25、，则求得了问题的解，退出。5.5.若节点若节点n n的深度的深度d(d(节点节点n)=dm,n)=dm,转（转（2 2）步。）步。6.6.若节点若节点n n不可扩展转（不可扩展转（2 2）步。）步。7.7.扩扩展展节节点点n n，将将其其子子节节点点放放入入OPENOPEN表表的的首首部部，并并为为每每一一个个子子节节点点都都配置指向父节点的指针，然后转（配置指向父节点的指针，然后转（2 2）步。）步。第48页，共50页，编辑于2022年，星期四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 4

26、7 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页，编辑于2022年，星期四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页，编辑于2022年，星期四