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

Method for automatic ship routing based on route stack

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

Focusing on the issue of high time complexity and spatial complexity of route binomial tree, a route automatic generation method based on route stack was proposed. Firstly, connecting the starting and ending points of the current track, the nearest barrier to the starting point was found. Secondly, the trajectory points were found by using the method that can bypass the obstacle area, one was selected to join the current track, and the rest was pressed into the stack. The current route was generated by bypassing all of the obstacles. Finally, another route was found by poping up the points from the stack one by one bypassing the obstacles. And the better route was found by comparing the current route and another route. The operation was repeated until the stack is empty, and the best route was selected. In the simulation experiments, accessing the route points dynamically from the current route, the best route was recorded in real-time. The construction of route binary tree was avoided by automatically generating the routed based on route stack for the same search results. Time complexity and spatial complexity were reduced by discarding the search for the current route when the distance between the points in the current route is much larger than the route obtained before.