最短路算法专业译文 下载本文

专业译文

最短路的算法:以实际道路网络作为评估

班级:2010122 姓名:张菲菲 学号:20102322 文章摘自:F. BENJAMIN ZHAN, CHARLES E. NOON.Department of Geography and Planning, Management Science Program, The University of Tennessee, Knoxville, Tennessee 37996

摘要:寻找最短路径网络的经典问题多年来一直是大家的研究目标。这些研究成果已经导致了一些不同的算法和大量的实证研究结果与性能。但是,之前的研究并没有在选择计算实际网络道路的最短路径问题方面提供一个明确的方向。大多数最短路径算法的计算测试是基于没有实际网络道路特征的随机生成的网络。在本文中,我们提供了一个利用各种各样现实道路网络的最短路径算法的客观评价。在评估的基础上,一套为计算实际道路网络而推荐的最短路径算法是正确的。这种评价应该是对研究人员和从业人员在运筹学,管理科学,交通运输,地理信息系统方面特别有用。

关键词:实际网络道路;随机生成的网络;Bellman–Ford算法;Dijkstra算法

1.介绍

最短路径的计算在很多网络和交通运输分析中都是一个重要的任务。在发展上面,计算测试和最短路径算法的有效实现一直在相关科学方面保持着重要的研究课题,比如运筹学,管理科学,地理,交通运输和计算机科学。(参见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)。

在面对解决最短路问题的任务中,选择正确的算法是必须要决定的。根据不同的应用,算法的运行时间在决策过程总将是一个重要的决定。尽管一些计算评估已经在文献中被报道(例如,Hung和Divoky,1988; Gallo和Pallottino,1988; Cherkassky等等,1993),在实际道路网络中,哪一个算法或哪一套算法运行的更快,一直都没有一个明确的答复,这是从业者所面临的网络问题中最常见的。本文的主要目的是确定哪种算法在实际道路网络中运行速度最快。第二个目标是更好的了解在输入数据时算法性能的灵敏度。

过去的计算评估主要是基于随机生成的网络。随机网络生成的方法有很大的

1

差别。由此产生的随机网络范围从均匀分布的电弧长度的完整网络到高度结构化的网格网络。与实际道路网络相比,随机网络往往由不同连接程度的弧表示节点的比例。本文所研究的真实网络的弧形节点比例,范围从2.66到3.28。在文献报道中,弧形节点比例高达10,这跟很多随机生成的网络描述中是不同的。另一方面,随机网络不同于实际网络,随机网络实际上是源于随机网络的弧长通常是随机抽取的一个独立的方式。这可能会导致网络违规行为,其中,“远远”分开的两个相邻的节点中的一个可能是“关闭”的。这样的违规行为可以强烈支持某些类型的算法和大幅放缓其他类型。随机网络的发电机在文献中有一个特征,就是,我们认为导致实际与随机网络有着显著差异的即他们为建立连接或在均匀的网络方式中产生的弧长申请一个过程。实际的网络拓扑结构往往包含被高子网郊区包围的密集的城市网络区域,然后进一步包围农村道路结构。随机网络产生的某些方法可以复制一个特定区域,例如在市区电网的发电机,但是在实际网络中包含一个混合不同类型的道路网络的拓扑结构,是几乎不可能模拟的。

我们已经利用实际网络测试了以15个为一组的最短路径的算法。用于测试的网络包括来自美国中西部和东南部的10个州的道路网络,以及横跨美国大陆的美国国家高速公路规划网(nhpn)。我们研究的算法的相对排序跟过去的研究有所不同,像Gallo和Pallottino(1988)和Cherkassky等人(1993)。对于不同学科的研究人员和从业者来说这个结论是有用的,如运筹学,管理学,交通运输,地理信息系统,它们在某些应用程序中都依赖最短路径的计算。我们的研究主要集中在各种算法的相对速度。程序的运行和存储要求的问题是很重要的,然而,经过严格测试的公共域代码的可用性,使得从业人员更容易的为自己获取和实现这样一个代码。本文中的计算结果是为了计算最短路径而使用公共领域的C源代码集,这是由Cherkassky等人(1993)经过轻微修改后提出的。它们的实现被证明在计算时间上是快速的,在存储要求上是有效的。

