您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

最短哈密爾頓回路（TSP）動態規劃算法原理與 C++ 實現

編輯：程式設計綜合問答

問題定義

給定 n 個城市及任意兩城市間距離，求訪問每個城市恰好一次並返回起點的最短路徑長度。

Held-Karp 動態規劃 (O(n²2ⁿ))

狀態定義

dp[mask][i]：已訪問城市集合為 mask (bitmask)，當前位於城市 i 的最短路徑長度。
mask 第 j 位為 1 表示城市 j 已訪問。

轉移方程

dp[mask | (1<


初始化
dp[1< (從 start 出發)。

答案
min(dp[(1< 其中 i ≠ start。

C++ 實現 (n ≤ 20)
#include <bits/stdc++.h>
using namespace std;
const double INF = 1e18;

double tsp(vector>& dist) {
    int n = dist.size();
    int ALL = 1 << n;
    vector> dp(ALL, vector(n, INF));
    dp[1][0] = 0; // 從城市 0 出發
    
    for (int mask = 1; mask < ALL; ++mask) {
        for (int u = 0; u < n; ++u) if (dp[mask][u] < INF) {
            for (int v = 0; v < n; ++v) if (!(mask & (1<

大規模近似算法

2-近似：MST 雙邊遍歷 (Christofides 算法 1.5-近似)。
啟發式：最近鄰、模擬退火、蟻群、遺傳算法。
精確求解器：Concorde TSP Solver (分支定界 + 割平面)。


						 
						 	
						
						
						
							上一篇文章： C 語言 fscanf 跳過第一行：文件編碼 BOM 導致讀取異常 
下一篇文章： 數據庫設計：一級二級分類表結構與關聯查詢最佳實踐


				
					
						程式設計綜合問答
						
					
					
						
						
							
							ASP.NET 後台隱藏 Label 但 a 標籤仍可點擊？隱藏 a 標籤本身
							後台 `daor.Visible = false;` 隱藏了			
						
						
						
							
							jstree 無限循環加載子節點：根節點 state="closed" 導致反覆請求 AJAX，移除屬性或實現懶加載邏輯
							現象

後端返回單根節點 XML，含 `state=clos			
						
						
						
							
							JSP 圖片無法顯示：本地路徑 vs Web 根目錄路徑
							現象
JSP 中 <img src=D:/projec			
						
						
						
							
							根據輸入字符比對資料庫欄位的 LIKE 查詢應用
							當使用者手動輸入話題並需要比對資料庫欄位時，最常見的做法是使