基于蚁群迭代算法的近似测地线计算

Approximate geodesic calculation based on ant colony iterative algorithm

为了提高两点之间近似测地线的计算精确度,提出一种蚁群迭代算法.在此算法中,对于任意一个地形,首先建立其垂直映射平面图,在平面图上进行初步网格划分,并用蚁群算法求出一条最短路径;再对网格不断进行加密划分,每一次加密处理网格之后都用蚁群算法计算精确度更高的最短路径,以此优化加密前求出的路径.该算法可有效避免待求两点之间图形解析式的困扰,并且采用自适应的方式寻找适当的网格规模,提高近似测地线的精确度.实验结果表明该算法在近似测地线的计算中是有效的.

An ant colony iterative algorithm is proposed to enhance the calculation accuracy of the approximate geodesic between two points.In this algorithm,for any terrain,its corresponding vertical mapping planar graph is constructed firstly,and a preliminary grid partition is carried out on this planar graph,a shortest path is computed by using the ant colony algorithm based on this partition.Then,the grid is subdivided and a more accurate shortest path is computed to optimize the previous path before subdivided.This algorithm avoids the trouble of finding the terrain formula.Moreover,the best grid partition can be determined in a self-adaptive way,which significantly improves the accuracy of the approximate geodesic.This algorithm is shown to be effective by a few experiments.