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

【opencv】示例-travelsalesman.cpp 使用模拟退火算法求解旅行商问题

0446b2afe218c87af03978969e6983bd.png

6eb23516b6dbfac595d1d35f62b8b3ee.png

3f6ce269db2eaaf6bfd4d672d76e98e1.png

// 载入 OpenCV 的核心头文件
#include <opencv2/core.hpp>
// 载入 OpenCV 的图像处理头文件
#include <opencv2/imgproc.hpp>
// 载入 OpenCV 的高层GUI(图形用户界面)头文件
#include <opencv2/highgui.hpp>
// 载入 OpenCV 的机器学习模块头文件
#include <opencv2/ml.hpp>// 使用命名空间cv,避免每次调用 OpenCV 的功能时都要前缀cv::
using namespace cv;// 定义旅行商(TravelSalesman)类
class TravelSalesman
{
private :// 私有成员:城市位置向量的引用const std::vector<Point>& posCity;// 私有成员:下一个城市索引的向量引用std::vector<int>& next;// 私有成员:随机数生成器RNG rng;// 私有成员:用于记录状态改变的城市索引int d0,d1,d2,d3;public:// 构造函数初始化城市位置和下一个城市的索引TravelSalesman(std::vector<Point> &p, std::vector<int> &n) :posCity(p), next(n){// 初始化随机数生成器rng = theRNG();}// 返回系统状态的能量值double energy() const;// 改变系统状态(随机扰动)void changeState();// 撤销到之前的状态void reverseState();};// 实现改变状态的函数
void TravelSalesman::changeState()
{// 产生随机城市索引d0 = rng.uniform(0,static_cast<int>(posCity.size()));// 获取随机城市后的各个城市索引d1 = next[d0];d2 = next[d1];d3 = next[d2];// 更改城市访问的顺序next[d0] = d2;next[d2] = d1;next[d1] = d3;
}// 实现撤销状态改变的函数
void TravelSalesman::reverseState()
{// 恢复原来的城市访问顺序next[d0] = d1;next[d1] = d2;next[d2] = d3;
}// 实现计算能量值的函数,能量值为城市间距离的总和
double TravelSalesman::energy() const
{// 初始化能量值double e = 0;// 遍历城市计算总距离for (size_t i = 0; i < next.size(); i++){// 计算两城市间距离并累加到能量值e += norm(posCity[i]-posCity[next[i]]);}// 返回总能量值return e;
}// 绘制每个城市点和城市间连线
static void DrawTravelMap(Mat &img, std::vector<Point> &p, std::vector<int> &n)
{// 遍历所有城市for (size_t i = 0; i < n.size(); i++){// 在图像中用小圆点表示城市位置circle(img,p[i],5,Scalar(0,0,255),2);// 连接城市间的线表示旅行路径line(img,p[i],p[n[i]],Scalar(0,255,0),2);}
}int main(void)
{// 设置城市数量int nbCity=40;// 创建图像,用于显示城市地图Mat img(500,500,CV_8UC3,Scalar::all(0));// 初始化随机数生成器,种子为123456RNG rng(123456);// 设置城市生成的半径范围int radius=static_cast<int>(img.cols*0.45);// 设置图像中心点位置Point center(img.cols/2,img.rows/2);// 初始化城市位置向量和下一个城市索引向量std::vector<Point> posCity(nbCity);std::vector<int> next(nbCity);// 随机生成城市位置for (size_t i = 0; i < posCity.size(); i++){// 在圆周上均匀分布城市double theta = rng.uniform(0., 2 * CV_PI);// 计算城市的坐标并存储posCity[i].x = static_cast<int>(radius*cos(theta)) + center.x;posCity[i].y = static_cast<int>(radius*sin(theta)) + center.y;// 设定下一个城市的索引next[i]=(i+1)%nbCity;}// 创建旅行商问题系统实例TravelSalesman ts_system(posCity, next);// 绘制初始的旅行商问题地图DrawTravelMap(img,posCity,next);// 显示地图窗口imshow("Map",img);// 短暂等待时间waitKey(10);// 初始化模拟退火算法的当前温度double currentTemperature = 100.0;// 模拟退火循环,直到连续10次没有改变发生时停止for (int i = 0, zeroChanges = 0; zeroChanges < 10; i++){// 执行模拟退火算法,尝试改变系统状态int changesApplied = ml::simulatedAnnealingSolver(ts_system, currentTemperature, currentTemperature*0.97, 0.99, 10000*nbCity, &currentTemperature, rng);// 重绘图像,显示新的旅行路径img.setTo(Scalar::all(0));DrawTravelMap(img, posCity, next);imshow("Map", img);// 短暂等待时间并检查是否有退出键被按下int k = waitKey(10);// 输出当前循环的信息std::cout << "i=" << i << " changesApplied=" << changesApplied << " temp=" << currentTemperature << " result=" << ts_system.energy() << std::endl;// 如果用户按下退出键,则退出程序if (k == 27 || k == 'q' || k == 'Q')return 0;// 如果没有改变发生,则计数器加1if (changesApplied == 0)zeroChanges++;}// 完成模拟退火算法,输出结束信息std::cout << "Done" << std::endl;// 等待用户按键以退出waitKey(0);// 程序结束return 0;
}

这段代码实现了一个使用模拟退火算法的旅行商问题解决方案。在这个解决方案中,首先随机在一个圆周上生成一定数量的城市,并在地图上用圆点和连线显示出旅行商访问城市的路径。然后,通过模拟退火算法不断尝试随机扰动城市访问的顺序,通过最小化城市间路径的总长度来寻找最优解(即最短路径)。代码中绘图部分使用了OpenCV库,而模拟退火的具体实现使用了OpenCV的机器学习模块。

相关文章:

【opencv】示例-travelsalesman.cpp 使用模拟退火算法求解旅行商问题

// 载入 OpenCV 的核心头文件 #include <opencv2/core.hpp> // 载入 OpenCV 的图像处理头文件 #include <opencv2/imgproc.hpp> // 载入 OpenCV 的高层GUI(图形用户界面)头文件 #include <opencv2/highgui.hpp> // 载入 OpenCV 的机器学习模块头文件 #includ…...

【linux深入剖析】深入理解软硬链接 | 动静态库的制作以及使用

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1.理解软硬链接1.1 操作观…...

xss常用标签和触发事件

无过滤情况 <script> <scirpt>alert("xss");</script> <img> 图片加载错误时触发 <img src"x" οnerrοralert(1)> <img src"1" οnerrοreval("alert(xss)")> 鼠标指针移动到元素时触发 <im…...

WPF中Binding的原理和应用

WPF中Binding的原理和应用 在WPF中&#xff0c;Binding机制是实现数据与界面的连接和同步的重要工具。了解Binding的原理和应用&#xff0c;对于开发人员来说是非常重要的。本文将详细介绍WPF中Binding的原理和应用&#xff0c;帮助读者更好地理解和运用这一强大的机制。 Bin…...

探索设计模式的魅力:深度挖掘响应式模式的潜力,从而精准优化AI与机器学习项目的运行效能,引领技术革新潮流

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 挖掘响应式模式&#xff0c;优化AI与机器学习项目性能&#xff0c;引领技术新潮流 ✨机器学习界的…...

《经典论文阅读2》基于随机游走的节点表示学习—Deepwalk算法

word2vec使用语言天生具备序列这一特性训练得到词语的向量表示。而在图结构上&#xff0c;则存在无法序列的难题&#xff0c;因为图结构它不具备序列特性&#xff0c;就无法得到图节点的表示。deepwalk 的作者提出&#xff1a;可以使用在图上随机游走的方式得到一串序列&#x…...

Java实现二叉树(下)

1.前言 http://t.csdnimg.cn/lO4S7 在前文我们已经简单的讲解了二叉树的基本概念&#xff0c;本文将讲解具体的实现 2.基本功能的实现 2.1获取树中节点个数 public int size(TreeNode root){if(rootnull){return 0;}int retsize(root.left)size(root.right)1;return ret;}p…...

Hello 算法10:搜索

https://www.hello-algo.com/chapter_searching/binary_search/ 二分查找法 给定一个长度为 n的数组 nums &#xff0c;元素按从小到大的顺序排列&#xff0c;数组不包含重复元素。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素&#xff0c;则返回 -1 。 # 首…...

常见分类算法详解

在机器学习和数据科学的广阔领域中&#xff0c;分类算法是至关重要的一环。它广泛应用于各种场景&#xff0c;如垃圾邮件检测、图像识别、情感分析等。本文将深入剖析几种常见的分类算法&#xff0c;帮助读者理解其原理、优缺点以及应用场景。 一、K近邻算法&#xff08;K-Nea…...

推送恶意软件的恶意 PowerShell 脚本看起来是人工智能编写的

威胁行为者正在使用 PowerShell 脚本&#xff0c;该脚本可能是在 OpenAI 的 ChatGPT、Google 的 Gemini 或 Microsoft 的 CoPilot 等人工智能系统的帮助下创建的。 攻击者在 3 月份的一次电子邮件活动中使用了该脚本&#xff0c;该活动针对德国的数十个组织来传播 Rhadamanthy…...

微服务之Consul 注册中心介绍以及搭建

一、微服务概述 1.1单体架构 单体架构&#xff08;monolithic structure&#xff09;&#xff1a;顾名思义&#xff0c;整个项目中所有功能模块都在一个工程中开发&#xff1b;项目部署时需要对所有模块一起编译、打包&#xff1b;项目的架构设计、开发模式都非常简单。 当项…...

MES生产管理系统:私有云、公有云与本地化部署的比较分析

随着信息技术的迅猛发展&#xff0c;云计算作为一种新兴的技术服务模式&#xff0c;已经深入渗透到企业的日常运营中。在众多部署方式中&#xff0c;私有云、公有云和本地化部署是三种最为常见的选择。它们各自具有独特的特点和适用场景&#xff0c;并在不同程度上影响着企业的…...

【core analyzer】core analyzer的介绍和安装详情

目录 &#x1f31e;1. core和core analyzer的基本概念 &#x1f33c;1.1 coredump文件 &#x1f33c;1.2 core analyzer &#x1f31e;2. core analyzer的安装详细过程 &#x1f33c;2.1 方式一 简单但不推荐 &#x1f33c;2.2 方式二 推荐 &#x1f33b;2.2.1 安装遇到…...

个人练习之-jenkins

虚拟机环境搭建(买不起服务器 like me) 重点: 0 虚拟机防火墙关闭 systemctl stop firewalld.service systemctl disable firewalld.service 1 (centos7.6)网络配置 (vmware 编辑 -> 虚拟网络编辑器 -> 选择NAT模式 ->NAT设置查看网关) vim /etc/sysconfig/network-sc…...

初探vercel托管项目

文章目录 第一步、注册与登录第二步、本地部署 在个人网站部署的助手vercel&#xff0c;支持 Github部署&#xff0c;只需简单操作&#xff0c;即可发布&#xff0c;方便快捷&#xff01; 第一步、注册与登录 进入vercel【官网】&#xff0c;在右上角 login on&#xff0c;可登…...

软考 - 系统架构设计师 - 质量属性例题 (2)

问题1&#xff1a; 、 问题 2&#xff1a; 系统架构风险&#xff1a;指架构设计中 &#xff0c;潜在的&#xff0c;存在问题的架构决策所带来的隐患。 敏感点&#xff1a;指为了实现某个质量属性&#xff0c;一个或多个构件所具有的特性 权衡点&#xff1a;指影响多个质量属性…...

基于Python豆瓣电影数据可视化分析系统的设计与实现

大数据可视化项目——基于Python豆瓣电影数据可视化分析系统的设计与实现 2024最新项目 项目介绍 本项目旨在通过对豆瓣电影数据进行综合分析与可视化展示&#xff0c;构建一个基于Python的大数据可视化系统。通过数据爬取收集、清洗、分析豆瓣电影数据&#xff0c;我们提供了…...

【已开源】​基于stm32f103的爬墙小车

​基于stm32f103的遥控器无线控制爬墙小车&#xff0c;实现功能为可平衡在竖直墙面上&#xff0c;并进行移动和转向&#xff0c;具有超声波防撞功能。 直接上&#xff1a; 演示视频如&#xff1a;哔哩哔哩】 https://b23.tv/BzVTymO 项目说明&#xff1a; 在这个项目中&…...

PCL 基于马氏距离KMeans点云聚类

文章目录 一、简介二、算法步骤三、代码实现四、实现效果参考资料一、简介 在诸多的聚类方法中,K-Means聚类方法是属于“基于原型的聚类”(也称为原型聚类)的方法,此类方法均是假设聚类结构能通过一组原型刻画,在现实聚类中极为常用。通常情况下,该类算法会先对原型进行初始…...

libVLC 视频窗口上叠加透明窗口

很多时候&#xff0c;我们需要在界面上画一些三角形、文字等之类的东西&#xff0c;我们之需要重写paintEvent方法&#xff0c;比如像这样 void Widget::paintEvent(QPaintEvent *event) 以下就是重写的代码。 void Widget::paintEvent(QPaintEvent *event) {//创建QPainte…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统

核心速览 研究背景 ​​研究问题​​&#xff1a;这篇文章要解决的问题是当前大型语言模型&#xff08;LLMs&#xff09;在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色&#xff0c;但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成&#xff08;RA…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...

组合模式:构建树形结构的艺术

引言:处理复杂对象结构的挑战 在软件开发中,我们常遇到需要处理部分-整体层次结构的场景: 文件系统中的文件与文件夹GUI中的容器与组件组织结构中的部门与员工菜单系统中的子菜单与菜单项组合模式正是为解决这类问题而生的设计模式。它允许我们将对象组合成树形结构来表示&…...