当前位置: 首页 > news >正文

运筹系列83:使用分枝定界求解tsp问题

1. 辅助函数

Node算子用来存储搜索树的状态。其中level等于path的长度,path是当前节点已经访问过的vertex清单,bound则是当前的lb。
这里的bound函数是一种启发式方法,等于当前路径的总长度,再加上往后走两步的最小值。

struct Nodelevel::Intpath::Vector{Int64} bound::Int
endfunction totaldist(adj_mat::Array{Int64,2},t::Vector{Int64} )n = length(t)sum([adj_mat[t[i],t[i+1]] for i in 1:n-1])+adj_mat[t[n],t[1]] 
endfunction bound(adj_mat::Array{Int64,2}, path::Vector{Int64} )_bound = 0n = size(adj_mat)[1]determined, last = path[1:end-1], path[end]remain = setdiff(1:n,path)for i in 1:length(path)-1;_bound += adj_mat[path[i],path[i + 1]];end_bound += minimum([adj_mat[last,i] for i in remain])p = [path[1];remain]for r in remain_bound+=minimum([adj_mat[r,i] for i in setdiff(p,r)])endreturn _bound
end;

2. 分枝定界代码

这里用priorityQueue存储节点,用Queue也是一样的。
分枝条件为bound<ub,往下搜索所有没有探访过的节点,使用函数setdiff(1:n,v.path)。当然这里可以尝试将搜索范围缩小,比如仅搜索最近的一些节点,不过就不保证最优性了。
当搜索到level==n-1时,获得一个可行解,并且停止往下探索。此时如果路径长度比ub还短,则更新ub。

function solve(adj_mat::Array{Int64,2},ub::Int64 = 10^9)optimal_tour = Vector{Int64}()optimal_length = 0n = size(adj_mat)[1]PQ = PriorityQueue{Node,Int}()path = Vector{Int64}([1])v = Node(1,path,bound(adj_mat,path))enqueue!(PQ,v,v.bound) while length(PQ)>0v = dequeue!(PQ)if v.bound<ublevel = v.level+1b = 0for i in setdiff(1:n,v.path)path = [v.path;i]if level==n-1 #终止条件push!(path,setdiff(1:n,path)[1])_len = totaldist(adj_mat,path)if _len < ubub = _lenoptimal_length = _lenoptimal_tour = pathendelse # 进行分叉b = bound(adj_mat,path)if b < ub # 分枝条件enqueue!(PQ,Node(level,path,b),b)endendendendendoptimal_tour,optimal_length
end
solve([0 14 4 10 20;14 0 7  8  7;4  5  0  7  16;11 7 9 0 2;18 7 17 4 0])

输出([1, 4, 5, 2, 3], 30)。
TSP时一个NPhard问题,当点数增多时,使用b&b的算法性能会急速下降。

相关文章:

运筹系列83:使用分枝定界求解tsp问题

1. 辅助函数 Node算子用来存储搜索树的状态。其中level等于path的长度&#xff0c;path是当前节点已经访问过的vertex清单&#xff0c;bound则是当前的lb。 这里的bound函数是一种启发式方法&#xff0c;等于当前路径的总长度&#xff0c;再加上往后走两步的最小值。 struct …...

linux 指令 第3期

cat cat 指令&#xff1a; 首先我们知道一个文件内容属性 我们对文件操作就有两个方面&#xff1a;对文件内容和属性的操作 扩展&#xff1a;echo 指令 直接打印echo后面跟的字符串 看&#xff1a; 这其实是把它打印到了显示器上&#xff0c;我们也可以改变一下它的打印位置…...

测试用例实战

测试用例实战 三角形判断 三角形测试用例设计 测试用例编写 先做正向数据&#xff0c;再做反向数据。 只要有一条边长为0&#xff0c;那就是不符合要求&#xff0c;不需要再进行判断&#xff0c;重复。 四边形 四边形测试用例...

Unity XML1——XML基本语法

一、XML 概述 ​ 全称&#xff1a;可拓展标记语言&#xff08;EXtensible Markup Language&#xff09; ​ XML 是国际通用的&#xff0c;它是被设计来用于传输和存储数据的一种文本特殊格式&#xff0c;文件后缀一般为 .xml ​ 我们在游戏中可以把游戏数据按照 XML 的格式标…...

了解Unity编辑器之组件篇Playables和Rendering(十)

Playables 一、Playable Director&#xff1a;是一种用于控制和管理剧情、动画和音频的工具。它作为一个中央控制器&#xff0c;可以管理播放动画剧情、视频剧情和音频剧情&#xff0c;以及它们之间的时间、顺序和交互。 Playable Director组件具有以下作用&#xff1a; 剧情控…...

python的包管理器pip安装经常失败的解决办法:修改pip镜像源

pip 常用的国内镜像源&#xff1a; https://pypi.tuna.tsinghua.edu.cn/simple/ // 清华 http://mirrors.aliyun.com/pypi/simple/ // 阿里云 https://pypi.mirrors.ustc.edu.cn/simple/ // 中国科技大学 http://pypi.hustunique.com/ // 华中理…...

