通俗理解LKH-3算法

LKH-3(Lin-Kernighan-Helsgaun)是求解**旅行商问题(TSP)**的最强启发式算法之一,由丹麦计算机科学家Keld Helsgaun在LKH-2基础上改进而来。它的核心思想是:通过智能的“局部破坏与修复”策略,逐步优化路径,最终找到接近最优的解。


1. 类比理解

想象你是一个快递员,要访问多个城市送货,目标是走最短路线。LKH-3的工作方式类似于:

  1. 先随便规划一条路线(可能很长)。
  2. 不断尝试对路线做小改动(比如交换两个城市的顺序、反转一段路径)。
  3. 只保留能让总距离变短的改动,丢弃无效的改动。
  4. 重复这个过程,直到无法再优化

2. 核心步骤分解

(1) 初始路径生成
  • 随便生成一条初始路径(比如按城市编号顺序连接)。
  • 或使用其他算法(如贪心算法)生成一个较好的起点。
(2) 局部优化(关键部分)

LKH-3通过k-opt交换不断改进路径:

  • k-opt交换:断开路径中的k条边,尝试用其他边重新连接。
    • 2-opt:交换两条边(类似把路径中的一段“翻转”)。
    • 3-opt:交换三条边(更复杂的重组,如图)。
    • LKH-3支持动态k值(最高到5-opt甚至更高)。
(3) 候选集策略(加速关键)
  • 不是对所有城市都尝试交换,而是优先检查“可能有用的邻居”
    • 对每个城市,预先计算最近的若干城市(如最近的20个),形成“候选列表”。
    • 只在这些候选城市之间尝试交换,大幅减少计算量。
(4) 增量式更新
  • 每次优化后,只更新受影响的部分路径,而非重新计算整个路径长度。
(5) 多次迭代
  • 重复上述过程,直到连续N次尝试都无法改进路径。

3. 为什么LKH-3强大?

特性说明
动态k值根据问题复杂度自动调整交换的边数(2-opt到5-opt),灵活性高。
候选集优化通过预选“潜力城市”减少无效计算,速度比暴力搜索快100倍以上。
适应性策略对不同类型的TSP问题(随机分布、聚类分布等)均表现良好。
并行化可多线程同时尝试多种交换策略。

4. 举个实际例子

假设有5个城市,初始路径为 A→B→C→D→E→A,总距离=100:

  1. 尝试2-opt:断开边 A-BC-D,重新连接为 A-CB-D,新路径 A→C→B→D→E→A,距离=95(接受优化)。
  2. 尝试3-opt:断开 A-CB-DE-A,重组为 A→D→B→E→C→A,距离=92(进一步优化)。
  3. 直到无法改进:最终可能得到 A→D→E→B→C→A,距离=90(近似最优解)。

5. 和传统算法的对比

算法优点缺点
穷举法保证找到最优解计算时间随城市数量指数级爆炸
遗传算法适合大规模问题结果不稳定,可能陷入局部最优
LKH-3速度快,解的质量接近最优实现复杂,参数需要调优

6. 实际应用场景

  • 物流配送:优化快递员、外卖骑手的路线。
  • 电路板设计:最小化钻孔机的移动路径。
  • DNA测序:寻找基因片段的最优拼接顺序。

7. 进一步学习

  • 官方实现:LKH-3代码
  • 数学细节:研究论文 Helsgaun, K. (2017). “An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic”

代码实战

Python 3.10 需安装elkai库
实测效果明显优于传统ACO(蚁群算法)+ 2-opt/3-opt局部优化的方法
在这里插入图片描述

elkai源码Github地址
https://github.com/fikisipi/elkai?tab=readme-ov-file

