最短路算法专业译文.doc

《最短路算法专业译文.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、专业译文最短路的算法：以实际道路网络作为评估班级：2010122姓名：张菲菲学号：20102322文章摘自：F.BENJAMINZHAN,CHARLESE.NOON.DepartmentofGeographyandPlanning,ManagementScienceProgram,TheUniversityofTennessee,Knoxville,Tennessee37996摘要：寻找嚴短路径网络的经典问题多年来一右•是大家的研究目标。这些研究成果已经导致了一些不同的算法和大量的实证研究结果与性能。但是，Z前的研究并没有在选择计算实际网络道路的最短路径问题方面提供一

2、个明确的方向。大多数最短路径算法的计算测试是基于没有实际网络道路特征的随机生成的网络。在木文屮，我们提供了一个利用各种齐样现实道路网络的最短路径算法的客观评价。在评估的基础上，一套为计算实际道路网络而推荐的最短路径算法是正确的。这种评价应该是对研究人员和从业人员在运筹学，管理科学，交通运输，地理信息系统方面特别有用。关键词：实际网络道路；随机生成的网络；Bellman-Ford算法；Dijkstra算法1.介绍最短路径的计算在很多网络和交通运输分析屮都是一个重要的任务c在发展上而，计算测试和最短路径算法的有效实现i直在相关科学方面保持着重耍的研究课题，比如运筹学，管理

3、科学，地理，交通运输和计算机科学。（参见Dijkstra算法，1959；表盘等,1979；Glover-Klingman算法和Philips,1985；Ahuja,1990；Goldberg和Radzik,1993）。这些研究成果已经衍牛出许多最短路径的算法，此外,对于算法的计算性能也有大量的实证研究。（参见比如，Glover-Klingman算法等，1985；Gallo和Pallottino,1988；Mondou,Crainic,Nguyen,1991；Cherkassky,Goldberg,Radzik,1993）□在面对解决最短路问题的任务屮，选择正确的算法是

4、必须要决定的。根据不同的应用，算法的运行吋间在决策过程总将是一个重要的决定。尽管一些计算评估已经在文献中被报道（例如,Hung和Divoky,1988;Gallo和PallottinoJ988;Cherkassky等等，1993）,在实际道路网络屮，哪一个算法或哪一套算法运行的更快，一直都没有一个明确的答复，这是从业者所而临的网络问题屮最常见的。本文的主要H的是确定哪种算法在实际道路网络屮运行速度最快。第二个H标是更好的了解在输入数据吋算法性能的灵每攵度。过去的计算评估主要是基于随机牛成的网络。随机网络牛成的方法有很人的差别c由此产牛的随机网络范围从均匀分布的电弧长度

5、的完整网络到高度结构化的网格网络。与实际道路网络相比，随机网络往往由不同连接程度的弧表示节点的比例。本文所研究的真实网络的弧形节点比例，范围从2.66到3.28o在文献报道屮，弧形节点比例高达10,这跟很多随机牛成的网络描述屮是不同的。另一•方面，随机网络不同于实际网络，随机网络实际上是源于随机网络的弧长通常是随机抽取的一个独立的方式。这可能会导致网络违规行为，其屮，“远远”分开的两个相邻的节点屮的一个可能是“关闭”的。这样的违规行为可以强烈支持某些类型的算法和夬幅放缓其他类型。随机网络的发电机在文献小有一•个特征,就是,我们认为导致实际与随机网络有着显著差异的即他们

6、为建立连接或在均匀的网络方式屮产牛的弧长中请一个过程。实际的网络拓扑结构往往包含被高子网郊区包围的密集的城市网络区域，然后进一步包围农村道路结构。随机网络产牛的某些方法可以复制一个特定区域，例如在市区电网的发电机，但是在实际网络屮色含一个混合不同类型的道路网络的拓扑结构，是几乎不可能模拟的。我们己经利用实际网络测试了以15个为一组的最短路径的算法。用于测试的网络包括来美国屮西部和东南部的10个州的道路网络，以及横跨美国大陆的美国国家高速公路规划网(nhpn)o我们研究的算法的相对排序跟过去的研究有所不同,像Gallo和Pallottino(1988)和Cherkass

7、ky等人(1993)。对于不同学科的研究人员和从业者來说这个结论是有用的，如运筹学，管理学，交通运输，地理信息系统，它们在某些应用程序屮都依赖最短路径的计算。我们的研究主要集屮在各种算法的相对速度。程序的运行和存储要求的问题是很重要的，然而，经过严格测试的公共域代码的可用性，使得从业人员更容易的为口己获取和实现这样一个代码。本文屮的计算结果是为了计算最短路径而使用公共领域的C源代码集，这是由Cherkassky等人(1993)经过轻微修改后提岀的。它们的实现被证明在计算吋间上是快速的，在存储要求上是有效的。本文的其余部分安排如下：第一部分提供了-•些