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

这篇具有很好参考价值的文章主要介绍了算法 |【实验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年才能搜索完所有的解。

因此蛮力法只能解决小规模问题。

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

2.问题分析与算法设计思路

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

算法过程:

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

  2. 从城市 1 开始

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

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

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

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

小结:

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

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.2】1-深度优先搜索暴力求解旅行商问题

5.算法分析

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

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


感谢阅读

CSDN话题挑战赛第2期
参赛话题:学习笔记文章来源地址https://www.toymoban.com/news/detail-404040.html

到了这里,关于算法 |【实验5.2】1-深度优先搜索暴力求解旅行商问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 广度优先搜索(BFS)算法求解单源最短路径问题

      单源最短路径问题是图论中一类重要且常见的应用问题。在这个问题中,我们需要找到从一个给定源节点到其他节点的最短路径。广度优先搜索(BFS)算法是一种常用且有效的求解这一问题的算法。   本篇博客将重点讨论单源最短路径问题及其实际应用,同时简要介绍

    2024年02月13日
    浏览(46)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(78)
  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(50)
  • 深度优先搜索(DFS)算法

    目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 深度优先搜索(DFS)算法的思想是从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。具体而言,DFS算法使用栈数据结构来实现,

    2024年02月05日
    浏览(46)
  • 深度优先搜索算法

    目录 4.1 二叉树的最大深度(简单):深度优先搜索 4.2 对称二叉树(简单):递归 4.3 岛屿数量(中等):深度优先搜索 4.4 岛屿的最大面积(中等):深度优先搜索 4.5 路径总和(简单):深度优先搜索 4.6 被围绕的区域(中等):深度优先搜索 4.7 路径总和Ⅱ(中等):深

    2024年02月12日
    浏览(46)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(52)
  • 深度优先搜索算法C实现

    深度优先搜索 (DFS, Depth-First Search) 是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当达到树的末端时,它会回溯到树的前一个节点,直到找到未探索的路径。 下面是一个简单的深度优先搜索的C语言实现,这个实现是在一个无向图中进行的。在这

    2024年04月09日
    浏览(41)
  • 数据结构上机实验——图的实现(以无向邻接表为例)、图的深度优先搜索(DFS)、图的广度优先搜索(BFS)

      图采用邻接表存储结构,编程实现图的深度优先搜索和广度优先搜索算法。              2.1创建图 2.1.1定义图的顶点、边及类定义   我们定义一个 邻接表类(ALGraph) 。这里实现一些基础的数据结构。要注意结构体的嵌套。    Edge: 用于表示图中的边

    2024年02月04日
    浏览(54)
  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包