第三章1搜索推理技术.ppt

《第三章1搜索推理技术.ppt》由会员分享，可在线阅读，更多相关《第三章1搜索推理技术.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 搜索推理技术搜索推理技术3.6 产生式系统3.7 系统组织技术3.8 不确定性推理3.9 非单调推理3.10 小结3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索3.4 消解原理3.5 规则演绎系统AI为什么要研究为什么要研究search问题没有直接的解法问题没有直接的解法;需要探索地求解需要探索地求解;什么是搜索什么是搜索?根据问题的实际情况不断寻找可利用的知识根据问题的实际情况不断寻找可利用的知识,构造出一条代构造出一条代价较少的推理路线价较少的推理路线,使问题得到圆满解决的过程使问题得到圆满解决的过程.包括两个方面：包括两个方面：-找到从初始事实到问题最终答案的一条推理

2、路径找到从初始事实到问题最终答案的一条推理路径 -找到的这条路径在时间和空间上复杂度最小找到的这条路径在时间和空间上复杂度最小2l在在图中寻找路径的方法图中寻找路径的方法l初始节点初始节点 初始数据库初始数据库l目标节点目标节点 满足终止条件的数据库满足终止条件的数据库求取把一个数据库求取把一个数据库变换为另一个数据变换为另一个数据库的规则序列库的规则序列求得图中一条路径求得图中一条路径3.1 图搜索策略图搜索策略 图搜索控制策略3l节点深度：根节点深度=0其它节点深度=父节点深度+101234l路径路径 设一节点序列为设一节点序列为(n0,n1,nk)，对于对于i=1,k，若节点若节点ni-

3、1具有具有一个后继节点一个后继节点ni，则该序列称为从则该序列称为从n0到到nk的路径的路径l路径的耗散值（代价）路径的耗散值（代价）一条路径的耗散值等于连接这条路径各节点间所有耗散值的一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用总和。用C(ni,nj)表示从表示从ni到到nj的路径的耗散值。的路径的耗散值。l扩展一个节点扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为这一过程称为“扩展一个节点扩展一个节点”。5 盲目搜索盲目搜索l图搜索策略图搜索策略 启发式搜索启发式搜索宽度优先搜索宽度优先搜索深

4、度优先搜索深度优先搜索6搜索过程的要点搜索过程的要点:起始节点起始节点:对应于初始状态描述对应于初始状态描述后继节点后继节点:把适用于某个节点状态描述的一些算符用来把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点推算该节点而得到的新节点,称为该节点的后继节称为该节点的后继节点点,检查各后继节点看是否为目标节点检查各后继节点看是否为目标节点.指针指针:从每个后继节点返回指向其父辈节点从每个后继节点返回指向其父辈节点7两个主要的数据结构：两个主要的数据结构：OPEN表表:存放刚生成的节点存放刚生成的节点,是还未扩展的节点是还未扩展的节点.一般一般是端节点是端节点.CLOSED表表:存

5、放将要扩展或已扩展的节点存放将要扩展或已扩展的节点.或者是已或者是已被扩展但还没有在搜索树中生成后继节点的端节点被扩展但还没有在搜索树中生成后继节点的端节点,或者是非端节点或者是非端节点8状状 态态 节节 点点父父 节节 点点编号编号状状 态态 节节 点点父父 节节 点点OPEN表表CLOSED表表9(1)把初始节点把初始节点S0放入放入OPEN表表,并建立目前只包含并建立目前只包含S0的图的图,记为记为G(2)检查检查OPEN表是否为空表是否为空,若为空则问题无解若为空则问题无解,退出退出(3)把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表表,记该节点为记该节点为n(

6、4)考察考察n是否为目标节点是否为目标节点.如是如是,则问题得解则问题得解,退出退出(5)扩展节点扩展节点n,生成一组子节点生成一组子节点.把其中不是节点把其中不是节点n先辈的那些节先辈的那些节点记作集合点记作集合M,并把这些子节点作为节点并把这些子节点作为节点n的子节点加入的子节点加入G中中搜索的一般过程：搜索的一般过程：10(6)针对针对M中子节点的不同情况中子节点的不同情况,分别进行处理分别进行处理1.对于那些未曾在对于那些未曾在G中出现过的中出现过的M成员设置一个指成员设置一个指向父节点向父节点(即即n)的指针的指针,并把它们放入并把它们放入OPEN表表2.对于那些先前已在对于那些先前

