使用深度优先搜索暴力求解旅行商问题
1.题目描述
商品推销员要去n个城市推销商品，城市从1至n编号，任意两个城市间有一定距离，该推销员从城市1出发，需要经过所有城市并回到城市1，求最短总路径长度。
把旅行商问题看作一种排列问题，不难想出，这道题的蛮力做法即穷举所有路线。选定起点有n种选法，选定起点后的下一个目的地有(n- 1)种选择方法，再下一个是(n-2)……总共有n!种排列方法，算法复杂度达到O(n!)。
一个20城市的TSP问题有大约60,000,000,000,000,000个可能解。如果一台计算机每秒搜索1000个解，需要大约1902587年才能搜索完所有的解。
因此蛮力法只能解决小规模问题。
2.问题分析与算法设计思路
总体思路： 深度优先搜索，递归
算法过程：
使用二维数组 dis 存放任意两个城市之间的距离
从城市 1 开始
使用一个循环遍历下一个城市的不同选择，且忽略已经走过的城市、不能直接到达的城市
每次遍历，更新到达当前城市走过的路径长度 len 。
走过所有城市后，len 再加上当前城市到城市 1 的距离（最后要回到 1 ），保存该条路径的长度。
在所有路径长度中找出最小值。
小结：
“先规划好思路，然后才开始编写代码”，这句话很早就听到说过了，但是能真正静下心来做到这一点的时候，却是不多。但我感觉，这很有用。
3.算法实现
完整可运行代码，C++实现：
//深度优先搜索求解旅行商问题 #include<iostream> using namespace std; const int Max = 10; int len_min = 999;//最短总路径长度 int road[Max] = {1};//存放路径 int it_r = 1; //搜索求解 //参数dis:城市距离，now:所在城市，have:走过城市， //len:走过路径长度，n:城市总数，num:已走过城市数 void dfs(int dis[][Max], int now, bool have[], int len, int n, int num){ //显示路径 cout<<"road："; for(int i = 0; i < it_r; i++){ cout<<road[i]<<" "; } cout<<endl; //一条完整路径 if(num == n){ len += dis[now][1]; if(len < len_min){ len_min = len; } } //遍历下一个城市 for(int i = 2; i <= n; i++){ //排除已走过、不能到达的城市 if(have[i] == true || dis[now][i] == 0){ continue; } int len_next = len + dis[now][i]; have[i] = true; road[it_r++] = i; dfs(dis, i, have, len_next, n, num+1); road[--it_r] = 0; have[i] = false; } } int main(){ int dis[Max][Max] = {};//任意两城市距离，0表示不能直接到达 bool have[Max] = {1};//已走过哪些城市 int n = 0;//城市的个数 int e = 0;//道路的个数 cin>>n>>e; for(int i = 1; i <= e; i++){ int a = 0, b = 0, x = 0; cin>>a>>b>>x; dis[a][b] = x; dis[b][a] = x; } //显示城市距离 for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cout<<dis[i][j]<<" "; } cout<<endl; } dfs(dis, 1, have, 0, n, 1); cout<<"最短路径："<<len_min; return 0; } /* 测试数据一 4 5 1 2 5 1 3 3 1 4 4 2 3 7 2 4 6 */
4.运行结果
5.算法分析
算法的时间复杂度在前面的题目描述中已经讲到了，达到了o ( n ! ) o(n!)o(n!) 。
空间复杂度应为o ( n 2 ) o(n^2)o(n2)，因为使用了二维数组来存放城市间距离。
