模S下的AND/OR图NAO算法的可采纳性研究

A Research on Admissibility of AND/OR Graph Algorithm NAO Based on Norm S

和Nilsson教授的观点不同,本文首先定义了一类新的AND/OR图:图中的结点或者是AND结点或者是OR结点,而不能是混合型结点,并定义其路径耗散值用三角模S来度量和计算,使其更具有普遍意义。和通常的AND/OR图AO算法不一样,本文依照普通图A算法中的启发式估价函数f=g+h,将新AND/OR图中的启发式估价函数F分成G、H两部分,并据此提出了NAO算法。本文的结论表明:NAO算法与AO算法有本质的不同;当H≤H时NAO可采纳,而且其结果极易推广到一般的AND/OR图中去。

Unlike professor Nilsson's viewpoint, a new type of AND/OR graphs is firstly defined in this paper:the nodes of an AND/OR graph are either AND or OR but not both. And then in new AND/OR graphs, the cost of solution paths is measured by triangle norm S.Unlike the general AND/OR graph algorithm Ao*[1]AO*, the heuristic evaluation function F of AND/OR graphs is decomposed into G and H according to f=g + h for ordinary graphs. Based on this, A new AND/OR graph heuristic search algorithm NAO* is presented. The conclusion shows that the algorithm NAO* is essentially different from AO* and is admissible if H≤H*.