本文的其余部分安排如下:第一部分提供了一些以前的学习背景也总结了在我们学习中的一些算法测试。第二部分是了解计算研究的一些细节。第三部分,文中得出了一套关于算法选择的建议。

2.背景

文献中报道的一个最近由Cherkassky发起的有关最短路径算法的学习是最综合的也是最新的。Cherkassky最近报道了一个有17种最短路径算法的评价。在他们的实验中,Cherkassky试验了这17种有不同特征的随机生成的网络的算法。从他们的研究中得到了一个重要的现象,就是没有一个单一的算法能一直超越其他各种类型的模拟网络。在他们的结论,他们认为,用Dijkstra算法实现了双桶结构(dikbd)是计算网络与非负弧长最好的算法,而Goldberg–Radzik算法在远程更新拓扑排序上(gor1)是一个很好的选择。

2

我们将用一个类似于Cherkassky算法的测试环境作为我们研究的出发点。我们的评价不同于他们的评价,因为我们使用实际的道路网络,而不是随机产生的网络。这17种算法在Cherkassky等人的评价中,只有15种是在我们的研究中的。因为我们不考虑无环网络,所以Cherkassky等人测试所专用无环网络的算法被排除在我们的研究中。同时,经过一些初步的测试后,我们发现,利用堆栈标记节点来处理程序执行的方法比其他的算法更慢,因此,它是不被认可的。

在继续测试之前,让我们正式介绍一些符号并定义最短路径问题。网络是一个图G?(N,A)由一组节点的索引N, n?N和一个生成的有向弧A ,m?A组成。每个弧表示为节点的有序对的形式,从节点i到j节点,记为(i,j)。每个弧(i,j)都有一个相关的数值dij,表示距离或成本通过电弧发生。在本文中,我们假设一对节点i和j是由两个不同的有向弧代表之间的双向传送(i,j)和(j,i)。给定一个有向网络G?(N,A)与已知的弧长dij,每个弧(i,j)?A,最短路径问题是要找到最短的距离(最低成本)从一个源节点到所有其他节点的节点集。

3

表1十五种算法研究综述

缩写 算法的实现描述

Bellman–Ford算法

BF 基本实现 BFP 起源检查

Dijkstra算法

DIKQ 单纯的实现

DIKB DIKBM DIKBA DIKF DIKH DIKR 增量图 PAPE TWO-Q 阈值算法 THRESH 拓扑排序 GOR GOR1

基本实现 超额的实现 近似的实现 斐波那契堆 K-array的堆 r-heap

Levit实现

基本实现 随着距离的更新

复杂度 O(nm) O(nm) O(n) O(m + nC) O(m + n(C/

2参考文献

Bellman (1958)

Dijkstra (1959)

Fredman and Tarjan (1987) Corman et al. (1990) Ahuja et al. (1990)

Pape (1974)

Pallottino (1984)

Glover et al. (1984, 1985)

Goldberg and Radzik (1993)

? + ?))

O(mb + n(? + C/ ?))

O(m + n log(n)) O(m log(n)) O(m + n log(C))

O(n2)

2nO(m)

n O(nm) O(nm) O(nm)

*n表示网络节点的数目;m表示网络弧的数目;C表示网络中的最大弧长;?和?输入参数

这些一对多的最短路径可以表示为一个指向外面树扎根的源节点S。这个有向树被称为最短路径树。

所有的算法,我们的研究都是基于标记的方法,但根据不同的选择标记节点的扫描,和用于管理标记的节点集的数据结构规则。读者可参阅Gallo 和 Pallottino (1988) , Ahuja,Magnanti 和 Orlin (1993)对这些问题进行更全面的讨论。在我们的研究中,对具体算法的评估总结在表1。该算法及其实现的细节可以在Cherkassky等人的发现中(1993)或在表1列出的参考文献中查看。该算法分为以下五类:1)Bellman–Ford 算法,2)Dijkstra算法, 3)增量图,4)阈值,5)拓扑排序。我们将Dijkstra的实现进一步分类,无论是单纯的,桶结构,或堆结构。应当指出的是,测试算法在最坏情况下的计算复杂性为多项式(多项式的m和n),伪多项式(N,M,C多项式),和指数(本文算法)。

Dijkstra算法的节点选择规则是不同于其他算法。这个规则保证了最短路径

4