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

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

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

专业译文

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

班级:2009121班 姓名:xx远 学号:20092426 文章摘自:F.BENJAMIN ZHAN,CHARLES E.NOON. Title[J]. Transportation Science 0041-1655 /98/ 3201-0065:

摘要:通过网络找到两结点间最短路径的经典问题,一直以来都是很多人的研究目的。这些努力的研究导致了许多算法和大量针对算法性能的实证结果出现。不过不足的是,之前的研究并没能提供一个明确的标准去选择一个面临实际道路网络时计算最短路径的算法。大部分的计算测试一直都是依靠最短路径算法随机生成的网络,可能会没有真实道路网络的一些特点。在本文中,对十五种最短路径算法根据其使用真实道路特点提供一个客观评价。基于此评价,选择出计算真实道路网络时选择的最短路径算法。这种评价标准应该对研究人员和在运筹学,管理科学,交通和地理信息系统的从业人员有特别作用。

关键字:评价;最短路径算法;真实道路网络;道路数据集

在许多网络和运输分析中,最短路径的计算是一项重要任务。开发、测试和高效实现计算最短路径算法在相关的学科一直是重要的研究主题,这些学科包括诸如运筹学、管理科学、地理、交通和计算机科学等(如1959年迪杰斯特拉;1979年戴尔等人;1985年的格洛弗、klingman和菲利浦等人;1990年的胡佳;1993年戈德堡等人出版的文献中指出)。这些研究成果产生了许多算法和大量针对算法性能的实证结果(参见1985年格洛弗等;1988年加洛等,1991年mondou等;1993年切尔卡斯基等人出版的文献)。

当面对计算最短路径的任务时,人们必须决定去选择哪些算法。根据应用程序的特点,算法的运行状况将成为决策过程中一个重要的考虑因素。虽然有很多的文献出提出了大量的计算评价方法(如1988年的hung和divoky;1988年的加洛和pallottino;1993年的切尔卡斯基等出版的文献),但都没能给出明确的答案:某个或某组算法在真实道路网络中是运行效果最快,或是网络从业者所会面临到的最常见的类型。本文的主要目的是识别在真实道路网络下运行最快的算法,其次目的是更好地理解算法性能上输入数据的敏感性。

过去的计算评价主要是基于随机生成的网络。而生成随机网络的方法差别很大。生成的随机网络的范围从完整的网络到均匀分布的弧长、高度的结果性网格网络。相比于真实道路网络,随机网络往往有不同关于程度的连通性,正如所指出的弧形节点比率。本文所研究的真实网络的弧形节点的比例为2.66至3.28不等,这不同于许多文献中弧形节点比例为10的随机生成网络(如1988年的加洛和pallottino出版的文献)。另一方面,随机网络不同于真实网络也源于以下事实:

第1页

你可能喜欢

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

热门文档

相关文档

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