摘要
本文首先根据三角模概念,定义了一类新的更具普遍意义的广义AND/OR图。根据新定义的启发式函数h(n,x)以及广义AND/OR图的最佳解树之所有子树亦是最佳子解树的原理,提出了广义AND/OR图的自底向上的启发式搜索算法BHAO~*。文中证明了算法BHAO~*的可采纳性。本文还提出了两类新的启发式函数的单调限制概念,并据此研究了算法BHAQ~*的单调限制性质,研究了两个BHAO~*算法间的比较性质。
A new type of general AND/OR graph is defined on triangle norm. In terms of the new-defined heuristic function h(n,x) and the principle that all subtrees of the optimum solulion tree for general AND/OR graph are also optimum solution subtrees, the backward heuristic search algorithm BHAO* for general AND/OR graph is presented. The admissibility of algorithm BHAO* is proved. Furthermore, two new concepts of monotone restrictions for heuristic function h(n,x) are defined.Based on this,the characteristic of monotone restrictions for algorithm BHAO* is investigated, and the comparison between two algorithms BHAO* is dscussed.
关键词
人工智能
启发式算法
搜索论
artificial intelligence
heuristic approach
search theory
