解空间搜索中的B*树算法

B* Tree Algorithm for Searching Resolution Space

本文给出了在人工智能求解中的一种算法——B*树算法。文章比较了B*树算法与A*树算法、BB算法的不同处和特点,较详细地叙述了在两种决策策略下B*树返回修正值的产生过程,并用算法语言对B*树算法作了具体描述。

For speeding up the searching in resolution space, there are A* tree algorithm and Branch and Bound (BB) algorithm. Their efficiencies are much higher than those of blind depth-first searching or breadth-first searching. There are however,still too many expanding active nodes which will be preserved in the memory in the procedure of searching when we use those two methods. It will cost many memory elements. When comparing which node is better, it will cost a great deal of CPU time. In the adversary tree one layer is max layer, the other is min layer. If the pessimistic value of a node in the max layer is no worse than the optimistic value of sibling nodes, we can prune subtrees 1he roots of which are sibling nodes. We do similar process in the min layer; the large in the max layer corresponds to the small in the min layer. In the B* tree algorithm we use back-up value of optimistic value and pessimistic value, it is quite different from the BB algorithm. Due to the usage of back-up value, the expanding active nodes are decreased to a great extent. In the present paper, we offer the B* trce algorithm and compare the speed of it to that of the Best First algorithm.