7、已在G中出现过的中出现过的M成员成员,确定是确定是否需要修改它指向父节点的指针否需要修改它指向父节点的指针3.对于那些先前已在对于那些先前已在G中出现并且已经扩展了的中出现并且已经扩展了的M成员成员,确定是否需要修改其后继节点指向父节点确定是否需要修改其后继节点指向父节点的指针的指针(7)按某种搜索策略对按某种搜索策略对OPEN表中的节点进行排序表中的节点进行排序(8)转第转第(2)步步11开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表

8、的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功图图3.1 图搜索过程框图图搜索过程框图是是是是否否否否3.1 图搜索策略12l1,G=G0(G0=s),OPEN:=(s);l2,CLOSED:=();l3,LOOP:IF OPEN=()THEN EXIT(FAIL);l4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);l5,IF GOAL(n)THEN EXIT(SUCCESS);l6,EXPAND(n)mi,G:=ADD(mi,G);l7,标记和修改指针：标记和修改指针：lADD(

9、mj,OPEN),并标记并标记mj到到n的指针；的指针；l计算是否要修改计算是否要修改mk、ml到到n的指针；的指针；l计算是否要修改计算是否要修改ml到其后继节点的指针；到其后继节点的指针；l8,对对OPEN中的节点按某种原则重新排序；中的节点按某种原则重新排序；l9,GO LOOP；13SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 例子：G14l这是一个通用的搜索过程这是一个通用的搜索过程,后面讨论的状态空间各种搜索策略后面讨论的状态空间各种搜索策

10、略都是其特例都是其特例.各种搜索策略的主要区别就是对各种搜索策略的主要区别就是对OPEN表中节点表中节点排序准则不同排序准则不同。l算法结束后，将生成一个图算法结束后，将生成一个图G，称为搜索图。同时由于每个称为搜索图。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为搜索树。的一个支撑树，称为搜索树。l从目标节点开始，将指针指向的状态回串起来，即找到一条从目标节点开始，将指针指向的状态回串起来，即找到一条解路径。解路径。l树树/不修改指针不修改指针;图图/修改指针。修改指针。l修改指针修改指针:找最优解。找最优

11、解。153.2 盲目搜索盲目搜索 l特点：不需重排OPEN表l种类：宽度优先、深度优先、等代价搜索等。3.2.1 宽度优先搜索v 定义 以接近起始节点的程度逐层扩展节点的搜索方法。v 特点：一种高代价搜索，但若有解存在，则必能找到它。v 算法从初始节点开始从初始节点开始,逐层对节点进行扩展并考察它是否为目标节点逐层对节点进行扩展并考察它是否为目标节点,在第在第n层层的节点没有全部扩展并考察之前，不对第的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。层的节点进行扩展。16开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移

12、至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的末端，提供返回节点表的末端，提供返回节点n的指针的指针失败失败成功成功图图3.2宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索17宽（广）度优先搜索示意图宽（广）度优先搜索示意图18广度优先搜索方法分析：广度优先搜索方法分析：宽度优先搜索是图搜索一般过程的特殊情况，实际是将宽度优先搜索是图搜索一般过程的特殊情况，实际是将OPEN表作为表作为“先进先出先进先出”的队列进行操作。的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向目标宽度优先

13、搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径节点的最短途径；这棵搜索树提供了所有存在的路径(如如果没有路径存在，那么对有限图来说，我们就说该法失败果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止退出；对于无限图来说，则永远不会终止)。19l 例子八数码难题（8-puzzle problem）1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。3.2 盲目搜

14、索201238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图3.4 八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123845671415161718192021123845673.2 盲目搜索21缺

15、点缺点:当目标节点距离初始节点较远时会产生许多当目标节点距离初始节点较远时会产生许多无用的节点无用的节点,搜索效率低搜索效率低。优点优点:只要问题有解只要问题有解,则总可以得到解则总可以得到解,而且是最短而且是最短路径的解。路径的解。223.2.2 深度优先搜索v 定义 首先扩展最新产生的(即最深的)节点。从初始节点开始从初始节点开始,在其子节点中选择一个节点进行考察，如果不是目标节点，在其子节点中选择一个节点进行考察，如果不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索。则再在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索。当到达某个子节点，且该子节点既

16、不是目标节点又不能继续扩展时，当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。才选择其兄弟节点进行考察。v 算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2 盲目搜索23深度优先搜索示意图深度优先搜索示意图24深度优先搜索方法分析：深度优先搜索方法分析：在深度优先搜索中，我们首先扩展最新产生的在深度优先搜索中，我们首先扩展最新产生的(即最深即最深的的)节点。深度相等的节点可以任意排列。节点。深度相等的节点可以任意排列。2526

