摘要： 本文根据乐观决策准则提出了广义与或树这一新概念,证明了广义与或树的耗散值与其最佳解树的耗散值是等价的。根据新定义的启发式函数h~(Tr)(n,x),提出了广义与或树的自底向上的启发式算法BTAO~*。算法BTAO~*是可采纳的,即定能找到最佳解树,进而求解出广义与或树的耗散值。

关键词: 算法, 广义与或树, 启发式函数h~(Tr)(n,x), 启发式算法BTAO~*, 耗散值

Abstract: A new general AND/OR tree is defined in terms of the non-pessimistic decision rule, which is proved to be equivalent in cost value to its best solution tree. Thus, based on the newly-defined heuristic function hTr(n, x), the backward heuristic algorithm BTAO for a general AND/OR Tree is presented and can be rendered acceptable to solving the cost value of a general AND/OR tree.