搜索
《Gallo&Pallottino_ShortestpathAlgorithms》读书笔记114122班丁舒娜201210043712014/10/10《Gallo&Pallottino_ShortestpathAlgorithms》读书笔记——114122班丁舒娜最短路径问题是从一个计算角度考虑算法，这篇文章介绍了8种算法来解决最短路和有向图，并且连同广泛的实验设计来的结果在不同的拓扑结构图来比较它们之间的相关表现。这篇文章的集中点：算法在不同的数据结构的实现情况。一些算法已经给出了，其中包含了足够的详细信息以允许以任何编程语言几乎直接执行。此外，实验中用到的所有算法在磁盘中都有包含。在本文中，我们处理从计算的角度来解决最短路径问题。如众所周知的那样，这个问题是在现实生活中是大型网络的模型的基本组成成分。这就解释了为什么，虽然问题本身是相当简单和广泛的研究，但新的贡献不断出现在科学文献中。有关这一主题的延伸调查中，我们指的是Gallo和Pallottino，在一个统一的框架把最短路径的方法列举出来。里面所有的算法示由一个单一的标准程序，它们用于实现组候选节点的特定的数据结构为主要区别来推导。从所有被提出的算法中，我们选择了8算法来解决最短路径图的问题。在本次评选中，我们遵循三个主要标准：历史的重要性，实际计算相关性和实施的简易性。因此，我们省略了若干重要的算法，是因为他们的兴趣是理论多于实际，或是因为它们的使用意味着相当复杂的实现，诸如一些在Denardo提出的算法与福克斯。这篇文章的重点是在算法中使用不同的数据结构的实现。虽然提供了Fortran代码，算法的“''PidginPascal”描述包含足够的细节，以便在任何其他语言中能够直接执行。事实上，在促算法的Fortran源码和帕斯卡描述之间存在着一对一的对应关系。这些算法的结果和具体过程也在这篇文章中给出了，在该实验中使用的图形发生器的源代码包含在磁盘中。虽然本文的目的是提供解决最短路径问题经过测试的和有效的算法，有些注意力也已预留给所有对问题。一种有效的算法针对此问题进行了说明，在这样一种方式，它的实现可以容易地获得利用的最短路径树算法在磁盘上的子程序。下面简介一下这8种算法：1、L-queue算法;(L-队列)在最短路径的实施时，队列是最优先的选择。我们叫这样的算法为L-队列算法。它代表了一种有效的实现一个众所周知的最短路径的方法。具体算法为：由于每个节点不能在队列中插入多于n次，L形队列的时间复杂度为O(nm)。算法的空间要求是4N+2M：N+2M为输入数据，N在该队列中，2N是数组P和D。2、L-deque算法;（L-双队列）一个双向队列采用的是著名的德Esopo-佩普算法。插入规则为:第一次一个节点是被插入到Q，它被添加到Q的尾部，这对应于一个广度优先搜索策略时，以后，在相同的节点，Q从被除去后，再次成为候补。它被添加至Q'在头部：从现在的节点上的深度优先搜索策略的基础上进行处理。使用这种较为特殊的政策的理由是，每一次的标签du被更新（减少），除了第一次，这是值得尝试减少标签u在当前树以及接班人的：这是深度优先的目标搜索阶段。具体的算法：该算法的时间复杂度为：O(n*2n)，空间复杂度为：4n+2m。3、L-2queue算法：L-2队列是当Q是由一个装置来实施所得到的算法排队和插入策略类似于在L-双端队列中所使用的。L型双端队列和L2队列之间的主要区别是在最坏情况下的计算复杂度。该算法的时间复杂度：，由于L-2队列（至少在我们的实验）一直被证明是几乎一样好左旋双端队列无不良行为在病理情况下的风险，它可以推荐给风险厌恶的用户。空间复杂度为：4n+2m。4、L-threshold算法：（L-阈值）后面L型双端队列和L2队列的有趣的想法是节点的集合的划分成两个子集和该节点根据不同的加工它们属于两个子集。分区是动态更新在每次迭代。该算法L-从提出的阈值算法得出通过格洛弗得出的。该组候选节点Q被划分成两个子集Q'和Q“，其中Q'是队列和Q”是一个链表。需要注意的是，虽然在L型双端队列而在二级队列Q'和Q“被实现为一个单独的列表两部分，在这里Q'和Q“是两个不同的链接的列表。算法时间复杂度为：；空间复杂度为：5n+2m5、S-Dijkstra算法：S-Dijkstra算法代表了最简单的实现Dijkstra的本意。具体算法为：时间复杂度为：空间复杂度为：4n+2m6、S-ord算法：该算法的S-ORD利用的有序双向链表。为了提高它的效率，进行前处理阶段，其中向前分进行排序从大到小依次为弧长。在这样做时，我们得到以下优点：为了展示在弧的结束节点上执行的操作秦，必须从尾部扫描一次到头部;这些事实可以被利用来“跳过”名单时无趣的部分在程序被被执行。时间复杂度为：空间复杂度为：5n+2m。7、S-Dial算法：该算法的S-Dial利用缓冲池来实施Q,不失一般性，我们可以考虑弧长（非负）的整数。算法的时间复杂度为：空间复杂度为：5n+2m+lmax。8、S-heap算法：在S-heap中，优先级队列是手段实施了偏序集二元堆。时间复杂度为：空间复杂度为：5n+2m。本文在介绍这8中算法的时候，首先介绍了基本的基础知识，在讲8种算法前：1、先分章节介绍了定义和符号的问题，给出了本篇论文中的一些常用的符号定义和一些关于最短路径的定义，对算法的格式和例子的演示做出了声明；2、介绍了一个最标准的最短路径算法，其中详细的把该算法涉及到的关键步骤都用图十分明白易懂的表示了出来，并且十分详细的解释了该算法原理，运行的程序表示法等；3、挑选的条件：说明了对于一些问题怎样来选择适合的、高效的算法，一些注意事项和挑选的法则；4、基础知识关于数据结构的队列：因为在前4种算法中，主要用到了队列，于是在解释算法之前，文章充分的先介绍了链表、双向链表、多链表等概念，先在进入算法的深入学习前，重温巩固基础知识点；5、列表搜索算法：这一部分的内容才详细的介绍了关于前四中算法的具体实施，并对4种算法做出了相互比较，和相互推出；6、优先队列的实施：这是在介绍后4种算法之前的基础知识储备，详细的解释了无序链表、有序链表、栈、二进制堆的概念、并分别用图示清楚的解释了各个数据结构的具体存取原理和方法；7、最短优先算法：这一部分详细解释了后四种算法，同时也是一种区分，将前四种算法与后四种算法做了大概的区别，之后又相互之间的推导引入和相互之间的区分，有些算法还具体讲了优缺点等，8、针对所有的求解最短路径的问题做出了概述性的的解释，并将大致的解决方法详细列出，十分的全面；9、数字实验：对于8种算法，分别带入具体的事例，用了完全图、随机图、k阶连接图、网格图等试验、并将得出的结果图做出了展示，从时间复杂度和空间复杂度等方面进行了相互比较；10、最后将本篇论文所用到的参考文献做出了记录；11、我觉得是做的最好的一点：将这8种算法的具体代码都一一列出来了，十分具体，很实用，在算法具体的位置还做出了注释。个人心得：其实，所有本篇的算法我都没怎么读的太懂，英文果然是很不好理解，但是我还是坚持在谷歌翻译的帮助下，把这篇文章读完了，算法的部分都是差不多能看懂，自己想的话应该是不会想出来，用的话可能也存在不少问题吧。对于最短路径问题，之前学习数据结构的时候也有学习，但也并没有很好的实施，在具体的程序中用到，这次，看了全英文的论文很有感触吧，在学习一样新的算法之前一定要把用到的基础知识再重新学习一遍，起码脑袋里要有这个概念，知道它具体是怎么用的，我之前看很多书吧，虽然有些知识在之前学过，可是自己不及时的复习，也还是会不会，这样一些不会的东西就日积月累的变成永远都不会的东西了。对以后的学习也是一项帮助吧。再说这8个算法，感觉都很简单简短的代码和西乡，可是有些还真的是很难理解，我也是一直在一遍翻译一边看，虽然老师之前说在百度上找一篇差不多的看看再写读书报告，可这次百度上真的是没有啊，很干枯但是读完，总觉得又是遇到了一种新的学习方法，新的世界吧，希望在以后的编程中可以用到。