算法整理:2-opt求解旅行商(Python代码)
文章目录
- 算法思想
- 算法步骤
- 代码1·纯函数
- 代码2·纯函数+数据+可视化
算法思想
通过交换边进行寻优。

算法步骤
-
把初始解作为当前解
-
通过交换边生成新解

-
如果新解优于历史最优解,则更新当前解为新解
-
重复2,3,直到当前解交换了所有的边均不能改善。
代码1·纯函数
def two_opt(I, c):"""Two-opt 旅行商路径优化算法I: 城市编号的listc: 距离矩阵c[i,j]"""best_distance = sum(c[I[i], I[i + 1]] for i in range(len(I) - 1))best_solution = I[:]improve = Trues = 0while improve:improve = Falsefor i in range(len(I) - 1):for j in range(i + 1, len(I) - 1):if j - i >= 1: # 确保至少有两个城市在i和j之间delta = (c[best_solution[i - 1], best_solution[j]] +c[best_solution[i], best_solution[j + 1]] -c[best_solution[i - 1], best_solution[i]] -c[best_solution[j], best_solution[j + 1]])if delta < -0.0001:# 进行反转操作best_solution[i:j + 1] = reversed(best_solution[i:j + 1])plot_route(cities, best_solution)best_distance += deltaimprove = Truereturn best_solution, best_distance
- 注意代码中当i == 0时,best_solution[i - 1] =best_solution[- 1],指向了最后一个城市,由于是TSP问题,并不违反逻辑。
代码2·纯函数+数据+可视化
import time
import numpy as np
import matplotlib.pyplot as pltdef generate_random_cities(num_cities):"""生成随机的城市坐标及距离矩阵"""np.random.seed(3) # 锁定随机种子cities = np.random.rand(num_cities, 2) # 生成随机坐标distance_matrix = np.zeros((num_cities, num_cities))for i in range(num_cities):for j in range(num_cities):distance_matrix[i, j] = np.linalg.norm(cities[i] - cities[j]) # 计算欧几里得距离return cities, distance_matrixdef two_opt(I, c):"""Two-opt 旅行商路径优化算法I: 城市编号的listc: 距离矩阵c[i,j]"""best_distance = sum(c[I[i], I[i + 1]] for i in range(len(I) - 1))best_solution = I[:]improve = Trues = 0while improve:improve = Falsefor i in range(len(I) - 1):for j in range(i + 2, len(I) - 1):delta = (c[best_solution[i - 1], best_solution[j]] +c[best_solution[i], best_solution[j + 1]] -c[best_solution[i - 1], best_solution[i]] -c[best_solution[j], best_solution[j + 1]])if delta < -1e-6:# 进行反转操作best_solution[i:j + 1] = reversed(best_solution[i:j + 1])plot_route(cities, best_solution)best_distance += deltaimprove = Truereturn best_solution, best_distancedef plot_route(cities, solution):"""可视化城市和路径"""# 画出路径plt.plot(cities[solution][:, 0], cities[solution][:, 1], color='black', marker='o')plt.plot([cities[solution[0], 0], cities[solution[-1], 0]],[cities[solution[0], 1], cities[solution[-1], 1]], color='black', marker='o') # 回到起点# 去掉坐标轴黑框ax = plt.gca()ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')ax.spines['left'].set_color('none')ax.spines['bottom'].set_color('none')# 隐藏坐标轴刻度ax.xaxis.set_ticks_position('none')ax.yaxis.set_ticks_position('none')# 隐藏坐标轴刻度标签ax.set_xticks([]) ax.set_yticks([])# 每帧显示时间plt.pause(1)# 清空内容plt.cla()# 主程序
num_cities = 10 # 城市数量
cities, distance_matrix = generate_random_cities(num_cities)
I = list(range(num_cities)) # 编号的集合# 运行 two_opt 算法
optimized_solution, optimized_distance = two_opt(I, distance_matrix)# 打印结果
print("优化后的路径:", optimized_solution)
print("优化后的距离:", optimized_distance)# 可视化优化后的路径
plot_route(cities, optimized_solution)
相关文章:
算法整理:2-opt求解旅行商(Python代码)
文章目录 算法思想算法步骤代码1纯函数代码2纯函数数据可视化 算法思想 通过交换边进行寻优。 算法步骤 把初始解作为当前解 通过交换边生成新解 如果新解优于历史最优解,则更新当前解为新解 重复2,3,直到当前解交换了所有的边均不能改…...
状态模式
在软件开发过程中,我们经常会遇到这样的情况:一个对象的行为会随着其内部状态的改变而发生变化。例如,一个手机在不同状态下(开机、关机、静音等)对相同的操作(如来电)会有不同的反应。传统的解…...
RoHS 简介
RoHS(Restriction of Hazardous Substances Directive,限制有害物质指令)是欧盟制定的一项环保法规,旨在限制电气和电子设备中某些有害物质的使用,以减少这些产品对环境和人体健康的危害。 RoHS限制的有害物质及其限量…...
【Vim Masterclass 笔记26】S11L46:Vim 插件的安装、使用与日常管理
文章目录 Section 11:Vim PluginsS11L46 Managing Vim Plugins1 第三方插件管理工具2 安装插件使用的搜索引擎3 Vim 插件的安装方法4 存放 Vim 插件包的路径格式5 示例一:插件 NERDTree 的安装6 示例二:插件 ctrlp.vim 的安装7 示例三&#x…...
深度学习原理与Pytorch实战
深度学习原理与Pytorch实战 第2版 强化学习人工智能神经网络书籍 python动手学深度学习框架书 TransformerBERT图神经网络: 技术讲解 编辑推荐 1.基于PyTorch新版本,涵盖深度学习基础知识和前沿技术,由浅入深,通俗易懂…...
ELK环境搭建
文章目录 1.ElasticSearch安装1.安装的版本选择1.SpringBoot版本:2.4.2 找到依赖的spring-data-elasticsearch的版本2.spring-data-elasticsearch版本:4.1.3 找到依赖的elasticsearch版本3.elasticsearch版本:7.9.3 2.安装1.官方文档2.下载压…...
基于Springboot + vue实现的民俗网
“前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站:人工智能学习网站” 💖学习知识需费心, 📕整理归纳更费神。 🎉源码免费人人喜…...
第24篇 基于ARM A9处理器用汇编语言实现中断<六>
Q:怎样设计ARM处理器汇编语言程序使用定时器中断实现实时时钟? A:此前我们曾使用轮询定时器I/O的方式实现实时时钟,而在本实验中将采用定时器中断的方式。新增第三个中断源A9 Private Timer,对该定时器进行配置&#…...
【数据结构】_不带头非循环单向链表
目录 1. 链表的概念及结构 2. 链表的分类 3. 单链表的实现 3.1 SList.h头文件 3.2 SList.c源文件 3.3 Test_SList.c测试文件 关于线性表,已介绍顺序表,详见下文: 【数据结构】_顺序表-CSDN博客 本文介绍链表; 基于顺序表…...
golang 使用双向链表作为container/heap的载体
MyHeap:container/heap的数据载体,需要实现以下方法: Len:堆中数据个数 Less:第i个元素 是否必 第j个元素 值小 Swap:交换第i个元素和 第j个元素 Push:向堆中追加元素 Pop:从堆…...
C#集合操作优化:高效实现批量添加与删除
在C#中,对集合进行批量操作(如批量添加或删除元素)通常涉及使用集合类型提供的方法和特性,以及可能的循环或LINQ查询来高效地处理大量数据。以下是一些常见的方法和技巧: 批量添加元素 使用集合的AddRange方法&#x…...
142.WEB渗透测试-信息收集-小程序、app(13)
免责声明:内容仅供学习参考,请合法利用知识,禁止进行违法犯罪活动! 内容参考于: 易锦网校会员专享课 上一个内容:141.WEB渗透测试-信息收集-小程序、app(12) 软件用法,…...
24.日常算法
1. 数组中两元素的最大乘积 题目来源 给你一个整数数组 nums,请你选择数组的两个不同下标 i 和 j,使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。 示例 1: 输入:nums [3,4,5,2] 输出:12 解释…...
分布式理解
分布式 如何理解分布式 狭义的分布是指,指多台PC在地理位置上分布在不同的地方。 分布式系统 分布式系**统:**多个能独立运行的计算机(称为结点)组成。各个结点利用计算机网络进行信息传递,从而实现共同的“目标或者任…...
wordpress调用指定ID页面的链接
在WordPress中,如果你想调用一个指定ID的页面链接,可以使用以下几种方法: 方法一:使用页面ID 你可以直接使用页面的ID来生成链接。例如,如果你想链接到ID为123的页面,可以使用以下代码: <…...
单值二叉树(C语言详解版)
一、摘要 今天要讲的是leetcode单值二叉树,这里用到的C语言,主要提供的是思路,大家看了我的思路之后可以点击链接自己试一下。 二、题目简介 如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 只有给定的树是单…...
python学opencv|读取图像(四十二)使用cv2.add()函数实现多图像叠加
【1】引言 前序学习过程中,掌握了灰度图像和彩色图像的掩模操作: python学opencv|读取图像(九)用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 python学opencv|读取图像(四十)掩模:三…...
速通Docker === Docker Compose
目录 Docker Compose 简介 Docker Compose 常用命令 使用 Docker Compose 启动 WordPress 普通启动方式(使用 Docker 命令) 使用 Docker Compose 启动 Docker Compose 的特性 Docker Compose 简介 Docker Compose 是一个用于定义和运行多容器 Dock…...
LMI Gocator GO_SDK VS2019引用配置
LMI SDK在VS2019中的引用是真的坑爹,总结一下经验,希望后来的人能少走弯路.大致内容如下: (1) 环境变量 (2)C/C 附加包含目录 E:\GWQ\Gocator\GO_SDK\Gocator\GoSdk E:\GWQ\Gocator\GO_SDK\Platform\kApi (3&#…...
技术之翼,创作之心
引言:初入编程的迷茫与追求 当我第一次接触到编程时,心中充满了既期待又迷茫的情感。那时,我还是一名刚刚踏入大学的学生,面对一门陌生而复杂的学科——计算机科学,我的内心充满了好奇与困惑。课堂上,老师…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
