资源描述：
《人工智能与或图搜索课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章与或图搜索4.1问题归约法当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为问题归约法。可直接解答的问题称为本原问题。归约法的问题表示可由下列三部分组成：1） 一个初始问题的描述2） 一组把问题变成子问题的算符3） 一组本原问题的描述4.2与或图对问题归约的描述可以很方便地用一个与或图的结构来表示它。与节点：一个归约算符能够把单个问题变为几个子问题组成的集合，这时所有子问题都有解，该父辈节点才有解。这种关系称为“与
2、”关系，对应的节点成为与节点。或节点：几个算符适用于同一个问题，从而产生不同的后继问题集合。这时只要有一个后继集合有解，则意味该父辈问题有解，此时关系是“或”关系，对应节点为或节点。在图中N，M，H是或节点，B，C，D，E，F分别是与节点。ANMHBCDEF图与节点和或节点与或节点是针对与或树而言，对于一般的与或图有歧义目标目标初始节点sabcK—连接符：假设节点N被某个算符归约为一个包含K个子问题的替换集合，K1，我们用一个叫做K—连接符的超弧线把它们和节点N连接起来。每个K—连接符从一个父节点指向一个含有K个后继节点的集合，并说N有一
3、个外向连接符K。这种图称为超图，但我们仍把这种结构叫与或图。问题归约描述对应的结构就是一个与或图，原始问题描述对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况下，不出现任何与节点，此时的图成了普通图，问题归约描述也就成为状态空间描述。4.3与或图搜索在与或图上执行搜索的过程，其目的在于表明起始节点是有解的，也就是说，搜索不是去寻找目标节点，而是寻找一个解图。定义：一个与或图G中，从节点n到节点集N的解图记为G，G是G的子图。1．若n是N的一个元素，则G由一节点组成；2．若n有一个指向节点{n1…,nk}的外向
4、连接符K，使得从每一个ni到N有一个解图(i=1,…,k)，则G由节点n，连接符K，及{n1,…,nk}中的每一个节点到N的解图所组成；3．否则n到N不存在解图。目标目标初始节点解图：在搜索解图的过程中，还需要进行耗散值的计算。设连接符的耗散值规定为：k-连接符的耗散值=k，若解图的耗散值记为k(n,N)，则可递归计算如下：1．若n是N的一个元素，则k(n,N)=0；2．若n有一个外向连接符指向后继节点(n1…,ni)，并设该连接符的耗散值为Cn，则k(n,N)=Cn+k(n1,N)+…+k(ni,N)具有最小耗散值的解图称为最佳解图，其
5、值也用h*(n)标记。耗散值的计算:k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集Cn为连接符的耗散值…...i个nn1n2ni搜索过程还要标记能解节点(SOLVED)，为此给出如下定义： 能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有
6、一个子节点不能解时，该非终节点才不能解。不过与或图搜索与状态空间图搜索有所不同，说明如下：搜索目的是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索是否找到叶节点。因此，搜索有可解标示过程和不可解标示过程。初始节点被标示为可解，则搜索成功结束，初始节点被标示为不可解，则搜索失败。普通图的情况f(n)=g(n)+h(n)对n的评价实际是对从s到n这条路径的评价ns与或图:对局部图的评价目标目标初始节点abc两个过程图生成过程，即扩展节点从最优的局部途中选择一个节点扩展计算耗散值的过程对当前的局部图新计算耗散值下面我
7、们讨论一般与或图的启发式搜索算法——AO*算法。与A*算法不同，其评价函数f(n)=h(n)，只考虑h(n)这个分量，h(n)作为h*(n)的一个估计。过程AO*:1建立一个搜索图G，G:=s，计算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；开始时图G只包括s，耗散值估计为h(s)，若s是终节点,则标记上能解。2Untils已标记上SOLVED,do:3begin4G:=FIND(G)；根据连接符标记（指针）找出一个待扩展的局部解图G，指针后面步骤有说明。5n:=G中的任一非终节点;选一个非终结点作为当前节点
8、。6EXPAND(n),生成子节点集(ni)，G:=ADD((nj),G),计算q(nj)=h(nj)，其中njG，IFGOAL(nj)THENM(nj,SOLVED);把n的
