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


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

    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.问题分析与算法设计思路

    总体思路: 深度优先搜索,递归

    算法过程:

    1. 使用二维数组 dis 存放任意两个城市之间的距离

    2. 从城市 1 开始

    3. 使用一个循环遍历下一个城市的不同选择,且忽略已经走过的城市、不能直接到达的城市

    4. 每次遍历,更新到达当前城市走过的路径长度 len 。

    5. 走过所有城市后,len 再加上当前城市到城市 1 的距离(最后要回到 1 ),保存该条路径的长度。

    6. 在所有路径长度中找出最小值。

    小结:

    “先规划好思路,然后才开始编写代码”,这句话很早就听到说过了,但是能真正静下心来做到这一点的时候,却是不多。但我感觉,这很有用。

    3.算法实现

    完整可运行代码,C++实现:

    //深度优先搜索求解旅行商问题
    #include
    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),因为使用了二维数组来存放城市间距离。


    感谢阅读

    CSDN话题挑战赛第2期
    参赛话题:学习笔记

  • 相关阅读:
    【linux基础(六)】Linux中的开发工具(中)--gcc/g++
    近期问题笔记20231116
    解决YYYY-MM-dd格式化日期获得的年份不正确问题
    MySQL之CRUD
    Qwt开发笔记(二):Qwt基础框架介绍、折线图介绍、折线图Demo以及代码详解
    代码随想录训练营 DP
    GeoServer源码运行(数据目录+数据库)
    应用聚类算法,预测中国足球在亚洲处于什么水平
    EasyCode全自动单表增删改查!
    MySQL 版本8.0.26在centos系统中安装的记录
  • 原文地址:https://blog.csdn.net/m0_63238256/article/details/127102979