忘记安卓图案/密码锁如何解锁?

如何解锁Android手机图案锁&#xff1f;如何删除忘记的密码&#xff1f;Android 手机锁定后如何重置&#xff1f;这是许多智能手机用户在网上提出的几个问题。为了回答这些问题&#xff0c;我们想出了一些简单有效的方法来解锁任何设备而不丢失数据。 忘记手机密码可能会令人恐…...

Bash编程

目录&#xff1a; bash编程语法bash脚本编写 1.bash编程语法 Bash 编程基础 变量引号数组控制语句函数 Bash 变量 语法&#xff1a; Variable_namevalue Bash 变量定义的规则 变量名区分大小写&#xff0c;a和A为两个不同的变量。变量名可以使用大小写字母混编的形式进行…...

vue指令-v-model修饰符

vue指令-v-model修饰符 1、目标2、语法 1、目标 让v-modelv-mode拥有更强大的功能 2、语法 v-model.修饰符“Vue数据变量” .number 以parseFloat转成数字类型 .trime 去除首位空白字符 .lazy 在change时触发而非input时示例1 <template><div id"app"&g…...

【论文精读CVPR_2023】3D-Aware Face Swapping

【论文精读CVPR_2023】3D-Aware Face Swapping 前言Abstract1. Introduction2. Related WorkFace Swapping.3D-Aware Generative Models.GAN Inversion.3. Method3.1. Overview3.2. Inferring 3D Prior from 2D Images3.3. Face Swapping via Latent Code Manipulation3.4. Joi…...

flutter开发实战-自定义相机camera功能

flutter开发实战-自定义相机camera功能。 Flutter 本质上只是一个 UI 框架&#xff0c;运行在宿主平台之上&#xff0c;Flutter 本身是无法提供一些系统能力&#xff0c;比如使用蓝牙、相机、GPS等&#xff0c;因此要在 Flutter 中调用这些能力就必须和原生平台进行通信。 实现…...

重排链表——力扣143

文章目录 题目描述法一&#xff1a;寻找链表中点、链表逆序、链表合并 题目描述 法一&#xff1a;寻找链表中点、链表逆序、链表合并 void reorderList(ListNode* head){if(headnullptr){return;}// 找到中点 ListNode* mid FindMiddle(head);ListNode *h1head, *h2mid->ne…...

Lambda表达式常见的Local variable must be final or effectively final原因及解决办法

目录 Local variable must be final or effectively final错误原因 解决办法按照要求定义为final&#xff08;不符合实情&#xff0c;很多时候是查库获取的变量值&#xff09;使用原子类存储变量&#xff0c;保证一致性AtomicReference常用原子类 其它 Local variable must be …...

YOLOv5改进系列(16)——添加EMA注意力机制(ICASSP2023|实测涨点)

【YOLOv5改进系列】前期回顾: YOLOv5改进系列(0)——重要性能指标与训练结果评价及分析 YOLOv5改进系列(1)——添加SE注意力机制 YOLOv5改进系列(2)——添加...

[SSM]GoF之代理模式

目录 十四、GoF之代理模式 14.1对代理模式的理解 14.2静态代理 14.3动态代理 14.3.1JDK动态代理 14.3.2CGLIB动态代理 十四、GoF之代理模式 14.1对代理模式的理解 场景&#xff1a;拍电影的时候&#xff0c;替身演员去代理演员完成表演。这就是一个代理模式。 演员为什…...

桥梁安全生命周期监测解决方案

一、方案背景 建筑安全是人们生产、经营、居住等经济生活和人身安全的基本保证&#xff0c;目前我国越来越多的建筑物逐 步接近或者已经达到了使用年限&#xff0c;使得建筑物不断出现各种安全隐患&#xff0c;对居民的人身安全和财产安全产 生不利影响&#xff0c;因此房…...

图技术在 LLM 下的应用:知识图谱驱动的大语言模型 Llama Index

LLM 如火如荼地发展了大半年&#xff0c;各类大模型和相关框架也逐步成型&#xff0c;可被大家应用到业务实际中。在这个过程中&#xff0c;我们可能会遇到一类问题是&#xff1a;现有的哪些数据&#xff0c;如何更好地与 LLM 对接上。像是大家都在用的知识图谱&#xff0c;现在…...

SpringBoot自动配置、启动器原理爆肝解析(干货满满)

文章目录 前言一、SpringBoot优势概要二、SpringBoot自动配置1. ☠注意☠2.自动配置详解 三、Starter&#xff08;场景启动器&#xff09;原理总结 前言 本文详细解析面试重点—SpringBoot自动配置原理、场景启动器原理&#xff0c;深入源码&#xff0c;直接上干货、绝不拖泥带…...

chrome扩展控制popup页面动态切换

