Loading AI tools
来自维基百科,自由的百科全书
圖論中的經典問題漢米頓路徑問題(中國大陸作哈密頓路徑問題,台灣作漢米頓路徑問題)(Hamiltonian path problem)與漢米頓環問題(中國大陸作哈密頓環問題,台灣作漢米頓環問題)(Hamiltonian cycle problem)分別是來確定在一個給定的圖上是否存在哈密頓路徑(一條經過圖上每個頂點的路徑)和哈密頓環(一條經過圖上每個頂點的環)。兩個問題皆為NP完全。[1]
哈密頓環問題與哈密頓路徑問題之間有着很簡單的關係:
在一個階數為的圖中,可能成為哈密頓路徑的頂點序列最多有有!個(在完全圖的情況下恰好為!個),因此暴力搜索所有可能的頂點序列是非常慢的。 一個早期的在有向圖上尋找哈密頓環的算法是Martello的枚舉算法[3] 由Frank Rubin[4] 提供的搜索過程將圖的邊分為3種類型:必須在路徑上的邊、不能在路徑上的邊和未定邊。在搜索的過程中,一個決策規則的集合將未定邊進行分類,並且決定是否繼續進行搜索。這個算法將圖分成幾個部分,在它們上問題能夠被單獨地解決。
另外,Bellman, Held, and Karp 的動態規劃算法可以在O(n2 2n)時間內解決問題。在這個方法中,對每個頂點集和其中的每一個頂點 ,均做出如下的判定:是否有一條經過中每個頂點,並且在結束的路徑,對於每一對和,若且唯若存在的鄰居滿足存在一條路徑經過的所有頂點,並在上結束的路徑時,存在路徑經過中每個頂點,並且在結束。這個充要條件已經可以之前的動態規劃計算中確認。[5][6]
Andreas Björklund通過容斥原理將哈密爾頓環的計數問題規約成一個更簡單,圈覆蓋的計數問題,後者可以被通過計算某些矩陣的行列式解決。通過這個方法,並通過蒙特卡洛算法,對任意階圖,可以在O(1.657n)時間內解決。對於二分圖,這個算法可以被進一步提升至o(1.415n)。[7]
對於最大度小於等於3的圖,一個回溯搜索的方法可以在 O(1.251n)時間內找到哈密頓環。[8]
哈密頓環和哈密頓路徑也可以通過SAT 求解器找到。
哈密頓環和哈密頓路徑問題是FNP問題,它的決定性問題是檢測是否存在一條哈密頓環或哈密頓路徑。有向圖和無向圖上的哈密頓環問題是卡普的二十一個NP-完全問題中的其中兩個。對於一些特殊類型的圖來說,它們仍然是NP完全的。例如:
然而,對於某些類型的圖,哈密頓環和哈密頓路徑問題可以在多項式時間內解決:
將以上提供的條件匯總起來,3-正則,3-定點連通的二分圖是否總是存在哈密頓環這一問題仍然是開放的,在這個情況下這一問題不是NP完全的,詳見Barnette猜想。
在所有頂點的度都是奇數的途中,一個與握手引理有關的結論說明對於任意一條邊來說,經過它的哈密頓環的個數總是偶數,因此如果存在一條哈密頓環,則一定存在另一條 [17] 然而,找到第二條哈密頓換並不是一個簡單的計算問題。Papadimitriou定義了一個複雜性類 PPA來描述這一類問題。 [18]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.