import elkaiimport yaml
import numpy as npimport cv2# data.yml是opencv存储的,距离矩阵,N*N,CV_64FC1,N表示城市数量
fs = cv2.FileStorage("data.yml", cv2.FILE_STORAGE_READ)
data = fs.getNode("double_matrix").mat()
fs.release()# yaml_path = "data.yml"  # 替换为你的文件路径
# cities = read_opencv_yaml_to_array(yaml_path)cities = elkai.DistanceMatrix(data)path = cities.solve_tsp()print(path) # Output: [0, 2, 1, 0]# 手动计算总距离
total_dist = 0
for i in range(len(path)-2):total_dist += data[path[i]][path[i+1]]
print(total_dist) # Output: 10.0

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/web/88137.shtml
繁体地址,请注明出处:http://hk.pswp.cn/web/88137.shtml
英文地址,请注明出处:http://en.pswp.cn/web/88137.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

游戏开发学习记录

初始化只是第一次实例化的时候调用,show和unshow是打开界面和关闭界面的时候,会多次调用 在一个脚本里面show是每一次打开界面的时候需要做的事情,而Init是初始化。UIMgr里面的数据结构:为什么我要先从数据结构入手呢?…

一级缓存与二级缓存深度剖析:作用域、配置与同步方案全解析

引言 在分布式系统与高并发场景下,缓存机制已成为提升系统性能的关键技术。本文从作用域、失效机制、配置实践到同步方案,系统化解析一级缓存与二级缓存的核心差异与工程实践。 一、一级缓存:会话级数据加速器 1.1 作用域与生命周期 作用域&a…

OneCode MQTT插件开发实战:基于Paho.Client的物联网通信解决方案

引言 在物联网应用开发中,MQTT协议因其轻量、低带宽占用的特性被广泛采用。OneCode平台提供的xui.MQTT插件基于Eclipse Paho.Client实现了完整的MQTT通信能力,本文将从插件用途、核心实现、开发要点和功能扩展四个维度,详解如何基于该插件构建…

1.1_5_1 计算机网络的性能指标(上)

在这个小节中我们要学习计算机网络的性能指标,我们在考研当中主要掌握这样的七个性能指标,分别是速率、带宽、吞吐量、时延、时延带宽积、往返时延和信道利用率。我会把相关性比较紧密的性能指标放在一起讲解。在这个视频中,我们先来学习前三…

Python 性能优化指南:深入剖析代码分析与优化工具

Python 性能优化指南:深入剖析代码分析与优化工具 在 Python 的广泛应用场景中,性能优化既是挑战,也是机遇。无论是构建 Web 应用还是处理数据分析,理解代码性能瓶颈并有效优化至关重要。本文将探讨 Python 代码性能分析的核心方法,并逐步解析关键工具的使用技巧,带您从…

力扣打卡第二十一天 中后遍历+中前遍历 构造二叉树

106. 从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7], postor…

Notepad++正则表达全解

摘要:Notepad正则表达式符号大全包含11类常用语法:基础符号(.^$?等)、预定义字符类(\d\w\s等)、锚点(\b\B)、量词({n,m})、分组引用(()$1)、字符…

前后端分离(java) 和 Nginx在服务器上的完整部署方案(redis、minio)

一、准备工作 服务器环境要求 银河麒麟 V10 操作系统 开放端口:MinIO (9000、9001)、 Redis (6379)、应用服务 jar包(18888)、前端服务(8080) 系统用户:具有 sudo 权限的用户 操作:需要先有必备的工具前端的vsCode,webStrom、后台的idea&…

贪心算法:简单而高效的求解策略C++

贪心算法详解及C实现 1. 什么是贪心算法 贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。 贪心算法与动态规划不同在于它…

IDEA 中使用 <jsp:useBean>动作指令时,class属性引用无效

问题&#xff1a;在 IDEA 中创建 Java Web项目&#xff0c;在src/model包下存在一个Student类该类中包含&#xff1a;全参构造器、私有属性的get/set方法。然后在 jsp 页面中使用 <jsp:useBean>创建Student类的对象&#xff1a;访问页面时报错&#xff1a;原因&#xff1…

【网络】Linux 内核优化实战 - net.core.flow_limit_table_len

目录参数作用查看与修改调优建议相关警告net.core.flow_limit_table_len 是 Linux 内核中的一个网络参数&#xff0c;用于控制**流限制表&#xff08;Flow Limit Table&#xff09;**的大小。这个表主要用于限制网络流量中单个"流"&#xff08;通常指来自同一源IP、端…

