人工智能-第三搜索推理技术

第三搜索推理技术从问题的表示到问题的解决是一个求解的过程，也就是搜索过程。在这一过程中，采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。本章首先介绍图搜索策略的一般过程，接着讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理，然后研究一些比较新的能够求解比较复杂问题的推理技术。第三确定性推理§3.1图搜索策略§3.2盲目搜索§3.3启发式搜索§3.4消解原理§3.5规则演绎系统§3.6产生式系统§3.7非单调推理第三搜索推理技术一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。Sg§3.1图搜索策略§3.1图搜索策略一.问题描述(图搜索问题描述)把求解问题看成一个状态图，求初始节点到目标节点的路径。§3.1.1图搜索策略回顾一下图论中几个术语的含义。节点深度：根节点的深度为0,其他节点的深度规定为父节点深度加1,即dn+1=dn+1。路径：设一节点序列为(n0、n1,…,ni,…,nk),对i=1,2,…,k,若节点ni-1都具有一个后继节点ni,则该节点序列称为节点n0到节点nK长度为k的一条路径。路径耗散值：令C(ni,nj)为节点ni到nj这段路径(或弧线)的耗散值,一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。路径耗散值可按如下式递归公式计算:C(ni,t)=C(ni,nj)+C(nj,t)C(nj,t)为ni→t这条路径的耗散值。§3.1.1图搜索策略回顾一下图论中几个术语的含义。扩展一个节点:后继节点操作符(相当于可应用规则)作用到节点(对应于某一状态描述)上,生成出其所有后继节点(新状态),并给出连接弧线的耗散值(相当于使用规则的代价),这个过程叫做扩展一个节点。扩展节点可使定义的隐含图生成为显式表示的状态空间图。§3.1.1图搜索策略二.图搜索过程S～起始结点G～搜索图OPEN～表存放未扩展节点CLOSED～表存放已扩展节点1.图搜索过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP:若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n。§3.1.1图搜索策略(5)若n为一目标节点n，则有解并成功退出。此解是追踪图G中沿着指针从n到s这条路径而得到的。(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继结点添入图G中。(7)对于那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已经在CLOSED表上的每一个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP§3.1.1图搜索策略举例：SABCDEMFS1.SOPEN(S)CLOSED()2.AOPEN(A,B)CLOSED(S)3.BOPRN(B,C,D)CLOSED(S,A)4.COPEN(C,D,E)CLOSED(S,A,B)5.DOPEN(D,E)CLOSED(S,A,B,C)6.EOPEN(E,M,F)CLOSED(S,A,B,C,D)7.N求解目标节点235647384ק3.1.1图搜索策略2.流程图开始把S放表入OPEN表中OPEN表为空表把第一个节点n从OPEN表移至CLOSED表N为目标节点把节点n的后继节点放入OPEN表，提供返回节点n的指针修正指针方向重排OPEN表失败成功是是①②③§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略§3.1.1图搜索策略3.遗留问题①n的某后继节点已在OPEN表中或CLOSED表中有了是否需要修改指针，对已存在的后继节点②按什么方式重排OPEN表宽度优先搜索深度优先搜索等代价搜索搜索控制方法§3.2盲目搜索盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索，又叫做无信息搜索。一般只适用于求解比较简单的问题。典型的盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜索方法。§3.2盲目搜索一.宽度优先搜索(一).宽度优先搜索以接近起始节点的程度依次扩展节点从根结点开始,每次都要扫遍同层的各个结点,若没有找到目标,则再往下一层扫描(扫描下一层的所有子结点),直到找到目标或没有找到目标退出系统(此种属于没有解的情况)。§3.2盲目搜索(二).流程算法扩展节点：把它的后继节点放入OPEN表的末端1.搜索算法⑴把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)⑵如果OPEN表是一个空表，则没有解，失败退出；否则继续。⑶把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。⑷扩展节点n。如果没有后继节点，则转向第⑵步。⑸把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。⑹如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第⑵步§3.2盲目搜索2.流程图开始把S放表入OPEN表OPEN表为空表把第一个节点n从OPEN表移至CLOSED表把节点n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功是是是否有任何后继节点为目标节点？§3.2盲目搜索3.举例：八数码难题初始棋局目标棋局2831476512384765283147652318476528316475283147652831476583214765283714652318476523184765283164752831647528143765283145768321476528371465123847652341876528364175283167542814376528314576832147658132476528374615283714651237846512384756123456789101112131415161718192021222325262728S0Sg§3.2盲目搜索(三).宽度优先搜索的性质•当问题有解时，一定能找到解•当问题为单位耗散值，且问题有解时，一定能找到最优解•方法与问题无关，具有通用性•效率较低•属于图搜索方法§3.2盲目搜索二．深度优先搜索(一).深度优先搜索总是先扩展最新产生的节点§3.2盲目搜索(二).OPEN表的排列算法对于许多问题，其状态搜索树的深度可能为无限深或者可能至少要比某个可接受的解答序列的已知深度上限还要深，为了避免考虑太长的路径：1.深度界限：规定的一个节点扩展的最大深度2.扩展节点：若不等于最大深度，将后裔节点放入OPEN表的前头。§3.2盲目搜索3.搜索算法⑴把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)⑵如果OPEN表是一个空表，则失败退出。⑶把第一个节点(节点n)从OPEN表移到CLOSED表。⑷如果节点n的深度等于最大深度，则转向第⑵步。⑸扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2.)⑹如果后继节点中有任一个为目标节点，则求得一个解答，成功退出；否则转向第⑵步§3.2盲目搜索4.流程图开始把S放表入OPEN表OPEN表为空表把OPEN表中第一个节点n移至CLOSED表扩展节点n，把后裔放入OPEN表的前头失败成功是是是否有任何后继节点为目标节点？S是否为目标节点？节点n的深度是否等于深度界限？是成功是否§3.2盲目搜索5.举例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标§3.2盲目搜索(三).深度优先搜索的性质•一般不能保证找到最优解•当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制•最坏情况时，搜索空间等同于穷举•是一个通用的与问题无关的方法§3.2盲目搜索三、等代价搜索(一).等代价搜索1.问题的提出：有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解，这可通过代价来描述2.代价(1)从节点I到它的后继节点j的连线弧线代价记为C(i,j).(2)从起始节点到任一节点i的路径代价记为g(i).3.等价搜索每次扩展的是代价最小的节点。§3.2盲目搜索(二).扩展算法扩展节点I对于节点I的每个后继节点，计算g(j)=g(i)+c(i,j)按g(j)升序插入到OPEN表中。§3.3启发式搜索启发式搜索是利用问题拥有的启发信息来引导搜索,达到减少搜索范围,降低问题复杂度的目的,这种利用启发信息的搜索过程都称为启发式搜索方法。§3.3启发式搜索§3.3.1启发式搜索策略一.启发信息1.启发信息：具体问题领域的可用来简化搜索的特性信息2.种类：(1)用于决定要扩展的下一个节点(以免象宽度优先或深度优先搜索中那样盲目地扩展)(2)在扩展一个节点的过程中，用于决定要生成那一个或那几个后继节点(以免盲目地同时生成所有可能的节点)(3)用于决定某些应该从搜索树中抛弃或修剪的节点§3.3启发式搜索§3.3.1启发式搜索策略二.启发式搜索1.启发式搜索：利用启发信息的搜索方法。本节只讨论利用第一种启发信息的搜索2.有序搜索：利用第一种启发信息，总是选择“最有希望”的节点作为下一个被扩展的节点。§3.3启发式搜索§3.3.2估价函数一.估价函数用来估算节点希望程度的量度二.估价函数考虑因素1.起始节点到此节点的距离(以减少搜索工作量为出发点)2.经过此节点到达目标的代价(以最小代价为出发点)三.估价函数表示f(n)我们可以用f函数来排列GRAPHSEARCH第8步中OPEN表上的节点。§3.3启发式搜索§3.3.3有序搜索一.有序搜索算法开始把S放表入OPEN表，计算f(s)OPEN=NIL?选取OPEN表中f值最小的节点I放入CLOSED表扩展i,得后继节点j，计算f(j),提供返回i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功是是i=Sg§3.3启发式搜索其中扩展节点i有下列几步对有i的每一个后继节点j:1.计算f(j)2.如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。3.如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则⑴以此新值取代旧值⑵从j指向i,而不是指向它的父辈节点。⑶如果节点j在CLOSED表中，则把它移回OPEN表。§3.3启发式搜索有序搜索的有效性直接取决于f的选择二.举例八数码难题起始节点目标节点选用的估价函数f(n)=d(n)+w(n)d(n)是搜索树中节点n的深度W(n)用来计算对应于节点n中错放棋子个数这样起始节点f=0+4=42831647512384765§3.3启发式搜索1.OPEN={1}CLOSED={}2.OPEN={3,1、2,1、4,1}CLOSED={1,0}3.OPEN={5,3、6,3、2,1、4,1、7,3}CLOSED={1,0、3,1}4.OPEN={6,3、2,1、4,1、7,3、8,5、9,5}CLOSED=