查看“︁最长路径问题”︁的源代码

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

== NP-困难性 ==
可以从[[哈密顿路径问题]][[规约]]到未加权最长路径问题，这显示出后者屬於[[NP-困难]]類別：当且仅当图''G''的最长路径的长度是n−1时（n是圖中顶点的数量），图''G''有哈密顿路径。 由于哈密顿路径问题是NP完全的，此规约表明最长路径问题的[[決定性問題|决定版本]]也是NP完全的。在该决定问题中，输入是图''G''和数''k；''如果''G''中存在至少一條由''k''条或更多条边的路径，则输出为“是”，否则为“否”。<ref>{{citation|title=Combinatorial Optimization: Polyhedra and Efficiency, Volume 1|volume=24|series=Algorithms and Combinatorics|first=Alexander|last=Schrijver|publisher=Springer|year=2003|isbn=9783540443896|page=114|url=https://books.google.com/books?id=mqGeSQ6dJycC&pg=PA114}}.</ref>

如果可以在多项式时间内解决最长路径问题，则可以通过找到最长路径，然后将其长度与数''k''进行比较来将其用于解决该决定问题。因此，最长的路径问题是NP难的。问题“在给定图中是否存在具有至少''k''条边的简单路径”是NP完全的。<ref>{{citation|title=Introduction To Algorithms|first1=Thomas H.|last1=Cormen|first2=Charles E.|last2=Leiserson|first3=Ronald L.|last3=Rivest|author3-link=罗纳德·李维斯特|first4=Clifford|last4=Stein|edition=2nd|publisher=MIT Press|year=2001|isbn=9780262032933|url=https://books.google.com/books?id=NLngYyWFl_YC&pg=PA978|page=978}}.</ref>

在具有非负边权的加权[[完全圖|完全图]]中，加权最长路径问题与[[旅行推销员问题]]相同，因为最长路径总是包括所有顶点。<ref>{{citation|title=Combinatorial Optimization: Networks and Matroids|first=Eugene L.|last=Lawler|publisher=Courier Dover Publications|year=2001|isbn=9780486414539|page=64|url=https://books.google.com/books?id=m4MvtFenVjEC&pg=PA64}}.</ref>

== 无环图 ==
在加权图''G''中两个给定顶点''s''和''t''之间的最长路径，与通过将''G''中每个权重改变为其相反数所导出的图''-G''中的最短路径相同。因此，如果在''-G''中找到最短路径，则在''G''中也可以找到最长路径。<ref>{{Cite journal |author=王建新 |author2=杨志彪 |author3=陈建二 |title=最长路径问题研究进展 |url=https://d.wanfangdata.com.cn/periodical/jsjkx200912001 |journal=计算机科学 |publication-date=2010-03-02 |volume=36 |issue=12 |page=1-4,31 |doi=10.3969/j.issn.1002-137X.2009.12.001 |access-date=2022-08-15}}</ref>

对于大多数图而言，此变换并无用途，因为它在''-G''中产生了负环。但是如果''G''是[[有向无环图]]（DAG），则不会有负环，并且通过对''-G''中的最短路径应用线性时间算法，可以在[[線性時間|线性时间]]里找到G的最长路径，因''-G''也是有向无环图。<ref name=":0">{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin Daniel|last2=Wayne|edition=4th|publisher=Addison-Wesley Professional|year=2011|isbn=9780321573513|pages=661–666|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA661}}.</ref>

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

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

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

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

有向无环图的最长路径也可以用于{{En-link|分层图绘制|layered graph drawing}}：将有向无环图''G''的每个顶点''v''分到层数是以''v''结尾的最长路径长度的层，这种层分配使''G''的层数最小。<ref>{{citation|last1=Di Battista|first1=Giuseppe|last2=Eades|first2=Peter|last3=Tamassia|first3=Roberto|last4=Tollis|first4=Ioannis G.|contribution=Layered Drawings of Digraphs|isbn=978-0-13-301615-4|pages=265–302|publisher=[[Prentice Hall]]|title=Graph Drawing: Algorithms for the Visualization of Graphs|year=1998}}.</ref>

== 图的特例 ==
迪杰斯特拉在20世纪60年代提出了一种用于在树中找到最长路径的线性时间算法，而该算法的正式证明于2002年出版。<ref>{{citation|last1=Bulterman|first1=R.W.|last2=van der Sommen|first2=F.W.|last3=Zwaan|first3=G.|last4=Verhoeff|first4=T.|last5=van Gasteren|first5=A.J.M.|doi=10.1016/S0020-0190(01)00198-3|journal=Information Processing Letters|title=On computing a longest path in a tree|issue=2|pages=93–96|volume=81|year=2002}}.</ref>此外，最长路径可以在加权树上，{{En-link|块图|Block graph}}上，{{En-link|仙人掌图|Cactus graph}}上，<ref>{{citation|last1=Uehara|first1=Ryuhei|last2=Uno|first2=Yushi|journal=Isaac 2004|volume=3341|title=Efficient algorithms for the longest path problem|pages=871–883|year=2004|doi=10.1007/978-3-540-30551-4_74|series=Lecture Notes in Computer Science|isbn=978-3-540-24131-7}}.</ref>[[二分图|二分]]{{En-link|置换图|Permutation graph}}上，<ref>{{citation|last1=Uehara|first1=Ryuhei|last2=Valiente|first2=Gabriel|doi=10.1016/j.ipl.2007.02.010|journal=Information Processing Letters|title=Linear structure of bipartite permutation graphs and the longest path problem|issue=2|pages=71–77|volume=103|year=2007|citeseerx=10.1.1.101.96}}.</ref>和{{En-link|托勒密图|Ptolemaic graph}}上<ref>{{citation|last1=Takahara|first1=Yoshihiro|last2=Teramoto|first2=Sachio|last3=Uehara|first3=Ryuhei|journal=IEICE Transactions|title=Longest path problems on Ptolemaic graphs|pages=170–177|volume=91-D|issue=2|year=2008|doi=10.1093/ietisy/e91-d.2.170|doi-access=free}}.</ref>以多项式时间计算。

对于{{En-link|区间图|Interval graph}}，已知 <math>O(n^4)</math>时间的算法，其使用动态规划方法。<ref>{{citation|last1=Ioannidou|first1=Kyriaki|last2=Mertzios|first2=George B.|last3=Nikolopoulos|first3=Stavros D.|doi=10.1007/s00453-010-9411-3|journal=Algorithmica|title=The longest path problem has a polynomial solution on interval graphs|issue=2|pages=320–341|volume=61|year=2011|citeseerx=10.1.1.224.4927|s2cid=7577817}}.</ref>这种动态规划方法已被用于获得{{En-link|Circular-arc 图|Circular-arc graph}}<ref>{{citation|last1=Mertzios|first1=George B.|last2=Bezakova|first2=Ivona|doi=10.1016/j.dam.2012.08.024|journal=Discrete Applied Mathematics|title=Computing and counting longest paths on circular-arc graphs in polynomial time|issue=2|pages=383–399|volume=164|year=2014|citeseerx=10.1.1.224.779}}.</ref>和可比性补图（即{{En-link|可比性图|Comparability graph}}的[[補圖|补图]]，也包含{{En-link|置换图|Permutation graph}}）<ref>{{citation|last1=Mertzios|first1=George B.|last2=Corneil|first2=Derek G.|doi=10.1137/100793529|journal=SIAM Journal on Discrete Mathematics|title=A simple polynomial algorithm for the longest path problem on cocomparability graphs|issue=3|pages=940–963|volume=26|year=2012|arxiv=1004.4560|s2cid=4645245}}.</ref>的多项式时间算法，两者具有相同的运行时间 <math>O(n^4)</math>。后一种算法基于可比性补图的词典深度优先搜索（LDFS）顶点排序的特殊属性。<ref>{{citation|last1=Corneil|first1=Derek G.|last2=Krueger|first2=Richard|doi=10.1137/050623498|journal=SIAM Journal on Discrete Mathematics|title=A unified view of graph searching|issue=4|pages=1259–1276|volume=22|year=2008}}.</ref>对于共同可比性图，还已知有较高运行时间 <math>O(n^7)</math>的另一种多项式时间算法，其基于由输入的可比性补图的[[補圖|补图]]定义的[[偏序关系]]的[[哈斯圖|哈斯图]]。<ref>{{citation|last1=Ioannidou|first1=Kyriaki|last2=Nikolopoulos|first2=Stavros D.|doi=10.1007/s00453-011-9583-5|journal=Algorithmica|volume=65|pages=177–205|title=The longest path problem is polynomial on cocomparability graphs|url=http://www.cs.uoi.gr/~stavros/J-Papers/J-2012-ALGO.pdf|year=2011|citeseerx=10.1.1.415.9996|s2cid=7271040|accessdate=2022-08-15|archive-date=2022-08-15|archive-url=https://web.archive.org/web/20220815083323/https://www.cs.uoi.gr/~stavros/J-Papers/J-2012-ALGO.pdf|dead-url=no}}.</ref>

此外，最长路径问题可以在树宽有界或团宽有界的任何图上在多项式时间内解决，例如{{En-link|距离-遗传图|Distance-hereditary graph}}。最后，在哈密顿路径问题是NP难的所有图上显然最长路径问题也是NP难的，例如在{{En-link|分割图|Split graph}}，{{En-link|圆图|Circle graph}}和[[平面图 (图论)|平面图]]上。

== 参数化复杂性 ==
当通过路径长度参数化时，最长路径问题是[[参数化复杂性|固定参数易处理]]的。例如，可以通过执行以下步骤的算法，以输入图大小的线性时间求解最长路径问题（但对于路径长度呈指数时间）：

# 对图进行[[深度优先搜索]]。设<math>d</math>是得到的{{En-link|深度优先搜索树|Trémaux tree}}的深度。
# 使用深度优先搜索树的根到叶路径的顺序，按照搜索遍历的顺序，构建图的{{En-link|路径宽度|Pathwidth|路径分解}}，路径宽度为<math>d</math>。
# 将[[动态规划]]应用于此路径分解以找到最长的路径 ，时间是<math>O(d!2^dn)</math>，其中<math>n</math>是图中顶点的数量。

由于输出路径的长度至少与<math>d</math>一样大，因此运行时间也受 <math>O(\ell!2^\ell n)</math>的限制，其中<math>\ell</math>是最长路径的长度。<ref>{{citation|last=Bodlaender|first=Hans L.|authorlink=Hans L. Bodlaender|doi=10.1006/jagm.1993.1001|issue=1|journal=Journal of Algorithms|mr=1199244|pages=1–23|title=On linear time minor tests with depth-first search|volume=14|year=1993}}. For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see {{citation|last=Monien|first=B.|contribution=How to find long paths efficiently|doi=10.1016/S0304-0208(08)73110-4|location=Amsterdam|mr=808004|pages=239–254|publisher=North-Holland|series=North-Holland Math. Stud.|title=Analysis and design of algorithms for combinatorial problems (Udine, 1982)|volume=109|year=1985|isbn=9780444876997|url=http://nbn-resolving.de/urn:nbn:de:hbz:466:2-4393}}.</ref>

== 参见 ==
* {{le|Gallai-Hasse-Roy-Vitaver定理|Gallai–Hasse–Roy–Vitaver theorem}}，最长路径与[[图着色问题|图着色]]的对偶关系
* {{le|最长无交叉骑士路径|Longest uncrossed knight's path}}
* {{le|盒中蛇|Snake-in-the-box}}问题中，{{le|超立方体图|Hypercube graph}}中的最长{{le|诱导路径|Induced path}}

== 参考文献 ==
<references />

== 外部链接 ==
* "[http://valis.cs.uiuc.edu/~sariel/misc/funny/longestpath.mp3 Find the Longest Path] {{Wayback|url=http://valis.cs.uiuc.edu/~sariel/misc/funny/longestpath.mp3 |date=20100614105441 }}", song by Dan Barrett
[[Category:图算法]]
[[Category:NP完全问题]]