《人工智能导论：与或图搜索问题》由会员分享，可在线阅读，更多相关《人工智能导论：与或图搜索问题（23页珍藏版）》请在金锄头文库上搜索。
1、第2章 与或图搜索问题前一章介绍了状态空间搜索问题及有关的搜索算法。这些问题的特点是一个节点的后继节点之间是“或”的关系，只要一个节点得以求解，则该节点也就被求解了。从初始节点到目标节点之间，求解的是一条路径，也就是一个节点的序列。但在某些问题中，一个节点是否被求解，取决于该节点的部分或全部后继节点被求解，而不只是一个后继节点被求解。也就是说，对于该节点来说，其部分或全部后继节点是“与”的关系。这就是本章要讨论的与或图搜索问题。2.1与或图的搜索在现实世界中，经常会遇到这样的问题：一个问题可以有几种求解方法，只要其中一种方法可以求解问题，则该问题被求解。也就是说，对求解该问题来说，方法之间是“
2、或”的关系。但在用每一种方法求解时，又可能需要求解几个子问题，这些子问题必须全部求解，才可能用该方法求解原始问题。也就是说，这些子问题之间是“与”的关系。此类问题可以用与或图来表示。通常我们要讨论与或图的一般情况（与或树是其特例）。在一个与或图中，一个节点可能会产生于不同的节点，比如节点c同时是节点a和节点b的后继节点。在这种情况下，可能会出现对于节点a来说c是“与”节点，而对于节点b来说，c是“或”节点的情况发生。也就是说，一个节点是“与”节点还是“或”节点，是与其来源有关的。为了避免混淆不清，通常不把与或图中节点叫做与节点或者或节点，而是引入一个适合于与或图的更一般的标记，而在称谓上沿用习
3、惯，仍把这种结构称作与或图。当然在讨论与或树时仍继续用“与”、“或”节点的称呼。图2.1给出一个简单的与或图例子，下面就来说明它的标记方法。这个图也称做超图，节点间是用超弧线（或连接符）来连接，如一个父节点和一组后继节点的关系可用若干个连接符来标记，并规定k-连接符是从一个父节点指向一组k个后继节点的节点集。这时若节点间全是1-连接符（相当于一条弧线）连接，显然这就是一般图的标记法，得到的就是与或图的特例普通图。n0n1n2n3n4n5n6n7n8图2.1与或图从图2.1可以看出，节点n0有两个连接符：1-连接符指向节点n1；2-连接符指向节点集n4，n5。该2-连接符还用一小段圆弧括起来（对
4、k1的k-连接符都应有小圆弧标记），以表示子节点间“与”的关系。可以看出这种标记法在节点间具有明确的关系。显然若用原先的术语，则对父节点n0来说，n4、n5是两个“与”节点，而n1可称为“或”节点；而n8既是n5的一个“与”节点，又是n4的一个“或”节点，混淆难于避免。另外也把图中没有任何父节点的节点叫根节点，没有任何后继节点的节点叫端节点或叶节点。一个可分解产生式系统规定了一个隐含的与或图，初始数据库对应于图中的初始节点，它有一个外向的连接符连到它的一组后继节点，每个后继节点分别对应初始数据库中的一个分量；可应用于分量数据库的每条产生式规则，也对应于一个连接符，它指向的节点则相应于应用规则后
5、生成的数据库；满足产生式系统结束条件的数据库是对应的一组终节点；产生式系统的任务是搜索从初始节点到一组终节点集N的一个解图。下面就解图及其耗散值的概念和定义、能解不能解节点的定义作些说明。与或图中某一个节点n到节点集N的一个解图类似于普通图中的一条解路径。解图的求法是：从节点n开始，正确选择一个外向连接符，再从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。图2.2给出n0n7，n8的三个解图。n0n4n5n7n8n0n1n3n5n6n7n8n0n4n5n7n8图2.2三个解图在与或图是无环（即不存在这样的节点其后继节
6、后同时又是它的祖先）的假定下，解图可递归定义如下：定义：一个与或图G中，从节点n到节点集N的解图记为，是G的子图。 n是N的一个元素，则由单一节点组成；若n有一个指向节点n1，nk的外向连接符K，使得从每一个ni到N有一个解图（i=1，k），则由节点n、连接符K、及n1，nk中的每一个节点到N的解图所组成；否则n到N不存在解图。同样我们可以递归定义局部图：定义：单一节点是一个局部图；对于一个局部图的任意叶节点n，选择一个n的外向连接符K，则该局部图、外向连接符K，以及K所连接的n的后继节点一起组成的图，仍然组成一个局部图。在搜索解图的过程中，还须要进行耗散值的计算。若解图的耗散值记为k（n，N
7、），则可递归计算如下：若n是N的一个元素，则k(n，N)0；若n是一个外向连接符指向后继节点n1，ni，并设该连接符的耗散值为Cn，则k(n，N)Cn+ k(n1，N) + + k(ni，N)根据这个定义，在假定k连接符的耗散值为k的情况下，图2.2三个解图的耗散值计算结果分别为8、7和5。具有最小耗散值的解图称为最佳解图，其值也用h*(n)标记，上例中h*(n0)5。同样，也可以计算一个局部图的耗散值。如果我们同样将局部图的耗散值记为k(n，N)，则： n是局部图的一个叶节点，则k(n，N)h(n)；若n有一个外向连接符指向后继节点n1，ni，并设该连接符的耗散值为Cn，则k(n，N)Cn+
8、 k(n1，N) + + k(ni，N)其中，h(n)表示节点n到目标节点集的最佳解图耗散值的估计。此外搜索过程还要标记能解节点(SOLVED)，为此给出如下定义：能解节点(SOLVED)终节点是能解节点；若非终节点有“或”子节点时，当且仅当其子节点至少有一能解，该非终节点才能解；若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才能解。不能解节点(UNSOLVED)；没有后裔的非终节点是不能解节点；若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不能解；若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不能解。2.2与或图的启发式搜索算法AO
9、*启发式的与或图搜索过程和普通图类似，也是通过评价函数f(n)来引导搜索过程。对于与或图来说，由于局部图中有多个叶节点，不能像普通图搜索那样，通过对某一个节点的评价来实现对整个局部图的评价。在普通图搜索中，f(n)=g(n)+h(n)，表面上是对n的评价，实际上是对通过n的这条路径的评价。因此对于与或图搜索来说，就是通过对局部图的评价来选择待扩展的节点。下面首先讨论AO*算法本身，然后再通过示例说明搜索过程以及与A*算法的某些差别。1AO*算法过程AO*：建立一个搜索图G，G:s，计算q(s)h（s），IF GOAL（s）THEN M（s，SOLVED）；开始时图G只包括s，耗散值估计为h(s
10、)，若s是终节点，则标记上能解。Until s已标记上SOLVED，do：beginG:FIND(G)；根据连接符标记（指针）找出一个待扩展的局部解图G。n:G中的任一非终节点；选一个非终节点作为当前节点。EXPAND(n)，生成子节点集nj，计算q(nj)h(nj)，其中njG，G:ADD(nj，G)，IF GOAL(nj) THEN M(nj，SOLVED)；对G中未出现的子节点计算耗散值，若有终节点则加能解标记，然后把n的子节点添加到G中。S:n；建立含n的单一节点集合S。Until S为空，do：beginREMOVE(m，S)，mcS；这个m的子节点mc应不在S中。修改m的耗散值q(
11、m)：对m指向节点集n1i，n2i，nki的每一个连接符i分别计算qi：qi(m)Ci+q(n1i)+q(nki)，q(m):min qi(m)；对m的i个连接符，取计算结果最小的那个耗散值为q(m)。加指针到min qi(m)的连接符上，或把指针修改到min qi(m)的连接符上，即原来指针与新确定的不一致时应删去。IF M(nji，SOLVED) THEN M(m，SOLVED)；若该连接符的所有子节点都是能解的，则m也标上能解。IF M(m，SOLVED)(q(m)q0(m)THEN ADD(ma，S)；m能解或修正的耗散值与原先估算q0不同，则把m的所有先辈节点ma添加到S中。ende
12、nd这个算法可划分成两个操作阶段：第一阶段是46步，完成自顶向下的图生成操作，先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终节点进行扩展，并对其后继节点赋估计耗散值和加能解标记。第二阶段是712步，完成自底向上的耗散值修正计算、连接符（即指针）的标记以及节点的能解标记。耗散值的修正从刚被扩展的节点n开始，其修正耗散值q（n）取估计h（n）的所有值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值，只有下层节点耗散值修正后，才可能影响上一层节点的耗散值，因此必须自底向上一直修正到初始节点。这由算法中的内循环过程完成，下面就用图2.1的例子来说明算法的
13、应用过程。2算法应用举例设某个问题的状态空间如图2.1所示，并定义了某个启发函数h（n），我们来看一看解图的搜索过程。为了使用方便，将h(n)函数对图2.1中各节点的假想估值先列写如下（实际应用中是节点生成出来之后才根据h(n)定义式计算）：h(n0)3，h(n1)2，h(n2)4，h(n3)4，h(n4)1，h(n5)1，h(n6)2，h(n7)h(n8)0（目标节点）。此外我们假设k-连接符的耗散值为k。图2.3给出了使用AO*算法对图2.1所示与或图的搜索过程。开始时，只有一个初始节点n0，n0被扩展，生成出节点n1、n4和n5，一个1连接符指向n1，一个2连接符指向n4和n5。这两个连
14、接符之间是“或”的关系。由已知条件知：h(n1)=2，h(n4)=1，h(n5)=1，并且已经假设k连接符的耗散值为k。所以由n0的1连接符，可以计算出n0的耗散值（即算法中的q值，为了与算法一直，以下用q值表示）为（n0的1连接符的耗散值）（n1的q值）123。对于目前得到的局部图来说，n1是一个叶节点，所以其q值用h值（2）代替。由n0的2连接符，可以计算出n0的q值为（n0的2连接符的耗散值）（n4的q值）（n5的q值）2114。在两个不同渠道计算得到的耗散值中取最小值作为n0的q值，并设置一个指针指向提供该耗散值的连接符。在这里34，所以n0的q值为3，指针所指向的连接符为n0的1连接
15、符。至此算法的第一个循环结束。搜索图如图2.3（a）所示。在第二个循环中，首先从n0开始，沿指针所指向的连接符，寻找一个未扩展的非终节点。这时找到的是n1节点。扩展n1节点，生成出节点n2和n3，两个节点分别通过1连接符与n1连接。由于h(n2)=h(n3)=4，所以通过这两个连接符计算的耗散值也一样，均为5。取其最小者还是5，从而更新n1的q值为5。由于耗散值相等，所以指向连接符的指针可以指向两个连接符中的任何一个，假定指向了n3这一边。由于n1的q值由2更新为5，所以需要从新计算n0的q值。对于n0来说，此时从1连接符这边算得的耗散值为6，大于从2连接符这边得到的耗散值4，所以n0的q值更新为4，并将指向连接符的指针由指向1连接符改为指向2连接符。注意，这时由n1出发的指向连接符的
