fbpx
维基百科

最长路径问题

图论理论计算机科学中,最长路径问题是指在给定的图中找出长度最长的道路。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量,而有权图中路径长度是边权重之和。不同的是,与此相反的最短路径问题(不含负权环)可以在多项式时间内解决。而最长路径问题是NP困难的,这意味着除非P = NP,否则对应于任意的图,没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是,有一个线性时间的方法可以用于有向无环图,这对于发现调度问题中的关键路径有重要的作用。

NP-困难性

可以从哈密顿路径问题规约到未加权最长路径问题,这显示出后者屬於NP-困难類別:当且仅当图G的最长路径的长度是n−1时(n是圖中顶点的数量),图G有哈密顿路径。 由于哈密顿路径问题是NP完全的,此规约表明最长路径问题的决定版本也是NP完全的。在该决定问题中,输入是图G和数k;如果G中存在至少一條由k条或更多条边的路径,则输出为“是”,否则为“否”。[1]

如果可以在多项式时间内解决最长路径问题,则可以通过找到最长路径,然后将其长度与数k进行比较来将其用于解决该决定问题。因此,最长的路径问题是NP难的。问题“在给定图中是否存在具有至少k条边的简单路径”是NP完全的。[2]

在具有非负边权的加权完全图中,加权最长路径问题与旅行推销员问题相同,因为最长路径总是包括所有顶点。[3]

无环图

在加权图G中两个给定顶点st之间的最长路径,与通过将G中每个权重改变为其相反数所导出的图-G中的最短路径相同。因此,如果在-G中找到最短路径,则在G中也可以找到最长路径。[4]

对于大多数图而言,此变换并无用途,因为它在-G中产生了负环。但是如果G有向无环图(DAG),则不会有负环,并且通过对-G中的最短路径应用线性时间算法,可以在线性时间里找到G的最长路径,因-G也是有向无环图。[5]

对于给定DAG中的每个顶点v,可以通过以下步骤获得以v结尾的最长路径的长度:

  1. 找到给定DAG的拓扑排序
  2. 对于DAG的每个顶点v,在拓扑排序中,通过检查连入的邻接点,并将这一个邻接点记录的最大长度加1来计算以v结尾的最长路径的长度。如果v没有连入的邻接点,则将以v结尾的最长路径的长度设置为零。在所有情况下,记录下这个数,以便算法的后续步骤访问它。

完成此操作后,可以从记录值最大的顶点v开始,然后向后找记录值最大的连入邻接点,最后反转这条路径就是结果。这和在-G上运行最短路算法等价。

关键路径

关键路径方法是進行工程項目計劃時常用的一種估算項目所需時間的方法。使用時,需要构造有向无环图,其中顶点表示项目里程碑,边表示達到某一个里程碑之后,要通向另一个里程碑所必須的活动;通过估计完成相应活动将花费的时间,算出每条边的边权。在这样的图中,从第一个里程碑到最后一个里程碑的最长路径是关键路径,它描述了完成项目的总时间。[5]

有向无环图的最长路径也可以用于分层图绘制英语layered graph drawing:将有向无环图G的每个顶点v分到层数是以v结尾的最长路径长度的层,这种层分配使G的层数最小。[6]

图的特例

迪杰斯特拉在20世纪60年代提出了一种用于在树中找到最长路径的线性时间算法,而该算法的正式证明于2002年出版。[7]此外,最长路径可以在加权树上,块图英语Block graph上,仙人掌图英语Cactus graph上,[8]二分置换图英语Permutation graph上,[9]托勒密图英语Ptolemaic graph[10]以多项式时间计算。