17、缺点缺点:如果目标节点不在搜索所进入的分支上如果目标节点不在搜索所进入的分支上,而而该分支又是一个无穷分支该分支又是一个无穷分支,则就得不到解则就得不到解.因此该因此该算法是不完备的算法是不完备的。优点优点:如果目标节点如果目标节点恰好恰好在搜索所进入的分支上在搜索所进入的分支上,则可以较快地得到解则可以较快地得到解。深度优先搜索方法的优缺点深度优先搜索方法的优缺点此外，用深度优先搜索求得的解，不一定是路径最短的解此外，用深度优先搜索求得的解，不一定是路径最短的解。27(1)起始节点起始节点(即根节点即根节点)的深度为的深度为0。(2)任何其它节点的深度等于其父辈节点深度加上任何其它节点的深度

18、等于其父辈节点深度加上1。首先，扩展最深的节点的结果使得搜索沿着状态空首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后于改变最后n步，而且保持步，而且保持n尽可能小。尽可能小。节点深度的定义：节点深度的定义：28对于许多问题，其状态空间搜索树的深度可能为无对于许多问题，其状态空间搜索树的深度可能为无限深，

19、或者可能至少要比某个可接受的解答序列的已知限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径深度上限还要深。为了避免考虑太长的路径(防止搜索过防止搜索过程沿着无益的路径扩展下去程沿着无益的路径扩展下去)，往往给出一个节点扩展的，往往给出一个节点扩展的最大深度最大深度深度界限。任何节点如果达到了深度界限，深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。定就是最

20、短的路径。有界深度优先搜索有界深度优先搜索29有一农夫带一只狼、一只羊和一筐菜欲从河的左有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：岸乘船到右岸，但受下列条件限制：（1）船太小，农夫每次只能带一样东西过河；）船太小，农夫每次只能带一样东西过河；（2）如果没有农夫看管，则狼要吃羊，羊要吃菜。）如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、狼、羊、菜都请设计一个过河方案，使得农夫、狼、羊、菜都能不受损失地过河。画出相应的状态空间图。能不受损失地过河。画出相应的状态空间图。用人工智能搜索算法：用人工智能搜索算法：301 1）老农携带羊羔过河，把狐

21、狸和白菜留在南岸；）老农携带羊羔过河，把狐狸和白菜留在南岸；2 2）老农到达北岸，把羊羔留在北岸，并独自回到南岸；）老农到达北岸，把羊羔留在北岸，并独自回到南岸；3 3）老农携带狐狸过河，把白菜留在南岸；）老农携带狐狸过河，把白菜留在南岸；4 4）老农到达北岸，把狐狸留下，并带上羊羔回到南岸；）老农到达北岸，把狐狸留下，并带上羊羔回到南岸；5 5）老农把羊羔留在南岸，携带白菜过河；）老农把羊羔留在南岸，携带白菜过河；6 6）老老农农到到达达北北岸岸，把把白白菜菜和和狐狐狸狸留留在在北北岸岸，独独自自回回到到南南岸；岸；7 7）老农最后携带羊羔过河，到达北岸。问题就此解决。）老农最后携带羊羔过河

22、，到达北岸。问题就此解决。31提示：提示：（1）用四元组（农夫、狼、羊、菜）用四元组（农夫、狼、羊、菜）表示状态，其中每个元素都可为表示状态，其中每个元素都可为0或或1，用用0表示在左岸，用表示在左岸，用1表示在右岸。表示在右岸。（2）把每次过河的安排作为一个算符，）把每次过河的安排作为一个算符，每次过河都必须有农夫，因为只有他可每次过河都必须有农夫，因为只有他可以划船。以划船。3233用符号表示：用符号表示：M M：代表老农：代表老农(farmer)(farmer)F F：代表狐狸：代表狐狸(fox)(fox)L L：代表羊羔：代表羊羔(lamb)(lamb)C C：代表白菜：代表白菜(ca

23、bbage)(cabbage)S S：表示在南岸：表示在南岸N N：表示在北岸：表示在北岸S-NS-N：表示从南到北：表示从南到北N-S N-S：表示从北到南：表示从北到南3334用用（M M，F F，L L，C C）表表示示四四个个对对象象的的一一个状态个状态,可有可有S S和和N N两个值；两个值；改改变变状状态态的的操操作作，可可分分别别用用1 1，0 0表表示示。表示对象表示对象“在船上在船上”和和“不在船上不在船上”两个值。两个值。如如：初初始始状状态态：（S S，S S，S S，S S），终终止止状状态态：（N N，N N，N N，N N），中中间间状状态态：S-NS-N（1 1，

