c++ 旅行商问题（动态规划）

一、旅行商问题简介

旅行商问题

TSP，即旅行商问题，又称TSP问题（Traveling Salesman
Problem），是数学领域中著名问题之一。

问题概述

假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个NPC问题。

问题由来

TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。

TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。

示例：
在这里插入图片描述

黑色数字代表点、红色代表路径的花费

输入：

输出：

运行中...最短距离为：7
共2条最短路径：
路径1：1-->4-->3-->2-->1
路径2：1-->2-->3-->4-->1

提示：

第一行输入点的个数n和边的个数m,点的编号为1~n
接下来m行输入m条边以及花费,p1 p2 v,表示点p1和点p2之间有一条无向边，边的花费为v

二、基本思路

1、我们需要知道，我们求的路径是一个环，所以无论从哪里开始，结果都应该是一样的，就像例题中的;
最短路径可表示为 1–>4–>3–>2–>1
那么它也可以表示为 4–>3–>2–>1–>4
还可以表示为 3–>2–>1–>4–>3

所以我们可以从任意的点出发去查找路径

2、旅行商问题只有当图是哈密顿图时才可能有解的，即需要满足题意，可以从一个点出发，到达所有的点一次，然后回到起点。

这个可以通过最后运行的结果判断，我们令初始答案是一个很大的值，如果查找后答案没有被改变，则该图无解

3、按照传统的暴力搜索，时间复杂度为O(n!)，而动态规划可以将复杂度减低到O(n²*2ⁿ)

4、有个注意的点，起点需要走两遍，为了简化问题，只需要预处理从起点走到其它点的最小花费，而起点不能标记为已经走过，因为后面还有回到原点

三、实现

1、状态压缩

我们需要表达我们已经走过了哪些点，目前到达了哪里，有什么办法表达出来呢？

暴力是万能的，我们可以开一个数组dp[i][j]，代表目前到达了i点，dp[i][j]的值代表j点是否已经走过了，但是这样做的话我们状态转移会变得很麻烦，状态压缩就是它的优化

状态压缩是通过二进制实现的，我们知道int有32位，那么我们可以用第0位代表第0个点的状态，第1位代表第1个点状态…第n位代表第n个点的状态，位的值如果是1的话就代表该点已经走过了，例如17的二进制为0000010001，代表第0个点和第4个点已经走过了

那么我们可以开一个数组dp[i][j]，代表目前走到了i点，用j代表已经哪些点，例如：
dp[0][17],17的二进制为0000010001,代表目前在第0个点，已经走过第0个点和第4个点。
dp[16][17]，17的二进制为0000010001,代表目前在第4个点，已经走过第0个点和第4个点。

我们可以用dp[i][j]的值代表当前这个状态的最小花费，例如dp[0][17]=12，那么就代表到达该状态需要的最小花费是12

2、状态转移

dp的基本思想就是记录某个状态的最优解，再从目前的状态转移到新的状态，从局部最优解转移到全局最优解

我们用数组a[i][j]存储图，那么a[i][j]的值就代表从i点到j点的花费

我们如何求状态dp[0][19]的最优解？
19的二进制是0000010011，因为18的二进制为0000010010，那么dp[0][19]可以由dp[4][18],dp[1][18]转移过来，最小花费是dp[0][19]=min(dp[4][18]+a[4][0],dp[1][18]+a[1][0])

即我们要求大的状态，那么就需要先把小状态最优解求出来。反过来我们求出了所有小状态，那么就可以求出大状态的最优解

在这里插入图片描述

{1，2，3}代表第1、2、3个点都已经走过了

可以发现，小状态总是比大状态小的，那么我们可以从0状态枚举到2ⁿ-1状态，获取到每个状态的最优解

我们还可以反过来想，从小状态去更新大的状态
在这里插入图片描述
两种思路都可以

四、代码

下面代码是基于逆向思想的，即从小状态更新大状态。理解透了的同学不妨尝试写一下大状态调用小状态更新的代码

#include<bits/stdc++.h>
using namespace std;
int n,m;//n点的个数，m边的个数 
int a[15][15];//邻接矩阵存无向图 
int dp[15][1<<15];//dp[i][j]代表从最后走到i点到达状态j 
int t;//一共有t个状态 void init(){//初始化 memset(a,0x3f,sizeof a);memset(dp,0x3f,sizeof dp);cout<<"请输入点和边的个数："<<endl;cin>>n>>m;cout<<"请输入"<<m<<"条边："<<endl;for(int i=0;i<m;i++){int x,y,val; cin>>x>>y>>val;x--;y--;a[x][y]=val;a[y][x]=val;}
} void run(){//dp核心算法 t=(1<<n);for(int i=1;i<n;i++){//因为起点初始不能被标记已经走过,所以需要手动初始化起点到达其它点的花费 dp[i][1<<i]=a[0][i];}for(int i=0;i<t;i++){//枚举每一个状态 for(int j=0;j<n;j++){//枚举每一个没有走过的点 if(((i>>j)&1)==0){for(int k=0;k<n;k++){//枚举每一个走过的点 if(((i>>k)&1)==1&&dp[j][i^(1<<j)]>dp[k][i]+a[k][j]){//取最优状态 dp[j][i^(1<<j)]=dp[k][i]+a[k][j];}}}}}
}int tt;//记录 
vector<int> path(1,0);//初始化从0点出发 ,存储单条路径 
vector<vector<int> > paths;//存储所有的路径 
void getPath(int p){//递归查找所有路径 if((tt^(1<<p))==0){//如果是最后一个点了就存储改路径 paths.push_back(path);return; }for(int j=1;j<n;j++){//回溯算法，一个加法的原则//如果点1到达点5的最短距离为100，点1到达点3的最短距离是70//而点3和点5之间的距离为30 ，那么点3是点1到5之间的一个中间点//即1-->...-->3-->5 if(a[j][p]+dp[j][tt^(1<<p)]==dp[p][tt]){tt^=(1<<p);path.push_back(j);getPath(j);tt^=(1<<p);path.pop_back();}}} void print(){//打印路径 cout<<"最短距离为："<<dp[0][t-1]<<endl;cout<<"共"<<paths.size()<<"条最短路径：" <<endl; for(int i=0;i<paths.size();i++){cout<<"路径"<<i+1<<"：1";for(int j=paths[i].size()-1;j>=0;j--){cout<<"-->"<<paths[i][j]+1;}cout<<endl;}
}int main(){init();cout<<"运行中..."<<endl<<endl; run(); cout<<"运行结果："<<endl; if(dp[0][t-1]==0x3f3f3f3f){//无解 cout<<"该图不是哈密顿图！"<<endl;return 0;}tt=t-1;getPath(0);print(); 
}