一、问题引入
TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。
假设现在有四个城市，0,1,2,3，他们之间的代价如图一，可以存成二维表的形式
现在要从城市0出发，最后又回到0，期间1，2，3都必须并且只能经过一次，使代价最小。
二、求解思路
1、动态规划思路
- 最优子结构（问题的最优解能够通过其子问题的最优解得到）
-
重叠子问题（问题有重叠，用备忘录记录减少时间复杂度）
从下往上构造备忘录（这里为一个压缩二维矩阵）
image.png
2、数据结构
- 备忘录（压缩二维矩阵）：d[MAX][1 << (MAX-1)]
求法：即利用上面的递归公式从下到上求解，具体见代码解释。 - 记录最优路线点矩阵（压缩二维矩阵）：route[MAX][1 << (MAX-1)]
求法：就是当利用递归公式求解出子问题最优值后，给备忘录赋值的同时，也给最优路线点矩阵赋选到的最优分割点的点序号。 - 其他结构：
dis[MAX][MAX]：距离地图表
p[MAX]：记录最优路线
3、求解中注意的地方
- 压缩矩阵的表示
例如4个城市{0,1,2,3}，{1,2,3}依次为{}，{1}，{2}，{1,2}，{3}，{1,3}，{2,3}，{1,2,3}，如果用111表示城市321，则上述子集转换成二进制为0，01，10，11，100,101,110,111，十进制恰好是0,1,2,3,4,5,6,7。虽然子集{1,2}在{3}之前，但遍历子集{1,2}的过程并不会使用过程矩阵中关于3的行列，因此不需要排序。 - 判断一个城市是否位于子集中
(1 << (i - 1))&j)：判断城市i是否在子集j中，为1则在，为0不在。 - 位运算符优先级小，记得加括号。
- 要想求得问题的最小代价，得在备忘录建立好后，再执行一次。
4、代码实现
#include <iostream>
#include <stdio.h>
#include<iomanip>
#define MAX 12
using namespace std;
int dis[MAX][MAX], d[MAX][1 << (MAX-1)];//距离地图表，d函数表,d[]为动态规划存储的城市经过矩阵
int route[MAX][1 << (MAX-1)];//记录最优路线点
int p[MAX];//记录最优路线
int main()
{
int n, temp,minDis,minPoint,count;
////给距离地图表赋值
cout<<"请输入城市个数：" ;
cin >> n;
cout<<"输入各城市之间的路程费用："<<endl ;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
scanf("%d", &dis[i][j]);
}
}
//给d函数表赋值
for (int i = 1; i<n; i++){ //将所有城市到第0个城市的路径初始化为两市间的距离
d[i][0] = dis[i][0];
route[i][0] = 0;
}
//给除了第0行以外的其余部分赋值
for (int j = 1; j<(1 <<(n-1)); j++){//j用二进制表示的城市集合,先说j再说i，动态规划从j的底层到上层，j数值越来越大
for (int i = 1; i<n; i++){
//i不在j表示的城市集合中，可以对d[i][j]赋值,否则赋0;
if (((1 << (i - 1))&j) == 0){
//temp=dis[i][k]+d[k][V-{k}]开始对V中所有的k进行遍历
int minDis = 60000;
for (int k = 1; k<n; k++){
if ((1 << (k - 1))&j) {//k表示的城市在j表示的城市集合中
temp = dis[i][k] + d[k][j - (1 << (k - 1))];
if (temp<minDis){//d(1,{2,3})=min{ C12+d(2,{3})||C13+d(3,{2})}
minDis = temp; //所有k中最小的距离
minPoint=k;
}
}
}
d[i][j] = minDis;//给d函数表每个位置赋值
// cout<< d[i][j]<<" ";
route[i][j]=minPoint;//从城市集j中选出minPoint点递归为最优
}
}
}
//对第0行最后一个d(0,{123})赋值，d(0,{1,2,3})=min {C01+d(1,{2,3})|| C02+d{2,{1,3}}||C03+d{3,{1,2}}）
minDis = 600;
for (int k = 1; k<n; k++){
temp = dis[0][k] + d[k][((1 << (n - 1)) - 1) - (1 << (k - 1))];//d[k][{123}-{k}]
if (minDis>temp){
minDis = temp;
minPoint=k;
}
}
d[0][(1 << (n - 1)) - 1] = minDis;//数组从零开始，所以-1
route[0][(1 << (n - 1)) - 1] = minPoint;
//此部分可以输出看看形成的d[][]矩阵，便于理解执行过程
for(int i=0;i<n;i++){
for(int j=0;j<(1<<(n-1));j++){
printf("%3d",d[i][j]);
}
cout<<endl;
}
cout <<"最小代价："<< d[0][(1 << (n - 1)) - 1]<<endl;
//求出最优路径p[12]
count=0;p[count++]=0;
int flat=(1 << (n - 1)) - 1;
do
{
temp=route[p[count-1]][flat];
p[count++]=temp;
flat-=(1<<(temp-1));
}
while(flat>0);//所有点都被查找过一遍，最后一次是空集0要先执行一遍(所以用do-while,记得加分号)
//打印最优路径
cout<<"最优路线：" ;
cout<<p[0];
for(int i=1;i<=n;i++)
{
cout<<"->"<<p[i];
}
return 0;
}
5、运行结果
6、计算过程
从0城市出发经城市1、2、3然后回到0城市的最短路径长度是：
d(0,{1, 2, 3})=min{c01+d(1, { 2, 3}), c02+d(2, {1, 3}), c03+d(3, {1, 2})}
这是最后一个阶段的决策，而：
d(1, {2, 3})=min{c12+d(2, {3}), c13+ d(3, {2})}
d(2, {1, 3})=min{c21+d(1, {3}), c23+ d(3, {1})}
d(3, {1, 2})=min{c31+d(1, {2}), c32+ d(2, {1})}
这一阶段的决策又依赖于下面的计算结果：
d(1, {2})= c12+d(2, {}) d(2, {3})=c23+d(3, {})
d(3, {2})= c32+d(2, {}) d(1, {3})= c13+d(3, {})
d(2, {1})=c21+d(1, {}) d(3, {1})=c31+d(1, {})
而下式可以直接获得（括号中是该决策引起的状态转移）：
d(1, {})=c10=5(1→0) d(2, {})=c20=6(2→0) d(3, {})=c30=3(3→0)
再向前倒推，有：
d(1, {2})= c12+d(2, {})=2+6=8(1→2) d(1, {3})= c13+d(3, {})=3+3=6(1→3)
d(2, {3})= c23+d(3, {})=2+3=5(2→3) d(2, {1})= c21+d(1, {})=4+5=9(2→1)
d(3, {1})= c31+d(1, {})=7+5=12(3→1) d(3, {2})= c32+d(2, {})=5+6=11(3→2)
再向前倒退，有：
d(1, {2, 3})= min{c12+d(2, {3}), c13+ d(3, {2})}=min{2+5, 3+11}=7(1→2)
d(2, {1, 3})=min{c21+d(1, {3}), c23+ d(3, {1})}=min{4+6, 2+12}=10(2→1)
d(3, {1, 2})=min{c31+d(1, {2}), c32+ d(2, {1})}=min{7+8, 5+9}=14(3→2)
最后有：
d(0, {1, 2, 3})=min{c01+ d(1, { 2, 3}), c02+ d(2, {1, 3}), c03+ d(3, {1, 2})}
=min{3+7, 6+10, 7+14}=10(0→1)
所以，从顶点0出发的TSP问题的最短路径长度为10，路径是0→1→2→3→0。
