双向启发式图搜索算法BRA之研究

INVESTIGATION ON BIDIRECTIONAL HEURISTIC GRAPH SEARCH ALGORITHM BRA

本文在[1]中基于模运算,提出了随机产生式系统的启发式图搜索算法RA~*.本文提出一个随机产生式系统的双向搜索的启发式图搜索算法BRA~*,证明了算法BRA~*的可采纳性,并得到了一些新的可采纳性结果.算法BRA~*的搜索效率比算法RA~*高.若启发式估价函数满足单调性限制,通过使用NP操作,则算法BRA~*的搜索空间将进一步减少.

A bidirectional heuristic graph search algorithm BRA* on random production system is presented with its admissibility proved and some new admissibility results obtained. The search efficiency of BRA* is higher than that of RA*, a heuristic graph search algorithm on random production system in [1] . If the heuristic evaluation function satisfies the monotonous restriction, the search space of BRA* will be educed by the use of NP operation.