基于航路堆栈的航线自动生成方法

作者：吕**^*; 刘志强; 王娜

来源：计算机应用, 2018, 38(S1): 16-19.

• 最短航线
• 航路
• 复杂度
• 堆栈
• 避障

针对航路二叉树获取最优航迹方法中的时间复杂度和空间复杂度高的问题,提出了一种基于航路堆栈的航线自动生成方法。首先,连接当前航迹的起始点和终点,找到距离起点最近的障碍区;其次,利用障碍区绕行法找到能绕过该障碍物的可航迹点,选择一个加入到当前航迹,其余压入堆栈,重复操作直至绕过所有障碍物,生成一条航线,称为当前航线;最后,依次弹出当前堆栈中的栈顶节点,重复绕行障碍物操作找到另一条航线,与当前航线比较,选择两条中短的作为最优航线,直至栈空。仿真结果表明,在达到同样的搜索结果的前提下,利用基于航路堆栈的航线自动生成方法根据当前航线动态获取航路点,实时记录最优航线,避免了建立航路二叉树的过程。当发现当前航迹中的航路点之间的距离远大于之前获得的航迹时,不需要将当前航迹搜索完而直接放弃搜索当前航迹,大大降低了时间复杂度和空间复杂度。

• 单位
  深圳大学信息工程学院