旅行商问题(回溯算法)

这篇具有很好参考价值的文章主要介绍了旅行商问题(回溯算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

回溯问题适合于解由向量的形式来构成的,这个向量空间中使用搜索的方法进行搜索,搜索使用宽度优先的方法。货郎问题又名旅行商问题,但其实更多教科书中更通用的叫法叫旅行商问题,下面来对旅行商问题使用回溯算法证明。

一、问题描述

有n个城市,已知任两个城市之间的距离,求一条每个城市恰好经过一次的回路,使得总长度最小 。

分析:
有n个城市,城市与城市之前有距离的,任意两个城市之间的距离是已知的,现在需要找一条回路,经过每一个城市1次,使得总长度最小,就相当于这个货郎在路途,或者旅行商的行路,遍历所有的城市去各个城市走一趟,但是城市不能重复,所以怎么走下来才能够使得总长度达到最小。

其实相当于把这些城市做一个排列,第一个城市指向k1所指向的城市,由城市k1走向城市k2,一直往下走,走到kn以后再回到k1形成一个闭环

二、数学建模

旅行商问题(回溯算法)

旅行商问题(回溯算法)
数学表达式中的C k1到C k2,这两个城市的距离用d来表示,走到最后一个城市再倒回来(从C kn到C k1),这个距离达到最小,就是我们要做的事情。

这个问题是有选择的,一定程度上讲,TSP也是优化问题,只要是涉及到有选择,选择的不同导致结果的不同,结果的不同要想法设法找出最好的选择,不管是调度问题、背包的装法问题还是这个城市排列的问题,现代的智能优化算法不再使用精确的解,而是找到一个近似最精确的解就可以了。

三、实例

旅行商问题(回溯算法)

1、传统经典做法

从第1个城市走到第2个城市,从第2个城市走到第4个城市,从第4个城市到第3个城市然后再回来。

C={1,2,3,4}
d(1,2)=5, d(1,3)=9,
d(1,4)=4, d(2,3)=13,
d(2,4)=2, d(3,4)=7

解:< 1,2,4,3 > ,
长度= 5 + 2 + 7 + 9 = 23

这是其中一个解,最后的解得到的是城市的排列向量,上面原始的数据每两个城市之间的距离都是给出的。

2、回溯算法

假定每个城市都有连接,回溯算法的实现也是一种搜索,首先对于第一个城市出发,第1个城市和2,3,4城市相连,这个时候做选择,选择任何一条路径往下走,走到第2个城市,又有两种选择:到第4个城市,或者到第3个城市。每走到一个城市就选相当于前面已经走过的城市就不用再选择了,就从剩下的城市中去选。

一开始选定任何一个出发点出发,接下来又n-1个城市可以去选择,当你走到任何一个点之后,接下来又有n-2个城市可以去选择,……一直到最后只有1种选择,就是唯一的选择:回去。所以总的路径有(n-1)!种,每到叶结点的路径就是城市间的路径。

表示为树,称之为排列树,有(n-1)!片树叶

其实我们要找的就是在所有的排列树叶结点中去找最小的那个,所以搜索空间是相当大的。

旅行商问题(回溯算法)文章来源地址https://www.toymoban.com/news/detail-461482.html

四、总结

  • 解:向量
  • 搜索空间:树,可能是n叉树、子集树、排列树等等,树的结点对应于部分向量,可行解在叶结点
  • 搜索方法:深度优先, 宽度优先, …
    跳越式遍历搜索树,找到解

到了这里,关于旅行商问题(回溯算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 遗传算法解决旅行商问题

    一、问题描述 旅行商问题(Travelling Salesman Problem, 简记TSP,亦称货郎担问题):设有n个城市和距离矩阵D=[dij],其中dij表示城市i到城市j的距离,i,j=1,2 … n,则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。 初始问题图像如下: 近似理想结果图像如

    2024年02月07日
    浏览(44)
  • 旅行商问题 python 不同算法实现

    一个网络上的最优路线问题,它寻求货郎走过网络上的所有点的路线最短。 定义: 输入 : 有穷个城市的集合 C = { c 1 , c 2 , . . . , c n } , 距 离 d ( c i , c j ) = d ( c j , c i ) ∈ Z + , 1 ≤ i j ≤ n C={c_1,c_2,...,c_n},距离d(c_i,c_j)=d(c_j,c_i)in Z^+,1 le i j le n C = { c 1 ​ , c 2 ​ , . . . , c n ​

    2024年02月06日
    浏览(34)
  • 关于旅行商问题的多种算法求解

    一、问题描述 旅行商问题是指旅行家要旅行n个城市,要求每个城市经历一次且仅经历一次然后回到出发城市,并要求所走路程最短。 首先通过所给出的一个无向图,即n个顶点,m个无向边,每条边有一个权值代表两个点之间的距离,要求把每一个点都走一遍并回到原点,求

    2024年02月04日
    浏览(45)
  • Matlab蚁群算法求解旅行商问题

    目录 问题展现 解决代码 代码1 输出结果 代码2 输出结果 代码3 输出结果 假设有一个旅行商人要拜访全国 31 个省会城市,他需要选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择要求是:所选路径的路程为所有路径之中的

    2023年04月15日
    浏览(57)
  • 整数规划——分支界定算法(旅行商问题,规约矩阵求解)

    一、普通优化问题分枝定界求解 题目的原问题为   在计算过程中,利用MATLAB中的linprog()函数进行求解最优解,具体的计算步骤如下: A为约束系数矩阵,B为等式右边向量,C为目标函数的系数向量。   进行第一次最优求解以A=[2 9;11 -8],B=[40;82],C=[-3,-13]利用linprog函数求解。解

    2024年02月16日
    浏览(37)
  • 遗传算法求解旅行商问题(含python源代码)

    目录 前言 编码初始化种群 计算适应度 选择 交叉 变异 完整代码 总结 这次的算法有一点不能确定是否正确,希望有大佬能够批评指正。 遗传算法的一般步骤 种群(population) 指同一时间生活在一定自然区域内,同种生物的所有个体。 所以种群是由个体组成的,所以先需要

    2024年01月23日
    浏览(66)
  • 算法 |【实验5.2】1-深度优先搜索暴力求解旅行商问题

    商品推销员要去n个城市推销商品,城市从1至n编号,任意两个城市间有一定距离,该推销员从城市1出发,需要经过所有城市并回到城市1,求最短总路径长度。 把旅行商问题看作一种排列问题,不难想出,这道题的蛮力做法即穷举所有路线。选定起点有n种选法,选定起点后的

    2023年04月08日
    浏览(70)
  • 量子退火算法入门(4):旅行商问题的QUBO建模「上篇」

    旅行商问题,是一个经典的组合优化问题,而且是著名NP问题之一。如下图所示 ,可以想象,有A,B,C,D,E 五个地点,我们想找到一条路径,从地点A出发,经过剩余四个地点,然后回到地点A,从所有可能路径中找到距离最短的一条路径。本章借用了文献[*1]的图表。 最简单

    2023年04月18日
    浏览(36)
  • Baltamatica 北太天元 —— 基于模拟退火算法的旅行商问题

    北太天元(Baltam)是一款对标矩阵实验室(Matlab)的国产通用科学计算软件,目前版本还在持续更新迭代中,并在国内不断提升知名度,营造良好的生态社区氛围。在很多外行、内行人都不看好Matlab国产化,甚至面对工业软件国产化的项目“谈虎色变”的形势下,北太天元横

    2024年02月11日
    浏览(58)
  • 基于TSP(旅行商)问题的混合粒子群算法 附直接运行代码

    如果对粒子群一点都不知道的可以看看上文标准粒子群算法, 想看代码的直接去下面1.4标题 即可 链接:(105条消息) 自己对粒子群算法的理解(附matlab直接运行代码)(二维)_吕浩轩的博客-CSDN博客_二维粒子群算法​​​​​​h 好现在开始正文: 标准粒子群通过追随个体极值和

    2023年04月16日
    浏览(74)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包