首页 > 其他分享 >TSP问题-分支限界法求解

TSP问题-分支限界法求解

时间:2024-11-01 14:46:52浏览次数:3  
标签:langle 求解 城市 路径 限界 rangle 长度 代价 TSP

1. 货郎问题的分支限界算法求解 (10.4)

1.1. 货郎问题的定义

  • 给定一个城市集合 \(C = \{c_1, c_2, \dots, c_n\}\),任何两个城市之间都有距离 \(d\left(c_i, c_j\right)=d\left(c_j, c_i\right) \in \mathbf{Z}^{+}, 1 \leq i<j \leq n\)。
  • 目标: 找到一个城市的排列,使得从一个城市出发,访问每个城市恰好一次,并返回出发城市,总路径长度最短。

1.2. 算法设计

  • 解向量:
    解: \(1,2, \ldots, n\) 的排列 \(k_1, k_2, \ldots, k_n\) 使得:

\[\min \left\{\sum_{i=1}^{n-1} d\left(c_{k_i}, c_{k_{i+1}}\right)+d\left(c_{k_n}, c_{k_1}\right)\right\} \]

  • 搜索空间:
    排列树结构,每个结点 \(\langle i_1, i_2, \dots, i_k \rangle\) 表示前 \(k\) 步的路线已确定。

  • 约束条件:

    • 已走过的城市标号放入集合 \(B = \{i_1, i_2, \dots, i_k\}\)。
    • 下一步只能选择未访问过的城市:\(i_{k+1} \in \{2, \dots, n\} \setminus B\)。
    • 即每个节点只能访问一次

1.3. 代价函数与界的定义

  • 界 (Bound): 当前已找到的最短巡回路线的长度。

  • 代价函数:
    假设顶点 \(c_i\) 出发的最短边为 \(l_i\),\(d_j\) 为已选定的巡回路线中第 \(j\) 段的长度,则代价函数为:

\[\boldsymbol{L}=\sum_{j=1}^k \boldsymbol{d}_j+\boldsymbol{l}_{i_k}+\sum_{i_i \notin B} \boldsymbol{l}_{i_j} \]

  • 前半部分:已走过的路径长度。
  • 后半部分:剩余未访问的城市,从每个城市出发的最短边构成的下界。

1.4. 代价函数示例

代价函数实例

1.4. 代价函数示例

我们通过一个具体路径的代价函数计算示例,来更好理解分支限界算法中如何评估路径的代价和下界。

示例路径及红色路径描述

如图所示,我们假设货郎从 1号城市 出发,依次访问了 3号城市2号城市,形成了部分路径 \(\langle 1, 3, 2 \rangle\)。现在我们已经走到 2号城市,接下来需要计算该路径的代价函数,来评估当前路径的花费以及剩余部分的下界。

代价函数的计算公式

代价函数 \(L\) 的通用表达式如下:

\[L = \text{已走过的路径长度} + \text{剩余部分的估计长度下界} \]

  • 已走过的路径长度:
    将已访问的城市之间的路径距离累加,例如在路径 \(\langle 1, 3, 2 \rangle\) 中,

    \[1 \to 3:9 \,\, (单位) \]

    \[3 \to 2:13 \,\, (单位) \]

    已走过的路径总长度为:

    \[9 + 13 = 22 \,\, (单位) \]

  • 剩余部分的估计长度下界:

    • 当前停留在 2号城市,我们需要从 2号城市出发选择一条最短边。
      2号城市的最短边是 \(2 \to 4\),边长为 \(2\)。
    • 在剩余的未访问城市中,还未访问的城市是 4号城市。从 4号城市出发的最短边也是 \(4 \to 2\),长度同样为 \(2\)。

因此,剩余部分的估计长度下界为:

\[2 + 2 = 4 \,\, (单位) \]

完整代价函数值计算

将已走过的路径长度和剩余部分的下界相加,得到代价函数的值:

\[L = 22 + 4 = 26 \,\, (单位) \]

下界解释

这个代价函数的结果表明,无论之后如何规划剩余的路径,完整路径的总长度不会小于 26。这个下界帮助算法在搜索时进行剪枝,即当其他路径的代价超过该下界时,就不再继续深入搜索该分支。

1.5. 搜索树结构

搜索树及其结构

  • 初始结点: 从城市 1 出发。

  • 可选路径:

    • 第一层:1 号城市之后可以去 2、3、4。
    • 第二层:假设选择了 2 号城市,则下一步可选 3 或 4。
  • 深度优先遍历:

    • 第一条路径:\(\langle 1, 2, 3, 4, 1 \rangle\),长度 \(29\)。

      • 这是第一个找到的巡回路线,界 \(B = 29\)。
    • 更新界:
      找到路径 \(\langle 1, 2, 4, 3, 1 \rangle\),长度 \(23\)。更新界 \(B = 23\)。

    • 剪枝:
      当搜索路径 \(\langle 1, 3, 2 \rangle\) 的代价函数值为 \(26\),大于当前界 \(B = 23\),停止搜索该分支。

1.6. 实例运行过程

  1. 初始路径:

    • 路径 \(\langle 1, 2, 3, 4, 1 \rangle\),长度为 \(29\)。
  2. 更新路径:

    • 找到更优路径 \(\langle 1, 2, 4, 3, 1 \rangle\),长度为 \(23\),更新界。
  3. 剪枝:

    • 代价函数值 \(F = 26\),停止该分支的搜索。
  4. 最优解:

    • 找到路径 \(\langle 1, 3, 4, 2, 1 \rangle\),长度 \(23\)。
      • 该路径与之前的最优解长度相同。

