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

【回溯算法】【Python实现】TSP旅行售货员问题

文章目录

    • @[toc]
      • 问题描述
      • 回溯算法
      • `Python`实现
      • 时间复杂性

问题描述

  • 给定一组城市和它们之间的距离矩阵,找到一条距离最短的路径,使得旅行商从一个城市出发,经过所有城市恰好一次,并最终回到出发城市

回溯算法

  • 旅行售货员问题的解空间是一棵排列树

  • i = n i = n i=n时,算法搜索至叶结点,其相应的路径长度为 c d cd cd,如果 c d < b e s t d cd < bestd cd<bestd,则表示当前解优于当前最优解,此时更新 b e s t d bestd bestd

  • i < n i < n i<n时,当前扩展结点位于排列树的第 i i i层,图 G G G中存在从顶点 x [ i ] x[i] x[i]到顶点 x [ i + 1 ] x[i + 1] x[i+1]的边时, x [ 1 : i + 1 ] x[1 : i + 1] x[1:i+1]构成图 G G G的一条路径,且当 x [ 1 : i + 1 ] x[1 : i + 1] x[1:i+1]的路径长度小于当前最优值时算法进入排列树的第 i + 1 i + 1 i+1层,否则将剪去相应的子树


Python实现

import numpy as npdef backtrack_tsp(cities):n = len(cities)visited = [False] * n  # 记录城市是否已经被访问shortest_path = []shortest_distance = float('inf')def distance(city1, city2):x1, y1 = city1x2, y2 = city2return np.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)# 创建距离矩阵dist_matrix = np.zeros((n, n))for i in range(n):for j in range(n):dist_matrix[i][j] = distance(cities[i], cities[j])def backtrack(path, distance):nonlocal shortest_path, shortest_distanceif len(path) == n:  # 所有城市都已经访问过distance += dist_matrix[path[-1]][path[0]]  # 回到起点的距离if distance < shortest_distance:  # 更新最短路径和最短距离shortest_path = path[:]shortest_distance = distancereturnlast_city = path[-1] if path else 0  # 上一个访问的城市for next_city in range(n):if not visited[next_city]:visited[next_city] = Truepath.append(next_city)distance += dist_matrix[last_city][next_city]backtrack(path, distance)# 恢复回溯前状态distance -= dist_matrix[last_city][next_city]path.pop()visited[next_city] = False# 开始回溯搜索visited[0] = Truebacktrack([0], 0)return shortest_path, shortest_distancecities = [(0, 0), (1, 5), (2, 3), (5, 2), (6, 4)]
shortest_path, shortest_distance = backtrack_tsp(cities)print(f'最短路径: {shortest_path}')
print(f'最短距离: {shortest_distance}')
最短路径: [0, 2, 1, 4, 3]
最短距离: 18.56187155119086

时间复杂性

  • 回溯算法解TSP问题的时间复杂性为 O ( n ! ) O(n!) O(n!)

相关文章:

【回溯算法】【Python实现】TSP旅行售货员问题

文章目录 [toc]问题描述回溯算法Python实现时间复杂性 问题描述 给定一组城市和它们之间的距离矩阵&#xff0c;找到一条距离最短的路径&#xff0c;使得旅行商从一个城市出发&#xff0c;经过所有城市恰好一次&#xff0c;并最终回到出发城市 回溯算法 旅行售货员问题的解空间…...

Java处理xml

Java处理xml DOM&#xff08;Document Object Model&#xff09;读取写入参考文献[Java DOM 教程](https://geek-docs.com/java/java-tutorial/dom.html#ftoc-heading-5) DOM&#xff08;Document Object Model&#xff09; Java的DOM&#xff08;Document Object Model&#…...

软考中级-软件设计师 (十一)标准化和软件知识产权基础知识

一、标准化基础知识 1.1标准的分类 根据适用的范围分类&#xff1a; 国际标准指国际化标准组织&#xff08;ISO&#xff09;、国际电工委员会&#xff08;IEC&#xff09;所制定的标准&#xff0c;以及ISO所收录的其他国际组织制定的标准。 国家标准&#xff1a;中华人民共和…...

pytest教程-46-钩子函数-pytest_sessionstart

领取资料&#xff0c;咨询答疑&#xff0c;请➕wei: June__Go 上一小节我们学习了pytest_report_testitemFinished钩子函数的使用方法&#xff0c;本小节我们讲解一下pytest_sessionstart钩子函数的使用方法。 pytest_sessionstart 是 Pytest 提供的一个钩子函数&#xff0c…...

Windows内核函数 - ASCII字符串和宽字符串

本章介绍了Windows内核中字符串处理函数、文件读写函数、注册表读写函数。这些函数是DDK提供的运行时函数&#xff0c;他们比标准C语言的运行时函数功能更丰富。普通的C语言运行时库是不能在内核模式下使用的&#xff0c;必须使用DDK提供的运行时函数。 和应用程序一样&#xf…...

从零开始学习MySQL 事务处理

事务处理与ACID特性 事务是数据库操作的基本单元&#xff0c;它确保一组操作要么全部成功&#xff0c;要么全部失败&#xff0c;以此来维护数据库的一致性。这四个字母缩写ACID代表了事务的四大特性&#xff1a; 原子性&#xff08;Atomicity&#xff09;**&#xff1a;事务被…...

字符数组以及字符串相关的几个函数

