第三章1搜索推理技术

1AI为什么要研究search问题没有直接的解法;需要探索地求解;什么是搜索?根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程.包括两个方面：---找到从初始事实到问题最终答案的一条推理路径---找到的这条路径在时间和空间上复杂度最小2在图中寻找路径的方法初始节点初始数据库目标节点满足终止条件的数据库求取把一个数据库变换为另一个数据库的规则序列求得图中一条路径3.1图搜索策略图搜索控制策略3节点深度：根节点深度=0其它节点深度=父节点深度+101234路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径路径的耗散值（代价）一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。5盲目搜索图搜索策略启发式搜索宽度优先搜索深度优先搜索6搜索过程的要点:起始节点:对应于初始状态描述后继节点:把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点,称为该节点的后继节点,检查各后继节点看是否为目标节点.指针:从每个后继节点返回指向其父辈节点7两个主要的数据结构：OPEN表:存放刚生成的节点,是还未扩展的节点.一般是端节点.CLOSED表:存放将要扩展或已扩展的节点.或者是已被扩展但还没有在搜索树中生成后继节点的端节点,或者是非端节点8状态节点父节点编号状态节点父节点OPEN表CLOSED表9(1)把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G(2)检查OPEN表是否为空,若为空则问题无解,退出(3)把OPEN表的第一个节点取出放入CLOSED表,记该节点为n(4)考察n是否为目标节点.如是,则问题得解,退出(5)扩展节点n,生成一组子节点.把其中不是节点n先辈的那些节点记作集合M,并把这些子节点作为节点n的子节点加入G中搜索的一般过程：10(6)针对M中子节点的不同情况,分别进行处理1.对于那些未曾在G中出现过的M成员设置一个指向父节点(即n)的指针,并把它们放入OPEN表2.对于那些先前已在G中出现过的M成员,确定是否需要修改它指向父节点的指针3.对于那些先前已在G中出现并且已经扩展了的M成员,确定是否需要修改其后继节点指向父节点的指针(7)按某种搜索策略对OPEN表中的节点进行排序(8)转第(2)步11开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否3.1图搜索策略121,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；13SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}例子：G14这是一个通用的搜索过程,后面讨论的状态空间各种搜索策略都是其特例.各种搜索策略的主要区别就是对OPEN表中节点排序准则不同。算法结束后，将生成一个图G，称为搜索图。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为搜索树。从目标节点开始，将指针指向的状态回串起来，即找到一条解路径。树/不修改指针;图/修改指针。修改指针:找最优解。153.2盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法从初始节点开始,逐层对节点进行扩展并考察它是否为目标节点,在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。16开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2宽度优先算法框图是否是否3.2盲目搜索17宽（广）度优先搜索示意图18广度优先搜索方法分析：宽度优先搜索是图搜索一般过程的特殊情况，实际是将OPEN表作为“先进先出”的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止)。19例子八数码难题（8-puzzleproblem）1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。3.2盲目搜索201238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图3.4八数码难题的宽度优先搜索树134561238456712384567123845671238456712384567232425262712367822123845671238456712384567123845671238456712384567123845671415161718192021123845673.2盲目搜索21缺点:当目标节点距离初始节点较远时会产生许多无用的节点,搜索效率低。优点:只要问题有解,则总可以得到解,而且是最短路径的解。223.2.2深度优先搜索定义首先扩展最新产生的(即最深的)节点。从初始节点开始,在其子节点中选择一个节点进行考察，如果不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。算法防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2盲目搜索23深度优先搜索示意图24深度优先搜索方法分析：在深度优先搜索中，我们首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。2526缺点:如果目标节点不在搜索所进入的分支上,而该分支又是一个无穷分支,则就得不到解.因此该算法是不完备的。优点:如果目标节点恰好在搜索所进入的分支上,则可以较快地得到解。深度优先搜索方法的优缺点此外，用深度优先搜索求得的解，不一定是路径最短的解。27(1)起始节点(即根节点)的深度为0。(2)任何其它节点的深度等于其父辈节点深度加上1。首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。节点深度的定义：28对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。有界深度优先搜索29有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：（1）船太小，农夫每次只能带一样东西过河；（2）如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、狼、羊、菜都能不受损失地过河。画出相应的状态空间图。用人工智能搜索算法：301）老农携带羊羔过河，把狐狸和白菜留在南岸；2）老农到达北岸，把羊羔留在北岸，并独自回到南岸；3）老农携带狐狸过河，把白菜留在南岸；4）老农到达北岸，把狐狸留下，并带上羊羔回到南岸；5）老农把羊羔留在南岸，携带白菜过河；6）老农到达北岸，把白菜和狐狸留在北岸，独自回到南岸；7）老农最后携带羊羔过河，到达北岸。问题就此解决。31提示：（1）用四元组（农夫、狼、羊、菜）表示状态，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。（2）把每次过河的安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。3232用符号表示：M：代表老农(farmer)F：代表狐狸(fox)L：代表羊羔(lamb)C：代表白菜(cabbage)S：表示在南岸N：表示在北岸S-N：表示从南到北N-S：表示从北到南3333用（M，F，L，C）表示四个对象的一个状态,可有S和N两个值；改变状态的操作，可分别用1，0表示。表示对象“在船上”和“不在船上”两个值。如：初始状态：（S，S，S，S），终止状态：（N，N，N，N），中间状态：S-N（1，1，0，0）3434老农和其他三个对象不在同一岸（狐狸要吃羊羔，羊羔要吃白菜）(S,N,N,N)：老农在南岸，其他三个对象在北岸(N,S,S,S)：老农在北岸，其他三个对象在南岸羊羔和白菜在同一岸（羊羔要吃白菜）(S,S,N,N)：老农和狐狸在南岸，羊羔和白菜在北岸(N,N,S,S)：老农和狐狸在北岸，羊羔和白菜在南岸狐狸和羊羔在同一岸（狐狸要吃羊羔）(S,N,N,S)：老农和白菜在南岸，狐狸和羊羔在北岸(N,S,S,N)：老农和白菜在北岸，狐狸和羊羔在南岸因老农、狐狸、羊羔和白菜都有2种状态，即在南岸和北岸，所以4个对象的总状态数为2*2*2*2=16种，按条件要求，有几种状态不能存在，如表所示。所以只有10种可能状态。3535根据题意，在10种可能的安全状态里，只有4种是有可能的操作：1）老农独自过河（包括从南岸到北岸和从北岸到南岸，下同）2）老农携带狐狸过河3）老农携带羊羔过河4）老农携带白菜过河3636问题求解过程的表示373.2.3等代价搜索定义是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。算法若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。3.2盲目搜索38有关约定起始节点记为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是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否3.2盲