广义AND/OR图的自底向上启发式搜索算法BHAO~*

摘要

本文首先根据三角模概念,定义了一类新的更具普遍意义的广义AND/OR图。根据新定义的启发式函数h(n,x)以及广义AND/OR图的最佳解树之所有子树亦是最佳子解树的原理,提出了广义AND/OR图的自底向上的启发式搜索算法BHAO~*。文中证明了算法BHAO~*的可采纳性。本文还提出了两类新的启发式函数的单调限制概念,并据此研究了算法BHAQ~*的单调限制性质,研究了两个BHAO~*算法间的比较性质。