| 基于城市道路网的快速路径寻优算法 |
| |
| 引用本文： | 毕军,付梦印,周培德,张宇河.基于城市道路网的快速路径寻优算法[J].计算机工程,2002,28(12):36-38. |
| |
| 作者姓名： | 毕军 付梦印 周培德 张宇河 |
| |
| 作者单位： | 1. 北京理工大学自动控制系,北京,100081
2. 北京理工大学计算机科学与工程系,北京,100081 |
| |
| 摘 要： | 从城市道路网的特点出发，描述了矢量化的城市道路网的存储结构，提出一种求解城市道路网两节点间最短路径的算法，算法基于双向式搜索原理，采用投影法，角最小的方法及二叉树理论，和Dijkstra算法相比，算法大大减小搜索空间，提高搜索速度，时间复杂性不超过O（N），N为网络节点数，实现应用表明算法有很强的实用性和可靠性。
|
| 关 键 词： | 城市道路网 快速路径寻优算法 路径规划 图论 二叉树理论 |
| 文章编号： | 1000-3428(2002)12-0036-03 |
| 修稿时间： | 2001年11月19 |
A Fast Algorithm for Optimum Path Based on a City Road Net |
| |
| BI Jun,FU Mengyin,ZHOU Peide,ZHANG Yuhe.A Fast Algorithm for Optimum Path Based on a City Road Net[J].Computer Engineering,2002,28(12):36-38. |
| |
| Authors: | BI Jun FU Mengyin ZHOU Peide ZHANG Yuhe |
| |
| Affiliation: | BI Jun1,FU Mengyin1,ZHOU Peide2,ZHANG Yuhe1 |
| |
| Abstract: | According to the characteristics of a city road net, this paper discusses a kind of data structure of road net and proposes an algorithm for seeking the shortest path between two points in the road net. The algorithm takes advantage of the theories of bidirectional search, projection, minimum angle and binary tree. Compared with Dijkstra algorithm, the algorithm can reduce seeking space and can raise seeking speed greatly, and its time complexity can not exceed O(N), while N is the number of road net points. The application results show that the algorithm has good practicability and reliability. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
