| 交通信息网格中的最短出行路径并行算法 |
| |
| 引用本文： | 章昭辉,闫春钢,丁志军,蒋昌俊.交通信息网格中的最短出行路径并行算法[J].同济大学学报(自然科学版),2006,34(12):1606-1611. |
| |
| 作者姓名： | 章昭辉 闫春钢 丁志军 蒋昌俊 |
| |
| 作者单位： | 1. 同济大学,计算机科学与技术系,上海,200092;安徽师范大学,计算机科学与技术系,安徽,芜湖,241000
2. 同济大学,计算机科学与技术系,上海,200092 |
| |
| 基金项目： | 国家重点基础研究发展计划(973计划);上海市科技攻关项目 |
| |
| 摘 要： | 根据城市路网的特点，提出了一种新的路网图的分割方法；在此基础上，提出两种网格最短路径并行算法GPSPA1和GPSPA2．这两种算法克服了传统并行标签算法只适合在共享内存的并行机器上使用的缺点，适合网格环境下使用．实验结果表明：分割器不能完全分割源点和目标点时，GPsPA2比GPSPA1效率高；完全分割时，两种并行算法的加速比大约都是3．GPSPA2应用于交通信息服务网格系统2．0版中．
|
| 关 键 词： | 交通信息网格 最短路径 并行算法 |
| 文章编号： | 0253-374X（2006）12-1606-06 |
| 收稿时间： | 05 9 2005 12:00AM |
| 修稿时间： | 2005-05-09 |
A Parallel Algorithm of the Shortest Travel Path in Traffic Information Grid |
| |
| ZHANG Zhaohui,YAN Chungang,DING Zhijun,JIANG Changjun.A Parallel Algorithm of the Shortest Travel Path in Traffic Information Grid[J].Journal of Tongji University(Natural Science),2006,34(12):1606-1611. |
| |
| Authors: | ZHANG Zhaohui YAN Chungang DING Zhijun JIANG Changjun |
| |
| Abstract: | Two parallel algorithms of the shortest travel path, GPSPA1 and GPSPA2 are presented on the basis of a new partition method of road nets. The disadvantages of traditional parallel label algorithms are overcome and heterogeneous duster can be fit in. The experimental results show that the speedup ratios of the two algorithms are about 3 when a cutter can partition the O-D completely, and that GPSPA2 is better than GPSPA1 in other cases. GPSPA2 is applied in the version 2.0 of TIG. |
| |
| Keywords: | traffic information grid shortest travel path parallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
