一种基于随机游走的A~*算法

A~* algorithm based on random walk

针对A~*算法中出现的高原搜索现象,结合蒙特卡罗随机游走思想提出了一种基于随机游走的A~*算法。其基本思想是当A~*算法陷入高原搜索期时,通过随机游走策略及时找到一个节点逃离该高原搜索期。针对A~*算法何时陷入高原搜索期的问题提出了一种新的检测高原搜索期的方法,即当连续扩展n次节点的启发值都比上一次最后扩展出节点的启发值大时,则认为搜索陷入了高原搜索期。实验结果验证了该方法的有效性。

A＊ algorithm based on random walk combining with Monte-Carlo random walk is proposed to solve the plateau exploration in A＊ algorithm. When the A＊ algorithm falls into the plateau cxploration, a random walk algorithm is employed to help it escape from the plateaus. In addition, a new method is proposed to test plateau exploration. The phenomenon is named plateau exploration as it continuously expand states n times without reducing the heuristic value compared with last states＇ expanded on last expansion. Experimental results prove the effectiveness of the improved A＊ algorithm.