一种逆向改进型A*路径搜索算法

针对路径搜索和路径优化问题,提出了一种改进的A＊搜索算法。通过逆序搜索和优化估价函数两种方法,将无向搜索转化为有向搜索,将全局估价转变为局部估价,提高了算法效率,使之更适合处理大规模的路径优化问题,消除了复杂环境下路径搜索中可能出现的假“死”现象,同时也提供了一种提高大规模仿真速度的新思路—路径搜索与仿真过程分离。最后,通过仿真试验验证了算法的可行性和有效性。

Conversely Improved A Star Route Search Algorithm

An improved A* search algorithm was proposed to solve path finding and optimization problems. By altering the search direction and reforming the evaluate function, the undirected finding was transformed to directed finding, making the evaluation to be local. The improved algorithm is efficient especially on solving large-scale path-finding problems. Meanwhile, it avoids dead locks in path-finding. A new way was suggested which separated the search from simulation process to improve large scale simulation. Simulation experiment is shown to demonstrate the feasibility and validity of the algorithm.