Control and Cybernetics
vol. 35 (2006) No. 3
Dijkstrarsquo;s algorithm revisited: the dynamic programming connexion
by
Moshe Sniedovich
Department of Mathematics and Statistics The University of Melbourne, Australia
e-mail: m.sniedovich@ms.unimelb.edu.au
Abstract: Dijkstrarsquo;s Algorithm is one of the most popular algo- rithms in computer science. It is also popular in operations research. It is generally viewed and presented as a greedy algorithm. In this paper we attempt to change this perception by providing a dynamic programming perspective on the algorithm. In particular, we are re- minded that this famous algorithm is strongly inspired by Bellmanrsquo;s Principle of Optimality and that both conceptually and technically it constitutes a dynamic programming successive approximation pro- cedure par excellence. One of the immediate implications of this perspective is that this popular algorithm can be incorporated in the dynamic programming syllabus and in turn dynamic program- ming should be (at least) alluded to in a proper exposition/teaching of the algorithm.
Keywords: Dijkstrarsquo;s algorithm, dynamic programming, greedy algorithm, principle of optimality, successive approximation, opera- tions research, computer science.
Introduction
In 1959 a three-page long paper entitled A Note on Two Problems in Connexion with Graphs was published in the journal Numerische Mathematik. In this paper Edsger W. Dijkstra — then a twenty nine years old computer scientist
— proposed algorithms for the solution of two fundamental graph theoretic problems: the minimum weight spanning tree problem and the shortest path problem. We shall say a bit more about this paper later on in this discussion. For the time being suffice it to say that today Dijkstrarsquo;s Algorithm (DA) for the shortest path problem is one of the most celebrated algorithms in computer science (CS) and a very popular algorithm in operations research (OR).
In the literature, this algorithm is often described as a greedy algorithm. For example, the book Algorithmics (Brassard and Bratley, 1988, 87-92) discusses it in the chapter entitled Greedy Algorithms. The Encyclopedia of Operations Research and Management Science (Gass and Harris, 1996, 166-167) describes
it as a “. . . node labeling greedy algorithm . . . ” and a greedy algorithm is described as “. . . a heuristic algorithm that at every step selects the best choice available at that step without regard to future consequences . . . ” (Gass and Harris, 1996, 264). And in Cormen et al. (1990, 519) we read:
Optimal substructure of a shortest path
Shortest-path algorithms typically exploit the property that a short- est path between two vertices contains other shortest paths within it. This optimal-substructure property is a hallmark of the applica- bility of both dynamic programming (Chapter 16) and the greedy method (Chapter 17). In fact, Dijkstrarsquo;s Algorithm is a greedy algo- rithm, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices (see Chapter 26), is a dynamic program- ming algorithm.
Although the algorithm is popular in the OR/MS literature, it is generally regarded as a “computer science method”. Apparently, this is due to three factors: (a) its inventor was a computer scientist (b) its association with special data structures, and (c) there are competing OR/MS oriented algorithms for the shortest path problem. It is not surprising therefore that some well established OR/MS textbooks do not even mention this algorithm in their discussions on the shortest path problem (e.g. Daellenbach et al., 1983; Hillier and Lieberman, 1990) and those that do discuss it in that context present it in a stand-alone mode, that is, they do not relate it to standard OR/MS methods (e.g. Markland and Sweigart, 1987; Winston, 2004). For the same reason it is not surprising that the “Dijkstrarsquo;s Algorithm” entry in the Encyclopedia of Operations Research and Management Science (Gass and Harris, 1996, 166-167) does not have any reference whatsoever to DP.
The objective of this paper is to present a completely different portrayal of DA, its origin, its role in OR/MS and CS, and its relationship to other OR/MS methods and techniques. Instead of focusing on its computational complexity, data structures that it can utilize to good effect, and other implementation is- sues, we examine the fundamental principle that inspired it in the first place, its basic structure, and its relationship to the well established OR/MS methods and techniques. That is, we show that at the outset DA was inspired by Bell- manrsquo;s Principle of Optimality and that, not surprisingly, technically it should be viewed as a DP successive approximation procedure.
Needless to say, this characterization of DA is not inconsistent with other valid characterizations. In particular, there is no conflict between this char- acterization and the common “ greedy ” characterization that is so popular in computer science circles. After all, DP offers a very natural paradigm for the formulation of greedy algorithms (Bird and de Moor, 1997, and Lew, 2005).
Be it as it may, one of the immediate implications of this fact is that OR/MS lecturers can present DA as an OR/MS-oriented algorithm par excellence and relate it to the well established OR/MS methods and techniques. In particular,
they can incorporate DA in the DP syllabus, where in fact it belongs. This, we should add, is long overdue for in teaching DA it is most constructive to draw the studentsrsquo; attention to the fact that this algorithm was inspired by Bellmanrsquo;s Principle of Optimality. Furthermore, it is important to point out that it is no more, no less, than a (clever) metho
剩余内容已隐藏，支付完成后下载完整资料
控制和控制论
第35卷(2006)第3期
重新审视Dijkstra算法:
动态规划连接Moshe Sniedovich
澳大利亚墨尔本大学数学与统计学系
电子邮件:m.sniedovich@ms.unimelb.edu.au
文摘:Dijkstra算法是计算机科学中最流行的算法之一。它在运筹学中也很受欢迎。一般认为它是一种贪婪算法。在本文中，我们试图通过对算法提供一个动态规划的视角来改变这种看法。特别值得注意的是，这个著名的算法受到贝尔曼最优性原理的强烈启发，在概念上和技术上它都构成了一个动态规划逐次逼近的卓越保证。这个观点的直接含义之一是，这个流行的算法可以被纳入到动态编程教学大纲中，而动态程序应该(至少)在适当的算法讲解/教学中提到。
关键词:Dijkstra算法，动态规划，贪婪算法，最优性原理，逐次逼近，歌剧研究，计算机科学。
介绍
1959年，在《数学数字》杂志上发表了一篇三页长的论文，题目是《关于图与两个问题的说明》。在这篇论文中，Edsger W. Dijkstra——当时是一名29岁的计算机科学家
-提出了求解两个基本图论问题的算法:最小权生成树问题和最短路径问题。我们将在稍后的讨论中对这篇文章做更多的介绍。就目前而言，Dijkstra算法(DA)是计算机科学(CS)中最著名的算法之一，也是运筹学(OR)中非常流行的算法之一。
在文献中，该算法常被描述为贪婪算法。例如，在《算法》(Brassard and Bratley, 1988, 87-92)一书中，“贪婪算法”一章讨论了它。运营研究和管理科学百科全书(Gass和Harris, 1996, 166-167)描述
它是一个“hellip;hellip;节点标记贪婪算法hellip;一个贪婪算法被描述为。一种启发式算法，它在每一步都选择该步骤中可用的最佳选择，而不考虑未来的结果hellip;(Gass and Harris, 1996, 264)。在Cormen et al.(1990, 519)中我们读到:
最短路径的最优子结构
最短路径算法通常利用两个顶点之间的最短路径包含其他最短路径的特性。这种最优子结构特性是动态规划(第16章)和贪心方法(第17章)可应用性的一个标志。事实上，Dijkstra算法是一种贪婪的algo- rithm算法，而Floyd-Warshall算法是一种动态程序明算法，它可以找到所有顶点对之间的最短路径(见第26章)。
虽然该算法在OR/MS文献中很流行，但通常被认为是一种“计算机科学方法”。显然，这是由三个因素造成的:(a)它的发明者是一位计算机科学家(b)它与特殊的数据结构有关，(c)存在针对最短路径问题的竞争性或面向MS的算法。因此，一些成熟的或/MS教科书在讨论最短路径问题时甚至没有提到这种算法也就不足为奇了(如Daellenbach et al.， 1983;希利尔和利伯曼(1990)以及那些在这种背景下讨论它的人以独立的模式呈现它，也就是说，他们没有将它与标准或/MS方法联系起来(如Markland和Sweigart, 1987;温斯顿,2004)。出于同样的原因，《运筹学与管理科学百科全书》(Gass and Harris, 1996, 166-167)中的“Dijkstra算法”条目与DP没有任何关联也就不足为奇了。
本文的目的是对DA、DA的起源、DA在OR/MS和CS中的作用以及DA与其他OR/MS方法和技术的关系进行完全不同的描述。我们不关注它的计算复杂性、它可以有效利用的数据结构以及其他实现，而是研究了最初激发它的基本原理、它的基本结构以及它与已建立的OR/MS方法和技术之间的关系。也就是说，我们证明了DA从一开始就受到贝尔曼最优性原理的启发，因此，从技术上讲，DA应该被看作是一个DP逐次逼近过程。
不用说，DA的这种特性与其他有效的特性并不矛盾。特别是，这种字符化与计算机科学领域中普遍存在的“贪婪”特征之间没有冲突。毕竟，DP为贪婪算法的制定提供了一个非常自然的范例(Bird and de Moor, 1997, and Lew, 2005)。
尽管如此，这一事实的直接含义之一是OR/MS讲师可以将DA作为一个OR/MS导向的优秀算法呈现出来，并将其与成熟的OR/MS方法和技术联系起来。特别是,
他们可以将DA纳入DP教学大纲中，实际上DA属于DP教学大纲。这一点，我们应该补充，是早就应该在DA教学中提请学生注意的事实，这是最有建设性的，该算法的灵感来自Bellman的最优性原则。此外，重要的是要指出，它并不比(聪明)的方法，解决DP函数方程的最短路径问题的周期存在和弧长是非负的。
DA和DP之间的亲密关系在专业文献中有明确的暗示(如Lawler, 1976, and Denardo, 2003)，但是细节没有明确的说明，也不容易理解。本讨论的一个重要目标是澄清这些细节，使计算机科学家和操作研究人员更容易理解这些细节。
简而言之，我们的分析旨在通过关注DA与标准DP方法和技术之间的关系，为DA提供一个OR/MS视角。我们希望，这将有助于更全面地了解两者。
在下一节中，我们将描述经典最短路径问题的基本结构。然后我们描述了DA，并确定了它所要解决的一类最短路径问题。接下来是DA作为DP算法的详细描述。然后，我们简要讨论了迪杰斯特拉(1959)的著名论文和相关事项。
关于内容和表现风格:我们有意采用半正式的方法，不要求读者有明显的DP背景。讨论很容易接受不太正式的阐述和解释，以及更正式和严格的技术处理。
因为考虑的话题应该感兴趣的教师教学DP和/或DA主题专业学科和/或在更广泛的女士或/和CS主题,我们提供附录包含相关讨论“DP - DA”尤其记住这样的读者写的。
最短路径问题
DA流行的主要原因之一是，它是最重要和最有用的算法之一，可用来生成(精确的)最优解的一类大的最短路径问题。重点是最短路径问题在理论、实践和实践上都是极其重要的。
的确，可以肯定地说，最短路径问题是OR/MS、CS和人工智能(AI)等领域中最重要的一般性问题之一。其中一个原因是，本质上任何组合优化问题都可以表示为最短路径问题。因此，这类问题是非常大的，包括许多与实际(“真正的”)最短路径问题无关的实际问题。
对于我们讨论的目的，只考虑一般最短路径问题的“物理”版本就足够了。还有很多其他的。
然后考虑由n个gt; 1个城市组成的问题{1,2，hellip;， n}，矩阵D表示各城市之间的直接联系长度，因此
D(i, j)表示连接城市i和城市j的直接链路的长度，这意味着任意一对城市之间最多有一个直接链路。正式我们假设minus;infin;lt; D (i, j)le;infin;,forall;i, jisin;C: = {1,hellip;n},
D(我)=infin;,forall;我isin;c .我们D (i, j) =infin;解释为表明没有
从i市到j市的直接链接
A(j):={iisin;C: D(j, i) lt;infin;}，jisin;C (1)
B(j):={iisin;C: D(i, j) lt;infin;}，jisin;C (2)
因此，由construction A(j)表示j市和
B(j)表示j市的直接前辈的集合。
目标是找到从一个给定的城市(称为家)到另一个给定的城市(称为目的地)的最短路径。路径的长度假设等于路径上连续城市之间链接的长度之和。在不失一般性的前提下，我们假设城市1是家乡城市，城市n是目的地城市。因此，基本任务是:ftnd是城市1到城市n的最短路径。
由于技术上的原因，且不失一般性，可以方便地假设city 1没有任何直接的前身。这只是一种形式，因为如果不满足这个条件，我们可以简单地引入一个虚拟城市，并用长度为0的链接将其连接到城市1。所以我们假设
B(1) ={}，其中{}表示空集。
注意,符合上述约定,我们应该得出这样的结论:最短路径的长度从城市我j =infin;,言外之意是,没有(可行)路径从节点到节点j。还应该指出,上述约定,最短路径问题的一个实例是唯一指定的距离矩阵d。因此,这个矩阵
可以看作是一个完整的模型问题。
就最优解(路径)而言，我们必须区分三种基本情况:
- 存在最优解。
- 没有最优解，因为没有可行解。
- 由于城市1到城市n的可行路径长度从下往上是无界的，所以不存在最优解。
理想情况下，为解决最短路径问题而设计的算法应该能够处理这三种情况。
考虑到我们对DA的兴趣，我们将重点研究最短路径问题，其中可能存在循环，但城市间距离是非负的。在这种情况下，我们确信如果存在一个可行解，那么存在一个最优解，并且至少有一个最优解是一个简单的路径，即它
为非循环路径。我们的目标是构建这样一条道路。考虑到这一点，让
f (j):=城市1到城市jisin;C的最短路径长度。 (3)
然后，我们的目标是确定f (n)的值。注意，鉴于B(1) ={}，因此f(1) = 0。此外，如果从城市1到城市j没有可行路径，那么f (j) =infin;。
事实上,尽管我们的目标是找到f (n)的价值我们也有兴趣在f的值(j), jfnof;= n,反映的本质DA和DP: f (n)的值来计算我们计算f(·)值的其他城市。
迪杰斯特拉算法
从纯技术的角度来看，DA是一个迭代过程，它不断地尝试改进{F (j)}的(精确)值的初始(上)近似{F (j)}。初始近似就是F (1) = 0 F (j) =infin;对于j = 2。， n.在每次迭代中处理一个新城市:其F(·)值用于更新尚未处理的其直接继承者的F(·)值。一个记录U保存了一组尚未处理的城市，因此最初U = C ={1，hellip;n}。终止时F (n)的值等于F (n)，详情如下:
Dijkstra算法:版本1
f (n) = ?
初始化:
j = 1;F (1) = 0;F (i) =infin;，iisin;{2。n};U = C
迭代:
当(jfnof;= n和F (j) lt;infin;):更新U: U = \ {j}
更新F: F (i) =分钟{F (i), F (j) D (j, i)},我isin;(j)cap;U
更新j: j = arg min{F (i): iisin;U}
注意，如果终止是因为F (j) =infin;，那么F (n) = F (n) =infin;
不管终止时j是否等于n。
有时需要确定从城市1到其他每个城市jisin;{2,3，hellip;n}。要完成这一任务，只需按照下面的步骤对上述公式稍加修改即可。在终止(j) = F (j),forall;jisin;C。
这两个公式的算法没有解释如何优化路径
构造。它们只描述了如何更新路径的长度。的
通过记录正在处理的城市的最佳直接前身，可以很容易地将最优路径的构建纳入这些公式中。当F (j)被更新时，这个前身将被动态更新。
Dijkstra算法:版本2
f (j) = ?， jisin;C
初始化:
j = 1;F (1) = 0;F (i) =infin;，iisin;{2。n};U = C
迭代:
而(|U | gt; 1 and F (j) lt;infin;)Do: Update U: U = U \{j}
更新F: F (i) =分钟{F (i), F (j) D (j, i)},我isin;(j)cap;U
更新j: j = arg min{F (i): iisin;U}
主要结果如下:
定理3.1 Dijkstra算法(版本2)在最多n - 1次迭代之后终止。如果非负城际距离在终止(j) = F (j),forall;jisin;C。
简而言之，如果城市间的距离不是负的，这些算法就会产生预期的结果。
就计算复杂度而言，DA执行得相当好。在第m次迭代中，对于算法的Update F和Update j步骤，我们有|U |:= n - m。为了简单起见，我们假设Update j步骤中的min操作是通过成对比较天真地执行的。这意味着
在第m次迭代中，更新j步需要n - m- 1的比较。表1总结了在
更新DA的F步和j步，其中上标m为迭代
把这些值加起来除以m = 1，hellip;， n - 1表示算法在最坏情况下执行的操作总数。
表1。DA的计算复杂度
|
更新F(m) |
添加 nminus;m |
比较 nminus;m |
|
更新j(m) |
0 |
n - m - 1 |
|
(m = 1，hellip;， n - 1) |
n (nminus;1) / 2 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[442805]，资料为PDF文档或Word文档，PDF文档可免费转换为Word |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
