机构地区: 浙江大学计算机科学与技术学院人工智能研究所
出 处: 《计算机学报》 1989年第11期821-828,共8页
摘 要: 本文建立了普通图和与/或图(指广义与/或图,它包括普通与/或图)的概念之间的相似对应关系,从而将图搜索中完美的理论、算法及分析方法成功地移植到与/或图搜索中来.以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.
领 域: [自动化与计算机技术] [自动化与计算机技术]