一种适合于移动定位的路径搜索算法  

A PATH SEARCHING ALGORITHM FOR MOBILE LOCATION SERVICE

作　　者：谭志强[1] 廖湖声[1] 

机构地区：[1]北京工业大学计算机学院,北京100022

出　　处：《计算机应用与软件》2008年第7期44-47,共4页Computer Applications and Software

基　　金：北京市自然科学基金(4052006)

摘　　要：随着3G时代的来临,在快速发展LBS业务中,一个重要功能是获得手机与手机之间或手机到地图上指定位置的最短路径。通过将路网划分成主干网与支路网,并且使用二级R*树来索引路网边,给出了一种获取手机周边道路与计算最短路径的算法。分析了该算法的复杂度,在适当划分主干网与支路网后,该算法可以缩小搜索空间,提高搜索性能。With the rapid development of 3G mobile services, LBS software will play a more important role. Therefore it is crucial to obtain the shortest path between two cell phones or between a cell phone and a position on map. Based on the 2-level R ＊ -tree indexed road network and the division of road network to backbone and branches, a new algorithm is presented to get the nearest edges of road network to a cell phone position and to calculate the shortest path. The algorithm can greatly reduce the searching space and increase the searching speed.

关 键 词：LBS 最短路径 路网 移动定位 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] O157.5[自动化与计算机技术—控制科学与工程]