維基百科

最長路徑問題

在图中寻找最长简单路径的问题

在圖論和理論計算機科學中，最長路徑問題是指在給定的圖中找出長度最長的簡單路徑。一條不具有任何重複頂點的路徑被稱為簡單路徑。無權圖中路徑的長度就是邊的數量，而有權圖中路徑長度是邊權重之和。不同的是，與此相反的最短路徑問題（不含負權環）可以在多項式時間內解決。而最長路徑問題是NP困難的，這意味着除非P = NP，否則對應於任意的圖，沒有辦法在多項式時間內解決該問題。更強的結果表明這個問題也難以近似地得出答案。但是，有一個線性時間的方法可以用於有向無環圖，這對於發現調度問題中的關鍵路徑有重要的作用。

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結尾的最長路徑的長度：

  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）和平面圖上。

參數化複雜性

編輯

當通過路徑長度參數化時，最長路徑問題是固定參數易處理的。例如，可以通過執行以下步驟的算法，以輸入圖大小的線性時間求解最長路徑問題（但對於路徑長度呈指數時間）：

  1. 對圖進行深度優先搜索。設 是得到的深度優先搜索樹（英語：Trémaux tree）的深度。
  2. 使用深度優先搜索樹的根到葉路徑的順序，按照搜索遍歷的順序，構建圖的路徑分解（英語：Pathwidth），路徑寬度為 。
  3. 將動態規劃應用於此路徑分解以找到最長的路徑 ，時間是 ，其中 是圖中頂點的數量。

由於輸出路徑的長度至少與 一樣大，因此運行時間也受  的限制，其中 是最長路徑的長度。[16]

參見

編輯

參考文獻

編輯
  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 .

外部連結

編輯
取自「https://zh.wikipedia.org/w/index.php?title=最长路径问题&oldid=80393632」