文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 最短路径算法,基于真实道路网络下评价
侵权投诉

最短路径算法,基于真实道路网络下评价

毕业译文,其英语文献,请于百度搜索“Shortest path algorithms An evaluation using real road networks (1998)”

随机网络中弧的长度通常是使用一个独立的方式随机抽取。这就会导致随机网络出现一些违规行为:一个节点可能会出现对一对相邻的节点出现距离一个“接近”,但距离另一个“远离”的情况。这样的违规行为会导致强烈偏向于某些类型的算法或其他运行稍慢的算法。根据随机网络发生器适用于均匀方式跨网络建立或弧长生成过程的这个特点,就导致在真实网络与随机网络中出现显著差异。真实的网络拓扑结构往往含有密集的城市网络所包围的高度子网络的郊区,然后在包围农村公路结构的领域。而随机网络生成的某些方法可能会复制一个特定的区域,例如,出现网格网络的市中心,但真正的市中心是包含一个混合模式的不同类型的道路网络拓扑,基本上都无法模拟。

我们已经测试了一套15使用真实道路网络最短路径算法。用于测试的网络,来自于包括美国中西部和东南部十个州,以及美国国家公路规划网络(NHPN)。最后研究得到的算法相对排名也与过去的研究出现不同结果,如1988年的加洛和pallottino,1993年的切尔卡斯基等出版文献。研究人员和在不同的学科,如运筹学,管理科学,运输,地理信息系统等的从业人员,依靠在某些应用程序中的最短路径计算的结果应该是有用的。我们的研究着重于各种算法的相对速度。实施和存储要求的问题是重要的,但是经过严格测试的公共域代码的可用性允许从业者能够很容易地获得和实施这样的代码到自己。本文的计算结果,获得使用一套公共领域计算最短路径的C源代码。与1993年的切尔卡斯基等人的成果相比,只有轻微的修改。事实证明,这组代码的实现相对于存储的要求是相对于计算时间的快速和高效的。

1.背景

切尔斯基等人最近的一项研究表明计算相互转化后的最短路算法在这些文献中都有报道(1985年的格洛弗;1988年的加洛 和 pallottino;1991年的mondou;以及1993年的切尔卡斯基等出版文献)。1993年的切尔卡斯基等人的文献是最全面也是最新的报道。切尔斯基等人的报告评估了17种最短路径算法。在他们的实验中,切尔斯基等人检测了这17个算法在许多随机生成的网络具有不同特点。他们的研究的主要是观察,对于模拟网络是否存在一个单一的算法始终优于所有其他的算法。从中得出的结论是,建议对双重(DIKBD)与非负弧长网络,使用迪杰斯特拉算法是最好的算法,并且,Goldberg–Radzik算法对于拓扑排序(GOR1)的距离不断更新的负弧长网络是一个不错的选择。

本文将使用与切尔卡斯基等人做的实验相似的测试环境,作为研究的一个起点。但此次的评估将不同于他们的,在此使用真实的道路网络而不是随机生成的网络。在切尔卡斯基等人评价的17种算法,本文仅使用其中的15种。因为本文中不考虑切尔卡斯基等人使用到的的非循环网络、专用算法的无环网络测试,因此有两种算法被排除在研究之外。同时,在进行初步的测试后,发现一个实现使

上一页第2页

你可能喜欢

  • 英文文献翻译
  • 弗洛伊德算法
  • Floyd算法
  • Dijkstra算法
  • 消防规划
  • 应急物资调度
  • 蚁群算法

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email