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

摘要

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