動態規劃演算法

請注意，如果我們考慮路徑（按順序）：

(1,2,3,4,6,0,5,7)

和路徑

(1,2,3,5,0,6,7,4) 

從頂點 1 到頂點 2 到頂點 3 的成本保持不變，為什麼必須重新計算？可以儲存該結果以供以後使用。

讓 dp[bitmask][vertex] 表示穿過所有頂點的最小成本，其中 bitmask 中的相應位設定為以 vertex 結尾的 1。例如：

dp[12][2] 

   12   =   1 1 0 0
            ^ ^ 
vertices:   3 2 1 0

由於 12 以二進位制表示 1100，因此 dp[12][2] 表示在圖中通過頂點 2 和 3，其路徑在頂點 2 處結束。

因此我們可以使用以下演算法（C++實現）：

int cost[N][N];                        //Adjust the value of N if needed
int memo[1 << N][N];                   //Set everything here to -1
int TSP(int bitmask, int pos){
    int cost = INF;
    if (bitmask == ((1 << N) - 1)){      //All vertices have been explored
        return cost[pos][0];             //Cost to go back
    }
    if (memo[bitmask][pos] != -1){       //If this has already been computed
        return memo[bitmask][pos];       //Just return the value, no need to recompute
    }
    for (int i = 0; i < N; ++i){         //For every vertex 
        if ((bitmask & (1 << i)) == 0){  //If the vertex has not been visited
            cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);   //Visit the vertex
        } 
    }
    memo[bitmask][pos] = cost;           //Save the result
    return cost;
}
//Call TSP(1,0)

這條線可能有點令人困惑，所以讓我們慢慢來看看：

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

這裡，bitmask | (1 << i) 將 bitmask 的第 i 位設定為 1，表示已經訪問了第 i 個頂點。逗號後面的 i 代表該函式呼叫中的新 pos，它表示新的最後頂點。cost[pos][i] 是增加從頂點 pos 到頂點 i 的旅行費用。

因此，這一行是將 cost 的值更新為前往尚未訪問過的每個其他頂點的最小可能值。

時間複雜性

函式 TSP(bitmask,pos) 具有 2^N 的 2^N 值和 N 的 N 值。每個函式需要執行時間（for 迴圈）。因此，這種實現需要時間 28 才能輸出確切的答案。