人工智能与或图搜索

《人工智能与或图搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章与或图搜索4.1问题归约法4.2与或图4.3与或图搜索4.4AO*算法4.5博弈树的搜索4.1问题归约法当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为问题归约法。可直接解答的问题称为本原问题，它是不必证明的、自然成立的。归约法的问题表示可由下列三部分组成：1）一个初始问题的描述；2）一组把问题变成子问题的算子；3） 一组本原问题的描述问题归约由问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的一些子问题，……，一直进行到产生的子问题

2、都为本原问题，则问题得解。由于一问题所产生的若干子问题内的关系是并列的、同时的，所以，用与或图便能表示问题归约的状态空间。即对问题归约的描述可以很方便地用一个与或图的结构来表示它。4.2与或图与节点：一个归约算子能够把单个问题变为几个子问题组成的集合，这时只有当所有子问题都有解，该父辈节点才有解。这种关系称为“与”关系，对应的节点称为与节点。或节点：几个算子适用于同一个问题，从而产生不同的后继问题集合。这时只要有一个后继集合有解，则意味该父辈问题有解，此时关系是“或”关系，对应节点称为或节点。与节点由与运算连接，如图（a）中Q和R，并用一条弧线将相关的边

3、连接起来，这种弧线及所相关的边被称为超弧。或节点由或运算连接，如图4-1（b）中Q和R。与或图是一种普遍图，这种图被称为超图。也就是说，超图是存在超弧的图。一超弧所相关的边数（K）被称为该超弧的度，实现的连接为K-连接。K—连接符：假设节点N被某个算子归约为一个包含K个子问题的替换集合，K1，我们用一个叫做K—连接符的超弧线把它们和节点N连接起来。每个K—连接符从一个父节点指向一个含有K个后继节点的集合，并说N有一个外向连接符K。问题归约描述对应的结构就是一个与或图，原始问题描述对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况

4、下，不出现任何与节点（所有超弧的度都为1），此时的图成了普通图，问题归约描述也就成为状态空间描述。从图4-2所示的与或图中，节点n0有两个连接符：1-连接符指向节点n1；2-连接符指向节点集合{n4、n5}；对于节点n0来讲，n1可称为或节点，n4、n5可称为与节点。图4-2、与或图4.3与或图搜索在与或图上执行搜索的过程，其目的在于表明起始节点是有解的，也就是说，搜索不是去寻找目标节点，而是寻找一个解图。一个节点被称为是能解节点(SOLVED)，其递归定义为：1．终节点是能解节点（直接与本原问题相关联）；2．若非终节点有“或”子节点时，当且仅当其子节点

5、至少有一个能解，该非终节点才能解；3．若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才能解。一个节点被称为是不能解节点(UNSOLVED)，其递归定义为:1．没有后裔的非终节点是不能解的节点；2．若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不能解；3．若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不能解。一个解图就是那些能解节点的子图，是包含一节点（n）到目的节点集合（N）的、连通的能解节点的子图。其定义如下：一个与或图G中，从节点n到节点集N的解图记为G，G是G的子图。1．若n是N的一个

6、元素，则G由单个节点n组成；2．若n有一个指向节点集{n1…,nk}的外向连接符K，使得从每一个节点ni到N有一个解图(i=1,…,k)，则G由节点n，连接符K，以及{n1,…,nk}中的每一个节点到N的解图所组成；3．否则n到N不存在解图。如果n=s为初始节点，则此解图即为所求解问题的解图。在对普通图的解路求解或搜索中，一般须计算或估计其路径代价，同样地，在搜索与或图解图的过程中，也需要进行耗散值的计算。设连接符的耗散值规定为：k-连接符的耗散值=k，若解图的耗散值记为k(n,N)，则可递归计算如下：1．若n是N的一个元素，则k(n,N)=0；2．

7、若n有一个外向连接符指向后继节点集合{n1…,ni}，并设该连接符的耗散值为Cn，则k(n,N)=Cn+k(n1,N)+…+k(ni,N)。具有最小耗散值的解图称为最佳解图，其值也用h*(n)标记。求解问题的解图的值为h*(s)。解图的求法是：从节点n开始，正确选择一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。图4-3给出了上图所示与或图中n0{n7，n8}的三个解图（解图的耗散值分别为8，7，5）。图4-3、三个解图与或图搜索与状态空间图搜索的不同：搜索目的是证明起始节点是否可解，而可解节点是递归定义的，取决于后继

8、节点是否可解，即搜索是否找到可解的叶节点。因此，搜索有可解标示过程和不可解标示过