摘要
本文建立了普通图和与/或图(指广义与/或图,它包括普通与/或图)的概念之间的相似对应关系,从而将图搜索中完美的理论、算法及分析方法成功地移植到与/或图搜索中来.以A~*算法为例,本文描述了一个类似于A~*的与/或图搜索算法AO.A~*,并分析了其性能. 本文还对与/或图搜索算法的复杂度的定义进行了讨论,并指出了G.Levi的复杂度定义的某些缺陷.
The similarity correspondence between the concepts of graph and these of generalized And/Or graph (GAG, it includes, standard And/Or graph) are presented. With this correspondence, the perfect theory, algorithms and analysis methods of graph search can be transferred to GAG search successfully. A GAG search algorithm AO.A*, which is transferred from graph search algorithm A*, is described, and its properties are analyzed. Some shortcoming of G. Levi's definition about complexity of GAG search algorithms is pointed out and a new complexity definition is proposed.
出处
《计算机学报》
EI
CSCD
北大核心
1989年第11期821-828,共8页
Chinese Journal of Computers