DFS

1.7. 算法分析

  • 搜索树的规模:

    • 树叶的个数为 \(O((n - 1)!)\)。
    • 每个叶片对应一条路径,每条路径有 \(n\) 个结点。
  • 时间复杂度:

    • 单个路径计算时间: \(O(n)\)。
    • 总时间复杂度: \(O(n!)\)。
    • 在最坏情况下,与蛮力算法的时间复杂度相同。
  • 实际性能:
    通过剪枝操作,大大减少了实际搜索空间,因此平均运行时间优于蛮力算法。

1.8. 小结

  • 货郎问题的分支限界算法:

    • 约束条件: 只能选择未访问过的城市。
    • 代价函数: 已走过的路径长度 + 未访问部分的长度下界。
  • 时间复杂度: \(O(n!)\),在最坏情况下与蛮力算法相同,但通过剪枝可显著提升平均性能。

标签:langle,求解,城市,路径,限界,rangle,长度,代价,TSP
From: https://www.cnblogs.com/cloud-ken/p/18520237

相关文章

  • ORB-SLAM2源码学习:ORBextractor.cc:IC_Angle 利用灰度质心法求解关键点方向角
    ORB特征点:特征点是由关键点和描述子两部分组成,关键点是指特征点在图像中的位置,描述子是用来描述关键点周围的像素信息。ORB关键点是在FAST关键点的基础上进行改进给像素增加了一个主方向,称为OrientedFAST。描述子在BRIEF的基础上加入了上述的方向信息,称为SteeredBRIEF。FAS......
  • zlmediakit源码学习(深入解析RTSP拉流)
    一、知其然更要知其所以然!花费了几天时间,对ZLM的源码再进行一次研究学习。通过梳理RTSP拉流过程,加深对ZLM架构的了解。二、业务流程: 三、完整代码剖析:1.WebApi.cpp。在installWebApi中注册拉流代理接口:addStreamProxy()。1)检查是否已经存在;2)创建拉流代理;3)设置超时重试、拉流......
  • Django设置跨域请求解决方案
    Django设置跨域请求解决方案在现代Web开发中,跨域资源共享(CORS,Cross-OriginResourceSharing)是一个常见的需求。尤其是在前后端分离的开发模式下,Django作为后端框架,常常需要处理来自不同源的请求。本文将详细介绍如何在Django中设置跨域请求的解决方案,帮助开发者有效管理跨域请求......
  • 最大团问题-分支限界法求解
    此为课题组所指导本科生和低年级硕士生学习组合优化问题汇报所用教材:北京大学屈婉玲教授《算法设计与分析》课程资料:https://www.icourse163.org/course/PKU-1002525003承诺不用于任何商业用途,仅用于学术交流和分享更多内容请关注许志伟课题组官方中文主页:https://JaywayXu.g......
  • TetSphere Splatting——非常粗糙的阅读笔记分享,欢迎讨论~
       源代码主页:gmh14/tssplat:TetSphereSplatting:RepresentingHigh-QualityGeometrywithLagrangianVolumetricMeshes原文地址:[2405.20283]TetSphereSplatting:RepresentingHigh-QualityGeometrywithLagrangianVolumetricMeshes  与NeRF类似,DMTet......
  • Setting up a mobile hotspot on your Samsung Galaxy phone is straightforward
    SettingupamobilehotspotonyourSamsungGalaxyphoneisstraightforward.Herearethesteps:OpenSettings:Swipedownfromthetopofthescreentoopenthenotificationshade,thentapthegearicontoaccessSettings.Connections:TaponConnec......
  • ArkTS 的内存空间详解:从 SemiSpace 到 HugeObjectSpace
    本文旨在深入探讨华为鸿蒙HarmonyOSNext系统(截止目前API12)的技术细节,基于实际开发实践进行总结。主要作为技术分享与交流载体,难免错漏,欢迎各位同仁提出宝贵意见和问题,以便共同进步。本文为原创内容,任何形式的转载必须注明出处及原作者。引言ArkTS作为鸿蒙系统的开发语言,提......
  • 基于ACO蚁群优化的VRPSD问题求解matlab仿真,输出规划路径结果和满载率
    1.程序功能描述基于ACO蚁群优化的VRPSD问题求解matlab仿真,输出ACO优化的收敛曲线,规划路径结果和每一条路径的满载率。2.测试软件版本以及运行结果展示MATLAB2022a版本运行3.核心程序fori=1:Iterationiis_best=0;forj=1:Npop%蚂蚁搜索一次......
  • C# SuperSocket 基础七【CountSpliterReceiveFilte-固定数量分隔符协议】不使用COMMAN
    publicclassCountSpliterReceiveFilterSession:AppSession<CountSpliterReceiveFilterSession>{publicoverridevoidSend(stringmessage){Console.WriteLine("发送消息:"+message);base.Send(message)......
  • C# SuperSocket 基础六【CountSpliterReceiveFilte-固定数量分隔符协议】使用COMMAND
    publicclassCountSpliterReceiveFilterSession:AppSession<CountSpliterReceiveFilterSession>{publicoverridevoidSend(stringmessage){Console.WriteLine("发送消息:"+message);base.Send(message)......