前端开发常见问题技术文章大纲

前端开发常见问题技术文章大纲 常见性能优化问题 页面加载速度慢的原因及解决方案渲染阻塞资源的优化方法内存泄漏的检测与修复 跨浏览器兼容性问题 不同浏览器对CSS和JavaScript的支持差异Polyfill和Shim的使用场景如何利用工具检测兼容性问题 响应式设计挑战 媒体查询的最佳实…

Redis常见性能问题和解决方案有哪些?

Redis 作为高性能的内存数据库&#xff0c;在实际使用中可能会遇到性能问题。以下是常见的性能问题及其解决方案&#xff0c;用中文总结如下&#xff1a; 1. 高延迟问题 问题描述&#xff1a;客户端请求响应时间过长&#xff0c;可能由于网络、命令复杂度或服务器负载导致。 解…

闪测仪应用案例丨手机中框如何突破「尺寸检测」瓶颈?

越来越多的手机中框&#xff0c;正改为更复杂的镂空设计&#xff0c;这种设计不仅保持了手机中框的结构强度&#xff0c;还进一步减轻了机身重量&#xff0c;同时提升了散热性能。这让手机中框的自动化生产增加了很多难点&#xff0c;其中的尺寸检测就遇到了许多瓶颈。▪ 尺寸精…

【字节跳动】数据挖掘面试题0011:介绍下时间序列分析常用知识点

文章大纲时间序列分析全面解析一、时间序列分析的基本概念二、时间序列分析的主要方法1. 描述性分析2.统计分析方法3.预测模型&#xff08;1&#xff09;传统统计模型&#xff08;2&#xff09;现代机器学习模型三、时间序列分析的应用场景四、模型评估五、在字节跳动的应用场景…

ubuntu中交叉编译iperf3到目标平台xilinx

注&#xff1a;此文为ubuntu x86系统编译程序到xilinx aarch64系统中。 一、工具准备 x86上编译aarch64的编译器 sudo apt install gcc-aarch64-linux-gnu g-aarch64-linux-gnu #保证编译器在环境变量中&#xff0c;尝试执行aarch64-linux-gnu-gcc 目标平台的根文件系统rootf…

Java-数据结构-集合框架

什么是集合框架集合本质是java所实现的一组数据结构&#xff0c;提供了不同的增删改查方法。集合就是定义了接口&#xff0c;再通过不同的类去实现定义的接口&#xff0c;这些实现了接口的类就是集合类&#xff0c;例如list&#xff0c;stack&#xff0c;map。集合框架的重要性…

黑马点评系列问题之基础篇16jedis redis依赖引入后仍然还是报错

问题描述依赖已经导入进去了&#xff0c;在仓库里有***.jar和***.pom这两个文件&#xff0c;但是点开右面的maven还是有很多爆红。点击maven里的更新还是不行。解决点到配置文件pom.xml在lombok这个依赖的代码下面&#xff0c;添加上版本号&#xff0c;刷新一下右键单击pom.xml…

SQL 一键转 GORM 模型,支持字段注释、类型映射、tag 自定义!

SQL 一键转 GORM 模型&#xff0c;支持字段注释、类型映射、tag 自定义&#xff01; 在使用 Golang GORM 开发项目时&#xff0c;你是否也经历过这些「重复性痛苦」&#xff1a; ✅ 拿到建表 SQL&#xff0c;要手动写 struct✅ 字段多、类型复杂&#xff0c;还要写 json、go…

前端计算机视觉:使用 OpenCV.js 在浏览器中实现图像处理

一、OpenCV.js 简介与环境搭建OpenCV&#xff08;Open Source Computer Vision Library&#xff09;是一个强大的计算机视觉库&#xff0c;广泛应用于图像和视频处理领域。传统上&#xff0c;OpenCV 主要在后端使用 Python 或 C 等语言。但随着 WebAssembly (Wasm) 技术的发展&…