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

算法整理:2-opt求解旅行商(Python代码)

文章目录

      • 算法思想
      • 算法步骤
      • 代码1·纯函数
      • 代码2·纯函数+数据+可视化

算法思想

通过交换边进行寻优。
在这里插入图片描述

算法步骤

  1. 把初始解作为当前解

  2. 通过交换边生成新解
    在这里插入图片描述

  3. 如果新解优于历史最优解,则更新当前解为新解

  4. 重复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纯函数数据可视化 算法思想 通过交换边进行寻优。 算法步骤 把初始解作为当前解 通过交换边生成新解 如果新解优于历史最优解&#xff0c;则更新当前解为新解 重复2&#xff0c;3&#xff0c;直到当前解交换了所有的边均不能改…...

状态模式

在软件开发过程中&#xff0c;我们经常会遇到这样的情况&#xff1a;一个对象的行为会随着其内部状态的改变而发生变化。例如&#xff0c;一个手机在不同状态下&#xff08;开机、关机、静音等&#xff09;对相同的操作&#xff08;如来电&#xff09;会有不同的反应。传统的解…...

RoHS 简介

RoHS&#xff08;Restriction of Hazardous Substances Directive&#xff0c;限制有害物质指令&#xff09;是欧盟制定的一项环保法规&#xff0c;旨在限制电气和电子设备中某些有害物质的使用&#xff0c;以减少这些产品对环境和人体健康的危害。 RoHS限制的有害物质及其限量…...

【Vim Masterclass 笔记26】S11L46:Vim 插件的安装、使用与日常管理

文章目录 Section 11&#xff1a;Vim PluginsS11L46 Managing Vim Plugins1 第三方插件管理工具2 安装插件使用的搜索引擎3 Vim 插件的安装方法4 存放 Vim 插件包的路径格式5 示例一&#xff1a;插件 NERDTree 的安装6 示例二&#xff1a;插件 ctrlp.vim 的安装7 示例三&#x…...

深度学习原理与Pytorch实战

深度学习原理与Pytorch实战 第2版 强化学习人工智能神经网络书籍 python动手学深度学习框架书 TransformerBERT图神经网络&#xff1a; 技术讲解 编辑推荐 1.基于PyTorch新版本&#xff0c;涵盖深度学习基础知识和前沿技术&#xff0c;由浅入深&#xff0c;通俗易懂&#xf…...

ELK环境搭建

文章目录 1.ElasticSearch安装1.安装的版本选择1.SpringBoot版本&#xff1a;2.4.2 找到依赖的spring-data-elasticsearch的版本2.spring-data-elasticsearch版本&#xff1a;4.1.3 找到依赖的elasticsearch版本3.elasticsearch版本&#xff1a;7.9.3 2.安装1.官方文档2.下载压…...

基于Springboot + vue实现的民俗网

“前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff1a;人工智能学习网站” &#x1f496;学习知识需费心&#xff0c; &#x1f4d5;整理归纳更费神。 &#x1f389;源码免费人人喜…...

第24篇 基于ARM A9处理器用汇编语言实现中断<六>

Q&#xff1a;怎样设计ARM处理器汇编语言程序使用定时器中断实现实时时钟&#xff1f; A&#xff1a;此前我们曾使用轮询定时器I/O的方式实现实时时钟&#xff0c;而在本实验中将采用定时器中断的方式。新增第三个中断源A9 Private Timer&#xff0c;对该定时器进行配置&#…...

【数据结构】_不带头非循环单向链表

目录 1. 链表的概念及结构 2. 链表的分类 3. 单链表的实现 3.1 SList.h头文件 3.2 SList.c源文件 3.3 Test_SList.c测试文件 关于线性表&#xff0c;已介绍顺序表&#xff0c;详见下文&#xff1a; 【数据结构】_顺序表-CSDN博客 本文介绍链表&#xff1b; 基于顺序表…...

golang 使用双向链表作为container/heap的载体

