漢密爾頓路徑檢查器

漢密爾頓路徑檢查器

漢密爾頓路徑檢查器 用於判定圖形是否包含 漢密爾頓路徑（訪問每個頂點恰好一次的序列）或 漢密爾頓迴圈（額外回到起始頂點的路徑）。它結合了快速的結構預檢查（連通性、度數先決條件、Dirac 定理、Ore 定理）與 Warnsdorff 啟發式優化的回溯搜尋，並透過逐步動畫視覺化見證路徑。

什麼是漢密爾頓路徑？

給定一個具有 n 個頂點的圖 G = (V, E)，漢密爾頓路徑 是所有頂點的一個有序序列 v₁, v₂, …, v_n，使得每一對連續的頂點 (v_i, v_i+1) 都是 G 的一條邊，且每個頂點恰好出現一次。如果額外滿足 (v_n, v₁) 也是一條邊，則該序列稱為 漢密爾頓迴圈。

此問題以 William Rowan Hamilton 的名字命名。他在 1857 年發明了 Icosian game（二十面體遊戲），要求解題者在正十二面體的頂點上找到一個恰好訪問每個頂點一次的迴圈。

為何困難：NP-Completeness

漢密爾頓路徑判定問題和漢密爾頓迴圈判定問題都是 NP-complete（Karp, 1972）。除非 P = NP，否則不存在能解決所有情況的多項式時間演算法。在最壞的情況下，回溯搜尋需要探索大小達 (n−1)! 的搜尋樹。這就是為什麼本計算機將輸入限制為 20 個頂點的原因 —— n 的微小增加會導致執行時間呈爆炸式增長。

在實踐中，Warnsdorff 啟發式（由 Heinrich Warnsdorff 於 1823 年針對騎士巡邏問題提出）使結構化圖形的搜尋速度大幅提升：在每一步中，演算法將當前路徑延伸到具有 最少 剩餘未訪問鄰居的未訪問頂點。這種貪婪規則能防止搜尋陷入死角，並經常在性能良好的圖形上找到無回溯的漢密爾頓巡迴。

必要條件 —— 快速拒絕

在執行昂貴的搜尋之前，本計算機會拒絕那些絕對不可能包含漢密爾頓路徑的圖形：

• 連通性。 漢密爾頓路徑必須訪問每個頂點，因此圖形必須恰好有一個連通分量。對於有向圖，需要弱連通性（忽略箭頭方向）。
• 度數 (無向)。 最多只能有兩個頂點的度數為 1 —— 它們是路徑端點的僅有候選者。對於漢密爾頓 迴圈，每個頂點的度數必須至少為 2。
• 度數 (有向)。 對於漢密爾頓路徑，最多只能有一個頂點入度為 0（起點），且最多只有一個頂點出度為 0（終點）。對於漢密爾頓 迴圈，每個頂點的入度與出度都必須 ≥ 1。

這些規則能在線性時間內拒絕許多無望的輸入，避免浪費回溯精力。

充分條件 —— 經典定理

幾條經典定理給出了保證無向簡單圖中存在漢密爾頓迴圈的 充分（但非必要）條件。如果其中任何一條適用，計算機會將結果標記為「保證存在」而無需運行搜尋 —— 儘管它仍會展示一個見證迴圈。

Dirac 定理 (1952)

如果 G 是一個頂點數 n ≥ 3 的簡單無向圖，且每個頂點的度數至少為 n / 2，則 G 具有漢密爾頓迴圈。

Ore 定理 (1960)

如果對於每一對不相鄰的頂點 u 和 v，我們有 deg(u) + deg(v) ≥ n，則 G 具有漢密爾頓迴圈。Ore 的條件嚴格來說比 Dirac 的更弱，因此 Ore 定理蘊含了 Dirac 定理。

未能滿足 Dirac 或 Ore 條件並不代表圖形缺乏漢密爾頓迴圈 —— 許多圖形兩者都不滿足但仍包含一個（例如，一個簡單的 n-迴圈最小度數為 2，在 n 較大時遠低於 n/2）。

內部搜尋演算法

當預檢查無法確定結果時，計算機會在圖形的鄰接表示上執行回溯搜尋。關鍵策略包括：

