算法 _【实验 5.2】1- 深度优先搜索暴力求解旅行商问题

2022-10-12
湖南
本文字数：1414 字
阅读完需：约 5 分钟

使用深度优先搜索暴力求解旅行商问题

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 51 2 51 3 31 4 42 3 72 4 6*/

复制代码

4.运行结果

5.算法分析

算法的时间复杂度在前面的题目描述中已经讲到了，达到了 $o (n!)$ 。

空间复杂度应为 $o (n^{2})$ ，因为使用了二维数组来存放城市间距离。

感谢阅读

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/a15acb4365e5f4331027d843b】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022-08-09 加入

编程一学生

发布

暂无评论

创作场景