基于子路径集的启发式图搜索算法RA的改进算法SPRA

Improved Algorithm SPRA for Heuristic Graph Search Algorithm RA Based on the Concept of Subpath Sets

本文在笔者以前研究的基础上,提出了子路径集这一新概念,并进而提出了算法RA~*的改进算法SPRA~*,文中证明了算法SPRA~*的可采纳性。从算法所扩展的节点数目这一角度来看,算法SPRA~*明显比算法RA~*好。

In this paper, the new concept of subpath sets is presented. Based on this concept, the improved algorithm SPRA* for heuristic graph search algorithm RA* is investigated. Algorithm SPRA* is admissible . From the viewpoint of the extended node number, algorithm SPRA* is better than algorithm RA*.