文章目录 1、通过控制元素的显示隐藏达到popup页面切换的效果2、通过监听页面重新加载完成不同popup的切换3、直接修改popup页面location.href&#xff0c;无需刷新页面 1、通过控制元素的显示隐藏达到popup页面切换的效果 下面在mv2版本的API下完成 实际上通过控制页面元素实…...

【AI】《动手学-深度学习-PyTorch版》笔记(三):PyTorch常用函数

AI学习目录汇总 1、torch.arange 返回一维张量(一维数组),官网说明,常见的三种用法如下 输入:torch.arange(5) 输出:tensor([0, 1, 2, 3, 4]) 输入:torch.arange(5, 16) 输出:tensor([ 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]) 输入:torch.arange(1, 25, 2) …...

某文化馆三维建模模型-glb格式-三维漫游-室内导航测试

资源描述 某文化馆某个楼层的三维建模模型&#xff0c;glb格式&#xff0c;适用于three.js开发&#xff0c;可用来做一些三维室内漫游测试和室内导航测试 资源下载地址...

网络安全 Day19-计算机网络基础知识04(网络协议)

计算机网络基础知识04&#xff08;网络协议&#xff09; 1. ARP1.1 ARP通讯原理1.2 arp欺骗1.3 ARP欺骗与预防1.4 排查ARP病毒 2. DHCP工作原理&#xff08;自动分配内网IP&#xff09;3. TCP协议三次握手、四次挥手原理4. DNS协议工作原理 1. ARP Linux查看arp&#xff1a;ar…...

Verilog语法学习——LV5_位拆分与运算

LV5_位拆分与运算 题目来源于牛客网 [牛客网在线编程_Verilog篇_Verilog快速入门 (nowcoder.com)](https://www.nowcoder.com/exam/oj?page1&tabVerilog篇&topicId301) 题目 题目描述&#xff1a; 现在输入了一个压缩的16位数据&#xff0c;其实际上包含了四个数据…...

❤️创意网页:创意动态画布~缤纷移动涂鸦~图片彩色打码

✨博主&#xff1a;命运之光 &#x1f338;专栏&#xff1a;Python星辰秘典 &#x1f433;专栏&#xff1a;web开发&#xff08;简单好用又好看&#xff09; ❤️专栏&#xff1a;Java经典程序设计 ☀️博主的其他文章&#xff1a;点击进入博主的主页 前言&#xff1a;欢迎踏入…...

数值分析第六章节 用Python实现解线性方程组的迭代法

参考书籍&#xff1a;数值分析 第五版 李庆杨 王能超 易大义编 第5章 解线性方程组的迭代法 文章声明&#xff1a;如有发现错误&#xff0c;欢迎批评指正 文章目录 迭代法的基本概念雅可比迭代法与高斯-塞格尔迭代法雅可比迭代法高斯-塞格尔迭代法 迭代法的基本概念 6.1.1引言…...

【低代码专题方案】使用iPaaS平台下发数据,快捷集成MDM类型系统

01 场景背景 伴随着企业信息化建设日趋完善化、体系化&#xff0c;使用的应用系统越来越多&#xff0c;业务发展中沉淀了大量数据。主数据作为数据治理中枢&#xff0c;保存大量标准数据库&#xff0c;如何把庞大的数据下发到各个业务系统成了很棘手的问题。 传统的数据下发方…...

驱动开发 day3 (模块化驱动启动led,蜂鸣器,风扇,震动马达)

模块化驱动启动led,蜂鸣器,风扇,震动马达并加上Makefile 封装模块化驱动&#xff0c;可自由安装卸载驱动&#xff0c;便于驱动更新(附图) 1.安装模块驱动同时初始化各个设备并使能 2.该驱动会自动创建驱动节点. 3.通过c函数程序输入控制各个设备 4.卸载模块驱动 //编译驱动…...

数据结构与算法基础-学习-27-图之最短路径之Dijkstra(迪杰斯特拉)算法

一、最短路径应用案例 例如从北京到上海旅游&#xff0c;有多条路可以到目的地&#xff0c;哪条路线最短&#xff0c;哪条路线最省钱&#xff0c;就是典型的最短路径问题。 二、最短路径问题分类 最短路径问题可以分为两类&#xff0c;第一类为&#xff1a;两点间最短路径。第…...

Windows Server 2012 能使用的playwright版本

由于在harkua_bot里面使用到了playwright&#xff0c;我的服务器又是Windows Server 2012 R2&#xff0c;最新版playwright不支持Windows Server 2012 R2&#xff0c;支持Windows Server 2016以上&#xff0c;所以有了这个需求 https://cdn.npmmirror.com/binaries/playwright…...

css实现溢出变为省略号

单行文本溢出省略 text-overflow&#xff1a;规定当文本溢出时&#xff0c;显示省略符号来代表被修剪的文本 white-space&#xff1a;设置文字在一行显示&#xff0c;不能换行 overflow&#xff1a;文字长度超出限定宽度&#xff0c;则隐藏超出的内容overflow设为hidden&#…...