MyHeap&#xff1a;container/heap的数据载体&#xff0c;需要实现以下方法&#xff1a; Len&#xff1a;堆中数据个数 Less&#xff1a;第i个元素 是否必 第j个元素 值小 Swap&#xff1a;交换第i个元素和 第j个元素 Push&#xff1a;向堆中追加元素 Pop&#xff1a;从堆…...

C#集合操作优化:高效实现批量添加与删除

在C#中&#xff0c;对集合进行批量操作&#xff08;如批量添加或删除元素&#xff09;通常涉及使用集合类型提供的方法和特性&#xff0c;以及可能的循环或LINQ查询来高效地处理大量数据。以下是一些常见的方法和技巧&#xff1a; 批量添加元素 使用集合的AddRange方法&#x…...

142.WEB渗透测试-信息收集-小程序、app(13)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;141.WEB渗透测试-信息收集-小程序、app&#xff08;12&#xff09; 软件用法&#xff0c…...

24.日常算法

1. 数组中两元素的最大乘积 题目来源 给你一个整数数组 nums&#xff0c;请你选择数组的两个不同下标 i 和 j&#xff0c;使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。 示例 1&#xff1a; 输入&#xff1a;nums [3,4,5,2] 输出&#xff1a;12 解释…...

分布式理解

分布式 如何理解分布式 狭义的分布是指&#xff0c;指多台PC在地理位置上分布在不同的地方。 分布式系统 分布式系**统&#xff1a;**多个能独立运行的计算机&#xff08;称为结点&#xff09;组成。各个结点利用计算机网络进行信息传递&#xff0c;从而实现共同的“目标或者任…...

wordpress调用指定ID页面的链接

在WordPress中&#xff0c;如果你想调用一个指定ID的页面链接&#xff0c;可以使用以下几种方法&#xff1a; 方法一&#xff1a;使用页面ID 你可以直接使用页面的ID来生成链接。例如&#xff0c;如果你想链接到ID为123的页面&#xff0c;可以使用以下代码&#xff1a; <…...

单值二叉树(C语言详解版)

一、摘要 今天要讲的是leetcode单值二叉树&#xff0c;这里用到的C语言&#xff0c;主要提供的是思路&#xff0c;大家看了我的思路之后可以点击链接自己试一下。 二、题目简介 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。 只有给定的树是单…...

python学opencv|读取图像(四十二)使用cv2.add()函数实现多图像叠加

【1】引言 前序学习过程中&#xff0c;掌握了灰度图像和彩色图像的掩模操作&#xff1a; python学opencv|读取图像&#xff08;九&#xff09;用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 python学opencv|读取图像&#xff08;四十&#xff09;掩模&#xff1a;三…...

速通Docker === Docker Compose

目录 Docker Compose 简介 Docker Compose 常用命令 使用 Docker Compose 启动 WordPress 普通启动方式&#xff08;使用 Docker 命令&#xff09; 使用 Docker Compose 启动 Docker Compose 的特性 Docker Compose 简介 Docker Compose 是一个用于定义和运行多容器 Dock…...

LMI Gocator GO_SDK VS2019引用配置

LMI SDK在VS2019中的引用是真的坑爹,总结一下经验,希望后来的人能少走弯路.大致内容如下: &#xff08;1&#xff09; 环境变量 &#xff08;2&#xff09;C/C 附加包含目录 E:\GWQ\Gocator\GO_SDK\Gocator\GoSdk E:\GWQ\Gocator\GO_SDK\Platform\kApi &#xff08;3&#…...

技术之翼,创作之心

引言&#xff1a;初入编程的迷茫与追求 当我第一次接触到编程时&#xff0c;心中充满了既期待又迷茫的情感。那时&#xff0c;我还是一名刚刚踏入大学的学生&#xff0c;面对一门陌生而复杂的学科——计算机科学&#xff0c;我的内心充满了好奇与困惑。课堂上&#xff0c;老师…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

李沐--动手学深度学习--GRU

1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...