对于区间图英语Interval graph,已知  时间的算法,其使用动态规划方法。[11]这种动态规划方法已被用于获得Circular-arc 图英语Circular-arc graph[12]和可比性补图(即可比性图英语Comparability graph补图,也包含置换图英语Permutation graph[13]的多项式时间算法,两者具有相同的运行时间  。后一种算法基于可比性补图的词典深度优先搜索(LDFS)顶点排序的特殊属性。[14]对于共同可比性图,还已知有较高运行时间  的另一种多项式时间算法,其基于由输入的可比性补图的补图定义的偏序关系哈斯图[15]

此外,最长路径问题可以在树宽有界或团宽有界的任何图上在多项式时间内解决,例如距离-遗传图英语Distance-hereditary graph。最后,在哈密顿路径问题是NP难的所有图上显然最长路径问题也是NP难的,例如在分割图英语Split graph圆图英语Circle graph平面图上。

参数化复杂性

当通过路径长度参数化时,最长路径问题是固定参数易处理英语Parameterized complexity的。例如,可以通过执行以下步骤的算法,以输入图大小的线性时间求解最长路径问题(但对于路径长度呈指数时间):

  1. 对图进行深度优先搜索。设 是得到的深度优先搜索树英语Trémaux tree的深度。
  2. 使用深度优先搜索树的根到叶路径的顺序,按照搜索遍历的顺序,构建图的路径分解英语Pathwidth,路径宽度为 
  3. 动态规划应用于此路径分解以找到最长的路径 ,时间是 ,其中 是图中顶点的数量。

由于输出路径的长度至少与 一样大,因此运行时间也受  的限制,其中 是最长路径的长度。[16]

参见

  • Gallai-Hasse-Roy-Vitaver定理英语Gallai–Hasse–Roy–Vitaver theorem,最长路径与图着色的对偶关系
  • 最长无交叉骑士路径英语Longest uncrossed knight's path
  • 盒中蛇英语Snake-in-the-box问题中,超立方体图英语Hypercube graph中的最长诱导路径英语Induced path

参考文献

  1. ^ Schrijver, Alexander, Combinatorial Optimization: Polyhedra and Efficiency, Volume 1, Algorithms and Combinatorics 24, Springer: 114, 2003, ISBN 9783540443896 .
  2. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction To Algorithms 2nd, MIT Press: 978, 2001, ISBN 9780262032933 .
  3. ^ Lawler, Eugene L., Combinatorial Optimization: Networks and Matroids, Courier Dover Publications: 64, 2001, ISBN 9780486414539 .
  4. ^ 王建新; 杨志彪; 陈建二. 最长路径问题研究进展. 计算机科学. 2010-03-02, 36 (12): 1-4,31 [2022-08-15]. doi:10.3969/j.issn.1002-137X.2009.12.001. 
  5. ^ 5.0 5.1 Sedgewick, Robert; Wayne, Kevin Daniel, Algorithms 4th, Addison-Wesley Professional: 661–666, 2011, ISBN 9780321573513 .
  6. ^ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G., Layered Drawings of Digraphs, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall: 265–302, 1998, ISBN 978-0-13-301615-4 .
  7. ^ Bulterman, R.W.; van der Sommen, F.W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A.J.M., On computing a longest path in a tree, Information Processing Letters, 2002, 81 (2): 93–96, doi:10.1016/S0020-0190(01)00198-3 .
  8. ^ Uehara, Ryuhei; Uno, Yushi, Efficient algorithms for the longest path problem, Isaac 2004, Lecture Notes in Computer Science, 2004, 3341: 871–883, ISBN 978-3-540-24131-7, doi:10.1007/978-3-540-30551-4_74 .
  9. ^ Uehara, Ryuhei; Valiente, Gabriel, Linear structure of bipartite permutation graphs and the longest path problem, Information Processing Letters, 2007, 103 (2): 71–77, CiteSeerX 10.1.1.101.96 , doi:10.1016/j.ipl.2007.02.010 .
  10. ^ Takahara, Yoshihiro; Teramoto, Sachio; Uehara, Ryuhei, Longest path problems on Ptolemaic graphs, IEICE Transactions, 2008, 91–D (2): 170–177, doi:10.1093/ietisy/e91-d.2.170  .
  11. ^ Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D., The longest path problem has a polynomial solution on interval graphs, Algorithmica, 2011, 61 (2): 320–341, CiteSeerX 10.1.1.224.4927 , S2CID 7577817, doi:10.1007/s00453-010-9411-3 .
  12. ^ Mertzios, George B.; Bezakova, Ivona, Computing and counting longest paths on circular-arc graphs in polynomial time, Discrete Applied Mathematics, 2014, 164 (2): 383–399, CiteSeerX 10.1.1.224.779 , doi:10.1016/j.dam.2012.08.024 .
  13. ^ Mertzios, George B.; Corneil, Derek G., A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM Journal on Discrete Mathematics, 2012, 26 (3): 940–963, S2CID 4645245, arXiv:1004.4560 , doi:10.1137/100793529 .
  14. ^ Corneil, Derek G.; Krueger, Richard, A unified view of graph searching, SIAM Journal on Discrete Mathematics, 2008, 22 (4): 1259–1276, doi:10.1137/050623498 .
  15. ^ Ioannidou, Kyriaki; Nikolopoulos, Stavros D., The longest path problem is polynomial on cocomparability graphs (PDF), Algorithmica, 2011, 65: 177–205 [2022-08-15], CiteSeerX 10.1.1.415.9996 , S2CID 7271040, doi:10.1007/s00453-011-9583-5, (原始内容 (PDF)于2022-08-15) .
  16. ^ Bodlaender, Hans L., On linear time minor tests with depth-first search, Journal of Algorithms, 1993, 14 (1): 1–23, MR 1199244, doi:10.1006/jagm.1993.1001 . For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see Monien, B., How to find long paths efficiently, Analysis and design of algorithms for combinatorial problems (Udine, 1982), North-Holland Math. Stud. 109, Amsterdam: North-Holland: 239–254, 1985, ISBN 9780444876997, MR 0808004, doi:10.1016/S0304-0208(08)73110-4 .

外部链接

  • "Find the Longest Path (页面存档备份,存于互联网档案馆)", song by Dan Barrett

最长路径问题, 在图论和理论计算机科学中, 是指在给定的图中找出长度最长的道路, 一条不具有任何重复顶点的路径被称为简单路径, 无权图中路径的长度就是边的数量, 而有权图中路径长度是边权重之和, 不同的是, 与此相反的最短路径问题, 不含负权环, 可以在多项式时间内解决, 而是np困难的, 这意味着除非p, 否则对应于任意的图, 没有办法在多项式时间内解决该问题, 更强的结果表明这个问题也難以近似地得出答案, 但是, 有一个线性时间的方法可以用于有向无环图, 这对于发现调度问题中的关键路径有重要的作用, 目录, 困. 在图论和理论计算机科学中 最长路径问题是指在给定的图中找出长度最长的道路 一条不具有任何重复顶点的路径被称为简单路径 无权图中路径的长度就是边的数量 而有权图中路径长度是边权重之和 不同的是 与此相反的最短路径问题 不含负权环 可以在多项式时间内解决 而最长路径问题是NP困难的 这意味着除非P NP 否则对应于任意的图 没有办法在多项式时间内解决该问题 更强的结果表明这个问题也難以近似地得出答案 但是 有一个线性时间的方法可以用于有向无环图 这对于发现调度问题中的关键路径有重要的作用 目录 1 NP 困难性 2 无环图 2 1 关键路径 3 图的特例 4 参数化复杂性 5 参见 6 参考文献 7 外部链接NP 困难性 编辑可以从哈密顿路径问题规约到未加权最长路径问题 这显示出后者屬於NP 困难類別 当且仅当图G的最长路径的长度是n 1时 n是圖中顶点的数量 图G有哈密顿路径 由于哈密顿路径问题是NP完全的 此规约表明最长路径问题的决定版本也是NP完全的 在该决定问题中 输入是图G和数k 如果G中存在至少一條由k条或更多条边的路径 则输出为 是 否则为 否 1 如果可以在多项式时间内解决最长路径问题 则可以通过找到最长路径 然后将其长度与数k进行比较来将其用于解决该决定问题 因此 最长的路径问题是NP难的 问题 在给定图中是否存在具有至少k条边的简单路径 是NP完全的 2 在具有非负边权的加权完全图中 加权最长路径问题与旅行推销员问题相同 因为最长路径总是包括所有顶点 3 无环图 编辑在加权图G中两个给定顶点s和t之间的最长路径 与通过将G中每个权重改变为其相反数所导出的图 G中的最短路径相同 因此 如果在 G中找到最短路径 则在G中也可以找到最长路径 4 对于大多数图而言 此变换并无用途 因为它在 G中产生了负环 但是如果G是有向无环图 DAG 则不会有负环 并且通过对 G中的最短路径应用线性时间算法 可以在线性时间里找到G的最长路径 因 G也是有向无环图 5 对于给定DAG中的每个顶点v 可以通过以下步骤获得以v结尾的最长路径的长度 找到给定DAG的拓扑排序 对于DAG的每个顶点v 在拓扑排序中 通过检查连入的邻接点 并将这一个邻接点记录的最大长度加1来计算以v结尾的最长路径的长度 如果v没有连入的邻接点 则将以v结尾的最长路径的长度设置为零 在所有情况下 记录下这个数 以便算法的后续步骤访问它 完成此操作后 可以从记录值最大的顶点v开始 然后向后找记录值最大的连入邻接点 最后反转这条路径就是结果 这和在 G上运行最短路算法等价 关键路径 编辑 关键路径方法是進行工程項目計劃時常用的一種估算項目所需時間的方法 使用時 需要构造有向无环图 其中顶点表示项目里程碑 边表示達到某一个里程碑之后 要通向另一个里程碑所必須的活动 通过估计完成相应活动将花费的时间 算出每条边的边权 在这样的图中 从第一个里程碑到最后一个里程碑的最长路径是关键路径 它描述了完成项目的总时间 5 有向无环图的最长路径也可以用于分层图绘制 英语 layered graph drawing 将有向无环图G的每个顶点v分到层数是以v结尾的最长路径长度的层 这种层分配使G的层数最小 6 图的特例 编辑迪杰斯特拉在20世纪60年代提出了一种用于在树中找到最长路径的线性时间算法 而该算法的正式证明于2002年出版 7 此外 最长路径可以在加权树上 块图 英语 Block graph 上 仙人掌图 英语 Cactus graph 上 8 二分置换图 英语 Permutation graph 上 9 和托勒密图 英语 Ptolemaic graph 上 10 以多项式时间计算 对于区间图 英语 Interval graph 已知 O n 4 displaystyle O n 4 时间的算法 其使用动态规划方法 11 这种动态规划方法已被用于获得Circular arc 图 英语 Circular arc graph 12 和可比性补图 即可比性图 英语 Comparability graph 的补图 也包含置换图 英语 Permutation graph 13 的多项式时间算法 两者具有相同的运行时间 O n 4 displaystyle O n 4 后一种算法基于可比性补图的词典深度优先搜索 LDFS 顶点排序的特殊属性 14 对于共同可比性图 还已知有较高运行时间 O n 7 displaystyle O n 7 的另一种多项式时间算法 其基于由输入的可比性补图的补图定义的偏序关系的哈斯图 15 此外 最长路径问题可以在树宽有界或团宽有界的任何图上在多项式时间内解决 例如距离 遗传图 英语 Distance hereditary graph 最后 在哈密顿路径问题是NP难的所有图上显然最长路径问题也是NP难的 例如在分割图 英语 Split graph 圆图 英语 Circle graph 和平面图上 参数化复杂性 编辑当通过路径长度参数化时 最长路径问题是固定参数易处理 英语 Parameterized complexity 的 例如 可以通过执行以下步骤的算法 以输入图大小的线性时间求解最长路径问题 但对于路径长度呈指数时间 对图进行深度优先搜索 设d displaystyle d 是得到的深度优先搜索树 英语 Tremaux tree 的深度 使用深度优先搜索树的根到叶路径的顺序 按照搜索遍历的顺序 构建图的路径分解 英语 Pathwidth 路径宽度为d displaystyle d 将动态规划应用于此路径分解以找到最长的路径 时间是O d 2 d n displaystyle O d 2 d n 其中n displaystyle n 是图中顶点的数量 由于输出路径的长度至少与d displaystyle d 一样大 因此运行时间也受 O ℓ 2 ℓ n displaystyle O ell 2 ell n 的限制 其中ℓ displaystyle ell 是最长路径的长度 16 参见 编辑Gallai Hasse Roy Vitaver定理 英语 Gallai Hasse Roy Vitaver theorem 最长路径与图着色的对偶关系 最长无交叉骑士路径 英语 Longest uncrossed knight s path 盒中蛇 英语 Snake in the box 问题中 超立方体图 英语 Hypercube graph 中的最长诱导路径 英语 Induced path 参考文献 编辑 Schrijver Alexander Combinatorial Optimization Polyhedra and Efficiency Volume 1 Algorithms and Combinatorics 24 Springer 114 2003 ISBN 9783540443896 Cormen Thomas H Leiserson Charles E Rivest Ronald L Stein Clifford Introduction To Algorithms 2nd MIT Press 978 2001 ISBN 9780262032933 Lawler Eugene L Combinatorial Optimization Networks and Matroids Courier Dover Publications 64 2001 ISBN 9780486414539 王建新 杨志彪 陈建二 最长路径问题研究进展 计算机科学 2010 03 02 36 12 1 4 31 2022 08 15 doi 10 3969 j issn 1002 137X 2009 12 001 5 0 5 1 Sedgewick Robert Wayne Kevin Daniel Algorithms 4th Addison Wesley Professional 661 666 2011 ISBN 9780321573513 Di Battista Giuseppe Eades Peter Tamassia Roberto Tollis Ioannis G Layered Drawings of Digraphs Graph Drawing Algorithms for the Visualization of Graphs Prentice Hall 265 302 1998 ISBN 978 0 13 301615 4 Bulterman R W van der Sommen F W Zwaan G Verhoeff T van Gasteren A J M On computing a longest path in a tree Information Processing Letters 2002 81 2 93 96 doi 10 1016 S0020 0190 01 00198 3 Uehara Ryuhei Uno Yushi Efficient algorithms for the longest path problem Isaac 2004 Lecture Notes in Computer Science 2004 3341 871 883 ISBN 978 3 540 24131 7 doi 10 1007 978 3 540 30551 4 74 Uehara Ryuhei Valiente Gabriel Linear structure of bipartite permutation graphs and the longest path problem Information Processing Letters 2007 103 2 71 77 CiteSeerX 10 1 1 101 96 doi 10 1016 j ipl 2007 02 010 Takahara Yoshihiro Teramoto Sachio Uehara Ryuhei Longest path problems on Ptolemaic graphs IEICE Transactions 2008 91 D 2 170 177 doi 10 1093 ietisy e91 d 2 170 Ioannidou Kyriaki Mertzios George B Nikolopoulos Stavros D The longest path problem has a polynomial solution on interval graphs Algorithmica 2011 61 2 320 341 CiteSeerX 10 1 1 224 4927 S2CID 7577817 doi 10 1007 s00453 010 9411 3 Mertzios George B Bezakova Ivona Computing and counting longest paths on circular arc graphs in polynomial time Discrete Applied Mathematics 2014 164 2 383 399 CiteSeerX 10 1 1 224 779 doi 10 1016 j dam 2012 08 024 Mertzios George B Corneil Derek G A simple polynomial algorithm for the longest path problem on cocomparability graphs SIAM Journal on Discrete Mathematics 2012 26 3 940 963 S2CID 4645245 arXiv 1004 4560 doi 10 1137 100793529 Corneil Derek G Krueger Richard A unified view of graph searching SIAM Journal on Discrete Mathematics 2008 22 4 1259 1276 doi 10 1137 050623498 Ioannidou Kyriaki Nikolopoulos Stavros D The longest path problem is polynomial on cocomparability graphs PDF Algorithmica 2011 65 177 205 2022 08 15 CiteSeerX 10 1 1 415 9996 S2CID 7271040 doi 10 1007 s00453 011 9583 5 原始内容存档 PDF 于2022 08 15 Bodlaender Hans L On linear time minor tests with depth first search Journal of Algorithms 1993 14 1 1 23 MR 1199244 doi 10 1006 jagm 1993 1001 For an earlier FPT algorithm with slightly better dependence on the path length but worse dependence on the size of the graph see Monien B How to find long paths efficiently Analysis and design of algorithms for combinatorial problems Udine 1982 North Holland Math Stud 109 Amsterdam North Holland 239 254 1985 ISBN 9780444876997 MR 0808004 doi 10 1016 S0304 0208 08 73110 4 外部链接 编辑 Find the Longest Path 页面存档备份 存于互联网档案馆 song by Dan Barrett 取自 https zh wikipedia org w index php title 最长路径问题 amp oldid 74294951, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。