1. 位元遮罩訪問集。 已訪問的頂點以位元遮罩形式儲存（對於最多 20 個頂點，O(1) 快速成員測試）。
2. Warnsdorff 啟發式。 在每次延伸時，按鄰居剩餘的未訪問度數排序嘗試（最小優先），模擬「低分叉」順序。
3. 根節點選擇。 對於漢密爾頓 迴圈，只需要一個起始頂點（迴圈具有旋轉不變性）。對於漢密爾頓 路徑，按出度升序嘗試起點 —— 優先嘗試最稀有的位置。
4. 步驟預算。 設有硬性上限以防止病態實例無限執行；如果預算耗盡，UI 將報告 verdict 為「逾時」。

漢密爾頓 vs 歐拉

漢密爾頓問題與歐拉問題很容易混淆 —— 它們聽起來很像，但本質上完全不同：

支援的輸入格式

邊列表

每行一條邊，或以逗號分隔。支援的分隔符號：A-B, A B, A,B, A--B, A->B, A<-B。使用 -> 強制解釋為有向邊。

鄰接矩陣

0/1 值的方陣，每行一列，以空格或逗號分隔。在「矩陣標籤」欄位中提供選填標籤；否則將自動使用 A, B, C…。

如何使用此檢查器

1. 挑選輸入格式 —— 手寫小型圖形選「邊列表」，從程式碼或教科書貼上選「鄰接矩陣」。
2. 貼上您的圖形 到文字區域。對於矩陣輸入，可選擇提供頂點標籤。
3. 選擇檢查項目：單次運行檢查路徑、迴圈或兩者。
4. 選擇圖形類型 —— 「自動檢測」會根據箭頭樣式 (->) 或矩陣對稱性推斷有向性。
5. 點擊「檢查漢密爾頓」。 結果頁面會顯示判定標題、必要條件預檢查、Dirac / Ore 充分條件測試、見證路徑（如果存在）以及互動式視覺化。
6. 重播見證，使用「播放 / 單步」控制。觀看路徑在圖上一邊一邊地亮起。

實例演示 —— Petersen 圖

著名的 Petersen 圖（10 個頂點，15 條邊，3-正則圖）是具有漢密爾頓路徑但 沒有 漢密爾頓迴圈的教科書範例。將此內容貼到邊列表欄位並點擊檢查：

檢查器確認：找到漢密爾頓路徑（例如 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3），但窮舉搜尋未發現閉合回到起點的方法 —— 這一結果最早在 1890 年代得到證明。

常見應用

• 路由與旅行推銷員問題 (TSP) —— 每個 TSP 巡迴都是完全權重圖中的一個漢密爾頓迴圈。
• 基因組組裝 —— 從重疊讀數重建 DNA 序列可以建模為重疊圖中的漢密爾頓路徑。
• 電路佈局 —— 在 PCB 上排列引腳以實現最小佈線長度。
• 遊戲 AI 與謎題求解 —— 棋盤上的騎士巡邏、Icosian game。
• 排程 —— 安排任務序列，使每個任務都能可行地過渡到下一個。
• 組合數學教學 —— 透過可手動求解的小型範例說明 NP-completeness。

常見問題

什麼是漢密爾頓路徑？

漢密爾頓路徑是圖中經過每個頂點恰好一次的走法。它以 William Rowan Hamilton 的名字命名，他在 1857 年研究了十二面體圖上的這個問題。判定是否存在這樣的路徑是一個 NP-complete 問題，因此目前尚無已知的演算法能在多項式時間內解決所有圖形。

漢密爾頓迴圈與漢密爾頓路徑有何不同？

漢密爾頓迴圈是一條回到起始頂點的漢密爾頓路徑，形成一個訪問每個頂點恰好一次的封閉迴圈。每個漢密爾頓迴圈都包含一條漢密爾頓路徑（只需去掉閉合邊），但反之則不然：許多圖具有漢密爾頓路徑但沒有漢密爾頓迴圈。

Dirac 定理說了什麼？

