TSP DP

  1 #include <algorithm>
  2 #include <cmath>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <deque>
  6 #include <iostream>
  7 #include <map>
  8 #include <queue>
  9 #include <set>
 10 #include <stack>
 11 #include <string>
 12 #include <vector>
 13 using namespace std;
 14 typedef long long LL;
 15 const int maxn = 18;
 16 const double PI = acos(-1);
 17 const int mod = 1e9 + 7;
 18 using namespace std;
 19 // 定义常量
 20 const int INF = 0x3f3f3f3f;
 21 #define sqr(x) ((x) * (x))
 22 // 定义变量
 23 int type; // type == 1 满秩矩阵格式, type == 2 二维坐标式
 24 int s;
 25 int N; // 城市结点数量
 26 int init_point;
 27 double dp[1 << maxn][maxn];
 28 // 动态规划状态数组dp[i][j]，i表示集合V’，j表示当前到达的城市结点
 29 double dis[maxn][maxn]; // 两个城市结点之间的距离
 30 vector<int> path[1 << maxn][maxn];
 31 double ans;
 32 vector<int> ans_path;
 33 // 定义结构体
 34 struct vertex {
 35     double x, y; // 城市结点的坐标
 36     string id;   // 城市结点的id
 37     void input() {
 38         cin >> id;
 39         scanf("%lf %lf", &x, &y);
 40     }
 41 } node[maxn];
 42 
 43 double Dist(const vertex &a, const vertex &b) {
 44     return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
 45 }
 46 
 47 void init() { // 数据初始化
 48     scanf("%d", &N);
 49     for (int i = 0; i < N; i++)
 50         node[i].input();
 51     for (int i = 0; i < N; i++) {
 52         for (int j = 0; j < N; j++)
 53             dis[i][j] = Dist(node[i], node[j]); // 计算城市之间的距离
 54     }
 55     for (int i = 0; i < (1 << N); i++) {
 56         for (int j = 0; j < N; j++)
 57             dp[i][j] = INF,path[i][j].clear();
 58     } // 初始化，除了dp[1][0]，其余值都为INF
 59     ans = INF;
 60     return;
 61 }
 62 //复杂度 2^N * N^2
 63 void slove() {
 64     int M = (1 << N);
 65     // M就是第四部分所说的V’状态总数，1<<N表示2^N，总共有2^N种状态
 66     dp[1][0] = 0;
 67     path[1][0].push_back(0);
 68     // 假设固定出发点为0，从0出发回到0的花费为0。TSP只要求是一个环路，所以出发点可以任选
 69     for (int i = 1; i < M; i++) {
 70         // 枚举V’的所有状态
 71         for (int j = 1; j < N; j++) {
 72             // 选择下一个加入集合的城市
 73             if (i & (1 << j))
 74                 continue;
 75             // 城市已经存在于V’之中
 76             if (!(i & 1))
 77                 continue;
 78             // 出发城市固定为0号城市
 79             for (int k = 0; k < N; k++) {
 80                 // 在V’这个城市集合中尝试每一个结点，并求出最优解
 81                 if (i & (1 << k)) {
 82                     // 确保k已经在集合之中并且是上一步转移过来的结点
 83                     if(dp[i][k] + dis[k][j] < dp[(1 << j) | i][j]){
 84                         dp[(1 << j) | i][j] = dp[i][k] + dis[k][j];
 85                         path[(1 << j) | i][j] = path[i][k];
 86                         path[(1 << j) | i][j].push_back(j);
 87                     }
 88                     dp[(1 << j) | i][j] = min(dp[(1 << j) | i][j],
 89                                               dp[i][k] + dis[k][j]); // 转移方程
 90                 } // 将j点加入到i集合中
 91             }
 92         }
 93     }
 94     for (int i = 0; i < N; i++){
 95         if(dp[M - 1][i] + dis[i][0]< ans){
 96             ans=dp[M - 1][i] + dis[i][0];
 97             ans_path = path[M-1][i];
 98         }
 99     }
100     // 因为固定了出发点，所以要加上到城市0的距离。另外要从所有的完成整个环路的集合V’中选择，完成最后的转移
101 }
102 int main() {
103 #ifndef ONLINE_JUDGE
104     freopen("in.txt", "r", stdin);
105 #endif
106     init();
107     slove();
108     cout<<"TSP路径长度: "<<ans<<endl<<"TSP回路： ";
109     for(int i=0;i<ans_path.size();i++){
110         if(i)cout<<' ';
111         cout<<node[ans_path[i]].id;
112     }cout<<endl;
113     return 0;
114 }