24、1 1，0 0，0 0）3435老农和其他三个对象不在老农和其他三个对象不在同一岸（狐狸要吃羊羔，同一岸（狐狸要吃羊羔，羊羔要吃白菜）羊羔要吃白菜）(S,N,N,N)：老农在南岸，其他三个对象在北岸：老农在南岸，其他三个对象在北岸 (N,S,S,S)：老农在北岸，其他三个对象在南岸：老农在北岸，其他三个对象在南岸 羊羔和白菜在同一岸（羊羊羔和白菜在同一岸（羊羔要吃白菜）羔要吃白菜）(S,S,N,N)：老农和狐狸在南岸，羊羔和白菜在北岸：老农和狐狸在南岸，羊羔和白菜在北岸 (N,N,S,S)：老农和狐狸在北岸，羊羔和白菜在南岸：老农和狐狸在北岸，羊羔和白菜在南岸 狐狸和羊羔在同一岸（狐狐狸和羊羔

25、在同一岸（狐狸要吃羊羔）狸要吃羊羔）(S,N,N,S)：老农和白菜在南岸，狐狸和羊羔在北岸：老农和白菜在南岸，狐狸和羊羔在北岸 (N,S,S,N)：老农和白菜在北岸，狐狸和羊羔在南岸：老农和白菜在北岸，狐狸和羊羔在南岸 因老农、狐狸、羊羔和白菜都有2种状态，即在南岸和北岸，所以4个对象的总状态数为2*2*2*2=16种，按条件要求，有几种状态不能存在，如表所示。所以只有10种可能状态。3536根根据据题题意意，在在10种种可可能能的的安安全全状状态态里里，只只有有4种种是有可能的操作：是有可能的操作：1 1）老农独自过河（包括从南岸到北岸和从北岸）老农独自过河（包括从南岸到北岸和从北岸到南岸，

26、下同）到南岸，下同）2 2）老农携带狐狸过河）老农携带狐狸过河3 3）老农携带羊羔过河）老农携带羊羔过河4 4）老农携带白菜过河）老农携带白菜过河3637问问题题求求解解过过程程的的表表示示 373.2.3 等代价搜索v 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。v 算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。3.2 盲目搜索38l有关约定起

27、始节点记为S；从节点i到它的后继节点j的连接弧线代价记为c(i,j)；起始节点S到节点i的路径代价记为g(i)。在搜索树上，g(i)也是从S到节点i的最少代价路径上的代价；等代价搜索算法等代价搜索算法以g(i)的递增顺序扩展其节点的算法39开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否否3.2 盲目搜索403.3 启发式搜索启发式搜索l特点

28、：重排OPEN表，选择最有希望的节点加以扩展l种类：有序搜索、A*算法等3.3.1 启发式搜索策略和估价函数v盲目搜索可能带来组合爆炸v启发式信息 用来加速搜索过程的有关问题领域的特征信息。l几种盲目搜索主要的异同 OPEN表中待扩展节点的顺序不同，但都具有某种固定的顺序。l盲目搜索的不足 效率低，耗费过多的计算空间与时间。41l估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 l应用节点“希望”程度（估价函数值）重排OPEN表3.3.2 有序搜索v实质 选择OPEN表上具有最小f值的节点

29、作为下一个要扩展的节点。3.3 启发式搜索42开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点得后继节点j，计算计算f(j)，提供返回提供返回节点节点i的指针，利用的指针，利用f(j)对对OPEN表重新排表重新排序，调整亲子关系及指针序，调整亲子关系及指针失败失败成功成功图图3.9有序搜索算法框图有序搜索算法框图是是否否是是否否3.3 启发式搜索v算法43l 例子八数码难题（8-puzzle problem）12384

30、567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：f(n)=d(n)+W(n)节点深度 错的棋子个数3.3 启发式搜索445714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图3.10 八数码难题的有序搜索树123845（4）73.3 启发式搜索6453.3.3 A*3.3.3 A*算法算法l估价函数的定义：对节点n定

31、义f f*(n)=g*(n)+h*(n)(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)g是g*的估计，h是h*的估计lA*算法的定义：定义定义1 1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定定义义2 2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定定义义3 3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。3.3 启发式搜索46