作者:赵晓; 王铮; 黄程侃; 赵燕伟 期刊:《机器人》 2018年第06期
为了解决较大场景下A*寻路算法存在的内存开销大、计算时间长等问题,本文在A*算法的基础上,结合跳点搜索算法,提出一种改进的A*算法.该算法通过筛选跳点进行扩展,直到生成最终路径,扩展过程中使用跳点代替A*算法中大量可能被添加到OpenList和ClosedList的不必要节点,从而减少计算量.为了验证改进A*算法的有效性,分别在不同尺寸的2维栅格地图中进行仿真,仿真结果表明,相比A*算法,改进A*算法在寻路过程中扩展更少的节点,寻路速度更快...
作者:邱磊 期刊:《中央民族大学学报·哲学社会科学版》 2014年第01期
等价网格环境下的寻路问题普遍存在于机器人、电子游戏等应用领域.其中,最先进的技术都被分层寻路算法所主导,这些算法速度快且内存开销较小,但通常返回的路径都是次优的.本文提出了一个新颖的、特定于网格的搜索策略,该策略速度快、最优且无需内存开销,其算法可以描述为一个宏算符,该宏算符识别和有选择地扩展网格地图上的仅仅某些节点,我们称之为跳点,连接两个跳点的路径上的中间节点将不再被扩展.我们将证明该方法计算出的解总...