摘要
本文首先定义了一类新的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图中去。
AND/OR graphs of a new type is defined. The nodes of an AND/OR graph are either AND or OR but not both and the cost of solution paths is measured by triangle norm S. As the generalization of the general AND/OR graph algorithm AO*, the heuristic evaluation function F of the new graphs is decomposed into G and H, likewise f = g+h for ordinary graphs. Based on this, a new AND/OR graph heuristic search algorithm NAO* is presented. It is concluded that NAO* is essentially different from AO* and it is admissible if H≤H*.
出处
《计算机学报》
EI
CSCD
北大核心
1991年第1期14-22,共9页
Chinese Journal of Computers
基金
国家自然科学基金
关键词
图
启发式
NAO
AND/OR
搜索算法
AND/OR graph, heuristic graph search, heuristic evaluation function, algorithm.
