动态规划算法

请注意，如果我们考虑路径（按顺序）：

(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 才能输出确切的答案。