并行最优路径算法及K优路径算法研究
文献类型：学位论文
| 作者 | 陈虎 |
| 学位类别 | 博士 |
| 答辩日期 | 2008-06-05 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 并行算法 最优路径 K优路径 网络划分 |
| 其他题名 | Research on the Shortest Path and K Shortest Path Parallel Algorithms |
| 中文摘要 | 最优路径问题是计算机科学、运筹学、工程设计等领域很多问题的基础。它的应用包括网络路由、电路设计、交通运输、机器人运动规划、事务调度中关键路径的计算以及VLSI设计等。同时，它也为很多最优化问题提供了解决框架，如背包问题、分子生物学中的序列比对、内接多边形的构造和长度受限的霍夫曼编码等都可以转化成最优路径问题进行求解。 求解网络中最优路径的方法可以分为两大类。一种是标号设定算法（label setting ,LS）,另一种是标号改变算法（label correcting ,LC）。由于网络路径算法的应用越来越强调动态性和及时性，使得高效求解最优路径问题变得越来越重要。在这里，我们利用一种高效的网络划分方法，实现了基于网络划分的LS/LC并行算法。实验结果表明，基于这种网络划分的并行算法对于求解最优路径有很好的加速比和扩展比。 在许多更加复杂的应用中，不仅要求计算出最优路径，而且要求给出前K优路径。K优路径是长期研究的泛化最优路径问题，即不但要求得到最优路径，还要得到次短、再次短等路径。 节点s到节点t的K优路径问题可以分为两大类：一类是求解K优非简单路径，即得到的路径可以包含环路；另一类是求解K优简单路径，即路径是简单通路，不包含环路。经过大量学者的研究，求解K优非简单路径相对容易。Fox 于1975年提出了复杂度为O(m+nlogn) 的求解K优非简单路径的算法，最近， Eppstein于1998年给出了一种优化的求解K优非简单路径的算法，时间复杂度达到了O(m+nlogn+k) ，基本上达到了理论下限。 在2000年对E 的算法进行并行化，时间复杂度为 。求解K优简单路径已被证明是更为具有挑战性，这个问题最先由Hofman和Pavley 在1957年进行开始研究，但几乎所有试图解决该问题的算法时间复杂度都达到指数时间。众所周知，Yen提出了一结果比较好的算法，利用现代的数据结构达到O(kn(n+nlogn)) 时间复杂度。John Hershberger于2007年给出了一个新的求K优路径的算法，该算法基于有效率的替代路径算法,相对于以前的替代路径算法，其加速比可达到O(n) 。在本文中，我们基于John Hershberger给出的K优路径算法，尝试给出其并行的方法，并在SMP的高性能计算机上进行了测试。 关键词 并行算法、最优路径、K优路径、网络划分 |
| 英文摘要 | Shortest paths are fundamental in many areas of computer science, including operations research, and engineering. The applications of shortest path computations are too numerous to cite in detail. Their applications include network and electrical routing, robot motion planning, highway and power line engineering, resource scheduling and VLSI design, etc. In addition, shortest path provide a unifying framework for many optimization problems. Many optimization problems solved by dynamic programming or more complicated matrix searching techniques, such as the knapsack problem, sequence alignment in molecular biology, construction of optimal inscribed polygons, and length-limited Huffman coding can be expressed as shortest path problems. The methods of finding the shortest path can be classified into two categories: one is label setting (LS), the other is label correcting (LC). With the intensive demands on the dynamicity and real time in solving the shortest path problem, how to improve the efficiency of the algorithm becomes more and more important. In this paper, we implement the parallel LC and LS algorithm based on an efficient graph partitioning method. The experimental result reveals that our algorithms are scalable. Most complex applications of the shortest path problem not only require the shortest path, but also the first K shortest paths. The k shortest paths problem is a natural and long-studied generalization of the shortest path problem in which not one, but several paths in non-decreasing order of length are sought. Finding the k shortest paths between two terminals s and t can also be classified into two categories: K short paths (not required to be simple) and K short simple paths. The K shortest path problem in which paths are not required to be simple turns out to be significantly easier. An O(m+knlogn)-time algorithm for this problem has been known since 1975[Fox 1975]. A recent improvement by Eppstein essentially achieves the optimal time of O(m+nlogn+k).The problem of determining the K shortest simple paths has proved to be more challenging. The problem was originally examined by Hofman and Pavley in 1957. But nearly all attempts to solve the problem led to exponential-time algorithms. The best result known to-date is an algorithm by Yen, which can be implemented using modern data structures to run in O(kn(n+nlogn)) worst-case time. John Hershberger proposed a new algorithm to find the K shortest simple paths in a directed graph in 2007. Their algorithm is based on the efficient replacement paths algorithm of Hershberger and Suri 2001), which gives O(n) speedup over the naïve algorithm for replacement paths. We implement a parallel algorithm [John Hershberger] base on SMP computer system. Keywords Parallel Algorithm、Shortest Path Finding、K shortest path、Network Partitioning |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 63 |
| 源URL | [http://124.16.136.157/handle/311060/5914]  |
| 专题 | 软件研究所_并行计算实验室 _学位论文 |
| 推荐引用方式 GB/T 7714 | 陈虎. 并行最优路径算法及K优路径算法研究[D]. 软件研究所. 中国科学院软件研究所. 2008. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。