广义与或树的启发式搜索算法BTAO

HEURISTIC SEARCH ALGORITHM BTAO FOR GENERAL AND/OR TREE

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

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.