论文部分内容阅读
提出了一种高效可靠的限制搜索区域的最优路径算法.该算法是基于典型城市路网的共同特征,而不是某个特定城市的统计信息提出的,它可以应用在不同的城市路网中.针对从源站点到目的站点不同的欧式距离,算法分别在两类不同大小的椭圆内搜索最短路径.理论计算和实验结果都表明,当源站点和目的站点相距较远时,与椭圆限制搜索区域算法相比,该算法可以降低33%47%的时间复杂度,而不会影响查询结果的准确性.
An efficient and reliable optimal path algorithm to restrict the search area is proposed.The algorithm is based on the common feature of a typical urban road network and not based on the statistical information of a particular city and can be applied in different urban road networks For the different Euclidean distance from the source site to the destination site, the algorithm separately searches for the shortest path in two types of ellipses with different sizes.Theoretical calculation and experimental results show that when the source site and the destination site are far apart, Compared with the regional algorithm, the algorithm can reduce the time complexity by 33% and 47% without affecting the accuracy of the query result.