动态规划解决TSP问题

问题描述：

旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

输入：

第一行输入一个整数n(2<=n<=15)。

输出：

输出一行，就是所有路径之中的最小值。

样例输入：

10

42 160 34 136 134 94 78 18 196

42 166 66 106 87 11 122 195 32

160 166 4 98 198 3 154 75 121

34 66 4 187 112 52 94 36 144

136 106 98 187 12 64 45 46 48

134 87 198 112 12 154 109 196 131

94 11 3 52 64 154 11 79 80

78 122 154 94 45 109 11 13 86

18 195 75 36 46 196 79 13 162

196 32 121 144 48 131 80 86 162

样例输出：

284

---

源代码:

#include <iostream>
#include<stdio.h>
#include<iomanip>
using namespace std;

int main()
{
    int n,temp,minDis;

        cin>>n;
        int dis[n][n]={0};     //dis为距离矩阵

        for(int i=0;i<n;i++){     //以下为距离矩阵的初始化
            for(int j=0;j<n;j++){
                if(j!=i){
                    cin>>temp;
                    dis[i][j]=temp;
                }
                else{
                    dis[i][j]=1000;
                }
            }
        }


        int d[n][1<<(n-1)]; //1<<(n-1)]表示2的n-1次方，d[]为动态规划存储的城市经过矩阵
        for(int i=1;i<n;i++){     //将所有城市到第0个城市的路径初始化为两市间的距离
            d[i][0]=dis[i][0];
        }

        for(int j=1;j<1<<(n-1);j++){
            for(int i=1;i<n;i++){    //j用二进制表示的城市集合
                    if(((1<<(i-1))&j)==0){         //i不在j表示的城市集合中

                        minDis=60000;
                        for(int k=1;k<n;k++){
                        if(((1<<(k-1))&j)!=0)  {//k表示的城市在j表示的城市集合中

                        temp=dis[i][k]+d[k][j-(1<<(k-1))];
                        if(temp<minDis){
                            minDis=temp;   //所有k中最小的距离
                        }
                        }
                        }
                    }
                    d[i][j]=minDis;
            }
        }
        minDis=60000;
        for(int k=1;k<n;k++){
            temp=dis[0][k]+d[k][((1<<(n-1))-1)-(1<<(k-1))];
            if(minDis>temp){
                minDis=temp;
            }
        }
      /*  for(int i=0;i<n;i++){    //此部分可以输出看看形成的d[][]矩阵，便于理解执行过程
            for(int j=0;j<1<<(n-1);j++){
                cout<<d[i][j]<<"  ";
            }
            cout<<endl;
        } */
        d[0][(1<<(n-1))-1]=minDis;
        cout<<d[0][(1<<(n-1))-1];


    return 0;
}

---

关键问题总结

1.最重要的就是矩阵d[i][j]表示的含义，j是用二进制代码表示城市是否在集合中，0表示不在，1表示在，这里需要好好看书以及网站博客理解j的含义，前人资料很丰富，就是有些难以理解。
2.子集如何表示？利用二进制位表示
3.移位运算符<<优先级很低，一定要加括号
4.循环的时候要注意先后，j在i的循环外层，这是由于temp=dis[i][k]+d[k][j-(1<<(k-1))];这句，需要把d[i][j]里j表示的小集合算好了，才能继续算j表示的大集合

如上图，j大的需要把j小的先算出来，不然就是数组中为初始化的垃圾数据

参考文章

参考代码
参考图解
oj