Dirac 定理（1952 年）指出，在任何頂點數 n ≥ 3 的簡單無向圖中，如果每個頂點的度數至少為 n/2，則該圖包含一個漢密爾頓迴圈。這是一個充分但非必要條件：許多未達到 Dirac 閾值的圖仍然具有漢密爾頓迴圈。

Ore 定理說了什麼？

Ore 定理（1960 年）指出，如果對於頂點數 n ≥ 3 的簡單圖中的每一對不相鄰頂點 u 和 v，其度數之和至少為 n，則該圖具有漢密爾頓迴圈。Ore 的條件比 Dirac 的更弱，因此只要 Dirac 定理適用，Ore 定理就適用。

為什麼搜尋限制在 20 個頂點？

漢密爾頓路徑和迴圈判定問題是 NP-complete。最壞情況下的執行時間隨頂點數量呈指數級增長。透過剪枝和 Warnsdorff 啟發式，本計算機可以快速處理許多多達 20 個頂點的小型圖形，但更困難的情況可能會逾時。超過 20 個頂點，您應該使用專業的求解器，如 Concorde 或整數規劃公式。

什麼是 Warnsdorff 啟發式？

Warnsdorff 規則於 1823 年針對騎士巡邏問題提出，它指出在每一步中，您應該訪問下一個具有最少剩餘未訪問鄰居的頂點。這種看似貪婪的規則在實踐中極大地剪枝了回溯樹，並且在正則圖上通常無需回溯即可找到漢密爾頓路徑。

這款工具會找出所有漢密爾頓路徑嗎？

不會。它會在存在漢密爾頓路徑或迴圈時找到單個見證路徑。計算漢密爾頓路徑的總數本身是一個 #P-complete 問題，比判定問題難得多。對於枚舉，專門的工具或整數規劃求解器更合適。

延伸閱讀

• 漢密爾頓路徑 —— 維基百科
• 漢密爾頓路徑問題 —— 維基百科
• 關於漢密爾頓迴圈的 Dirac 定理 —— 維基百科
• Ore 定理 —— 維基百科
• Warnsdorff 規則 —— 維基百科

進階數學計算:

• 鄰接矩陣計算機 新
• antilog計算機
• Beta函數計算機
• 二項式係數計算機
• 二項機率分布計算機
• 按位計算機
• 布林代數化簡器 新
• 中央極限定理計算機
• 中國剩餘定理計算機
• 組合計算機 熱門
• 互補誤差函數計算機
• 複數計算機 熱門
• 連分數計算機
• 錯排 子階乘計算機
• 戴克斯特拉最短路徑計算機
• 熵計算機
• 誤差函數計算機
• 歐拉函數計算機
• 指數衰減計算機（高精度）
• 指數增長計算機 高精度
• 指數積分計算機
• 指數計算機（高精度）
• 擴展歐幾里得演算法計算機
• 階乘計算機 熱門
• 伽瑪功能計算機
• 黃金比例計算機
• 圖著色計算機 新
• 圖度數序列驗證器
• 群論階數計算機 新
• 半衰期計算機
• 漢密爾頓路徑檢查器 新
• 容斥原理計算機 新
• 卡諾圖 (K-Map) 求解器 新
• 線性規劃求解器 新
• 馬可夫鏈穩態分布計算機
• 最小生成樹計算機
• 模冪運算計算機 新
• 模乘逆元計算機
• 負二項分布計算機 新
• 網路最大流計算機 新
• 百分比增長率計算機 熱門
• 排列計算機
• 重複排列計算機 新
• 鴿巢原理計算機
• 平面圖檢查器 新
• 泊松分佈計算機
• 多項式根計算機與詳細步驟
• 原根計算機
• 機率計算機
• 機率分布計算機
• 比例計算機 熱門
• 二次公式計算機 熱門
• 環與體計算機 新
• 四捨五入計算機 熱門
• 科學計算機
• 科學記數法計算機 熱門
• 集合論計算機
• 有效數字計算機 熱門
• 穩定婚姻問題求解器 新
• 斯特林數計算機
• 立方和計算機
• 連續數之和計算機
• 平方和計算機
• 拓撲排序計算機 新
• 旅行推銷員問題求解器 (TSP) 新
• 真值表產生器
• 韋恩圖產生器3集合