TSP问题（dp实现）

TSP问题

给定n个顶点组成的带权有向图矩阵,要求从顶点0出发，经过每个顶点恰好一次后再回到顶点0，问所经过的变得权值的最小值是多少？

动态规划

设dp[v][S]：v表示当前所在节点，S是集合，表示从v出发历经S中所有节点各一次到达0的最短距离，
这里的集合我们用二进制来表示。

初始值：
当S集合没有顶点时，dp[v][S]表示从v直接到0的距离，那么dp[v][S]=d[v][0]（邻接矩阵表示图）

递归表达式：
当S非空的时候，假设S={v1,v2,v3}，那么根据dp中元素的意义：dp[v][S]经过v1,v2,v3各一次到达0的最短距离，这就可以分成3种情况：

  • v先到v1，再从v1经过S/v1回到0
  • v先到v2，再从v2经过S/v2回到0
  • v先到v3，再从v3经过S/v3回到0

图解：

注：最终S集合中不再有顶点时，层次不在增加

集合的表示

如何用一个整数表示集合？
二进制的枚举：
图中除起点0之外有1，2，3，4，我们用一个二进制数表示这些顶点的集合
例：
S=7：集合S={1,2,3}

判断集合中是否存在某个点
1位于二进制数的第一位：S&1
2位于二进制数的第二位：S>>1&1
3位于二进制数的第三位：S>>2&1
……,……
k位于二进制数的第k位：(S>>(k-1))&1

删除集合中的某个点
与判断的方法类似，先找到它再二进制数中的位置，再利用^将此位置变为0
删除顶点k: S^(1<<(k-1))

初始dp数组：

代码：

#include<iostream>
#include<stdlib.h>
#include<algorithm>
#define INF 100
using namespace std;

int n=5;
int d[5][5] = { {0,3,INF,4,INF},
   {INF,0,5,INF,INF},
   {4,INF,0,5,INF},
   {INF,INF,INF,0,3},
   {7,6,INF,INF,0} };
int dp[5][1 << 4];

void DP() {
for (int i = 0; i < n; i++)
dp[i][0] = d[i][0];
//以列从左往右计算dp数组
for (int S = 1; S < 1 << 4; S++) {
for (int v = 0; v < n; v++) {
dp[v][S] = INF;
//当S中包含v时跳过
if (((S >> (v - 1)) & 1) == 1) continue;

//遍历所有顶点，若S中包含点k，则例举v到k，再经过S/k到0的距离
for (int k = 1; k < 5; k++) {
if (((S >> (k - 1)) & 1) == 0) continue;
dp[v][S] = min(dp[v][S], dp[k][S ^ (1 << (k - 1))] + d[v][k]);
}
}
}
}

int main() {
DP();
//dp[0][(1 << 4) - 1]表示从0经过{1,2,3,4}再到0
cout << dp[0][(1 << 4) - 1];
system("pause");
}
赞 (0)

相关推荐