单边矩形扩展 A* 算法

        摘 要：提出了一种新的单边矩形扩展 A *（ REA*）算法．新算法采用受迫扩展规则，在以矩形单元探索地 图的过程中，用单条公共边取代相邻矩形的 2 条冗余独立边，从而提高了算法效率，简化了终止条件，优化了路 径质量．在无需对地图进行预处理的情况下，算法速度比传统 A * 算法提高 1 个数量级以上．算法能够保证得到栅 格最优的路径点序列，且最终路径（由路径点间直线组成）总是比栅格最优路径更短．典型地图集上的实验结果 表明，相比于现有 R EA* 算法，新算法提高了对复杂地图的处理能力和算法效率上限．新算法路径长度更短，路 径转折次数更少，因此路径质量更优．除了在低复杂且不开阔的地图上外，新算法平均效率也高于 R EA* 算法．