一.字符数组 1.定义&#xff1a;格式如下 char a[10]; //此处就表示定义了一个长度为10的字符数组 2.引用&#xff1a; 也和其余的数组一样&#xff0c;是下标引用。 3.初始化&#xff1a; 如下代码为字符数组初始化的几种情况&#xff1a; int main() {char arr[5] {…...

AOP面向切面编程

1&#xff0c;注入依赖 <!--web--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></dependency><dependency><groupId>org.springframework.boot</grou…...

C# WinForm —— 15 DateTimePicker 介绍

1. 简介 2. 常用属性 属性解释(Name)控件ID&#xff0c;在代码里引用的时候会用到,一般以 dtp 开头Format设置显示时间的格式&#xff0c;包含Long&#xff1a; Short&#xff1a; Time&#xff1a; Custom&#xff1a;采用标准的时间格式 还是 自定义的格式CustomFormat自定…...

SpringBoot中六种批量更新Mysql 方式效率对比

SpringBoot中六种批量更新Mysql 方式效率对比 先上结论吧,有空可以自测一下,数据量大时运行一次还时挺耗时的 效率比较 小数据量时6中批量更新效率不太明显,根据项目选择合适的即可,以1万条为准做个效率比较,效率从高到低一次排名如下 replace into和ON DUPLICATE KEY效率最…...

【SpringBoot】SpringBoot整合jasypt进行重要数据加密

&#x1f4dd;个人主页&#xff1a;哈__ 期待您的关注 目录 &#x1f4d5;jasypt简介 &#x1f525;SpringBoot使用jasypt &#x1f4c2;创建我需要的数据库文件 &#x1f4d5;引入依赖 &#x1f513;配置数据库文件&#xff08;先不进行加密&#xff09; &#x1f319;创…...

【Go语言入门学习笔记】Part1.梦开始的地方

一、前言 经过一系列的学习&#xff0c;终于有时间来学习一些新的语言&#xff0c;Go语言在现在还是比较时髦的&#xff0c;多一个技能总比不多的好&#xff0c;故有时间来学一下。 二、配置环境 按照网络中已有的配置方法配置好&#xff0c;本人采用了Jetbrain的Goland&#…...

数据特征降维 | 主成分分析(PCA)附Python代码

主成分分析(Principal Component Analysis,PCA)是一种常用的数据降维技术和探索性数据分析方法,用于从高维数据中提取出最重要的特征并进行可视化。 PCA的基本思想是通过线性变换将原始数据投影到新的坐标系上,使得投影后的数据具有最大的方差。这些新的坐标轴称为主成分…...

当服务实例出现故障时,Nacos如何处理?

当服务实例出现故障时&#xff0c;Nacos的应对策略 在微服务架构日益盛行的今天&#xff0c;服务之间的稳定性与可靠性成为了我们架构师们不得不面对的重要课题。尤其是在面对服务实例出现故障时&#xff0c;如何确保整个系统的稳定运行&#xff0c;成为了我们首要考虑的问题。…...

遥感数据集制作(Potsdam数据集为例):TIF图像转JPG,TIF标签转PNG,图像重叠裁剪

文章目录 TIF图像转JPGTIF标签转PNG图像重叠裁剪图像重命名数据集转COCO格式数据集转VOC格式 遥感图像不同于一般的自然图像&#xff0c;由于波段数量、图像位深度等原因&#xff0c;TIF图像数据不能使用简单的格式转换方法。本文以Potsdam数据集为例&#xff0c;制作能够直接用…...

根据web访问日志,封禁请求量异常的IP,如IP在半小 时后恢复正常则解除封禁

在网络安全日益受到重视的今天&#xff0c;如何有效防范恶意流量和攻击成为了每个网站管理员必须面对的问题。恶意流量不仅会影响网站的正常运行&#xff0c;还可能导致服务器崩溃&#xff0c;给网站带来不可估量的损失。为了应对这一问题&#xff0c;我们特别推出了一款实用的…...

2.go语言初始(二)

本篇博客涉及到go 的基础数据类型、 go 语言中的运算符、转义字符、格式化输出、字符串操作 go 语言中的运算符 在 go 语言中&#xff0c;基本数据类型主要包括以下几类&#xff1a;整数类型、浮点数类型、复数类型、布尔类型、字符串类型、字节类型&#xff08;byte&#xf…...

MQTT对比HTTP

吞吐量&#xff1a;根据3G网络的测量结果&#xff0c;MQTT的吞吐量比HTTP快93倍。这意味着在相同的网络条件下&#xff0c;MQTT能够更有效地传输数据&#xff0c;从而在处理大量数据或实时数据传输时具有更高的效率。架构与模式&#xff1a;MQTT基于发布/订阅模型&#xff0c;提…...

暴力数据结构之二叉树(堆的相关知识)

1. 堆的基本了解 堆&#xff08;heap&#xff09;是计算机科学中一种特殊的数据结构&#xff0c;通常被视为一个完全二叉树&#xff0c;并且可以用数组来存储。堆的主要应用是在一组变化频繁&#xff08;增删查改的频率较高&#xff09;的数据集中查找最值。堆分为大根堆和小根…...

死锁调试技巧:工作线程和用户界面线程

有人碰到了一个死锁问题&#xff0c;找到我们想请我们看看&#xff0c;这个是关于应用程序用户界面相关的死锁问题。 我也不清楚他为什么会找上我们&#xff0c;可能是因为我们经常会和窗口管理器打交道吧。 下面&#xff0c;我们来看看死锁的两个线程。 >> 请移步至 …...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...