| 典型城市路网中的椭圆最短路径算法 |
| |
| 引用本文： | 王世明,邢建平,张玉婷,柏宝华.典型城市路网中的椭圆最短路径算法[J].系统工程理论与实践,2011,31(6):1158-1164. |
| |
| 作者姓名： | 王世明 邢建平 张玉婷 柏宝华 |
| |
| 作者单位： | 1. 山东大学 信息科学与工程学院, 济南 250100;2. 山东省导航通信协同系统工程技术研究中心, 济南 265200 |
| |
| 基金项目： | 国家自然科学基金，教育部新世纪优秀人才支持计划，山东省自然科学基金 |
| |
| 摘 要： | 提出了一种高效可靠的限制搜索区域的最优路径算法．该算法是基于典型城市路网的共同特征, 而不是某个特定城市的统计信息提出的, 它可以应用在不同的城市路网中．针对从源站点到目的站点不同的欧式距离, 算法分别在两类不同大小的椭圆内搜索最短路径．理论计算和实验结果都表明, 当源站点和目的站点相距较远时, 与椭圆限制搜索区域算法相比, 该算法可以降低33%-47%的时间复杂度, 而不会影响查询结果的准确性．
|
| 关 键 词： | 迪杰斯特拉算法 欧式距离 最短路径 限制搜索区域 典型城市路网 |
| 收稿时间： | 2010-5-20 |
Ellipse-based shortest path algorithm for typical urban road networks |
| |
| WANG Shi-ming,XING Jian-ping,ZHANG Yu-ting,BAI Bao-hua.Ellipse-based shortest path algorithm for typical urban road networks[J].Systems Engineering —Theory & Practice,2011,31(6):1158-1164. |
| |
| Authors: | WANG Shi-ming XING Jian-ping ZHANG Yu-ting BAI Bao-hua |
| |
| Institution: | 1. School of Information Science and Engineering, Shandong University, Jinan 250100, China;2. Navigation Communication Co-system Engineering Technology Research Center of Shandong Province, Jinan 265200, China |
| |
| Abstract: | An efficient and reliable optimal path algorithm within restricted searching area is proposed in this paper.Based on the common characteristics of typical urban road networks rather than the statistical information of a certain special city it can be used in different urban road networks.This algorithm searches for the shortest path in two kinds of different size ellipses for different Euclidean distances between the source station and the destination station.Compared to the ellipse restricted searching are... |
| |
| Keywords: | Dijkstra algorithm Euclidean distance shortest path restricted searching area typical urban road networks |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
