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



// 载入 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, ¤tTemperature, 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深入剖析】深入理解软硬链接 | 动静态库的制作以及使用
🍁你好,我是 RO-BERRY 📗 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 目录 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中,Binding机制是实现数据与界面的连接和同步的重要工具。了解Binding的原理和应用,对于开发人员来说是非常重要的。本文将详细介绍WPF中Binding的原理和应用,帮助读者更好地理解和运用这一强大的机制。 Bin…...
探索设计模式的魅力:深度挖掘响应式模式的潜力,从而精准优化AI与机器学习项目的运行效能,引领技术革新潮流
🌈 个人主页:danci_ 🔥 系列专栏:《设计模式》 💪🏻 制定明确可量化的目标,坚持默默的做事。 挖掘响应式模式,优化AI与机器学习项目性能,引领技术新潮流 ✨机器学习界的…...
《经典论文阅读2》基于随机游走的节点表示学习—Deepwalk算法
word2vec使用语言天生具备序列这一特性训练得到词语的向量表示。而在图结构上,则存在无法序列的难题,因为图结构它不具备序列特性,就无法得到图节点的表示。deepwalk 的作者提出:可以使用在图上随机游走的方式得到一串序列&#x…...
Java实现二叉树(下)
1.前言 http://t.csdnimg.cn/lO4S7 在前文我们已经简单的讲解了二叉树的基本概念,本文将讲解具体的实现 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 ,元素按从小到大的顺序排列,数组不包含重复元素。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素,则返回 -1 。 # 首…...
常见分类算法详解
在机器学习和数据科学的广阔领域中,分类算法是至关重要的一环。它广泛应用于各种场景,如垃圾邮件检测、图像识别、情感分析等。本文将深入剖析几种常见的分类算法,帮助读者理解其原理、优缺点以及应用场景。 一、K近邻算法(K-Nea…...
推送恶意软件的恶意 PowerShell 脚本看起来是人工智能编写的
威胁行为者正在使用 PowerShell 脚本,该脚本可能是在 OpenAI 的 ChatGPT、Google 的 Gemini 或 Microsoft 的 CoPilot 等人工智能系统的帮助下创建的。 攻击者在 3 月份的一次电子邮件活动中使用了该脚本,该活动针对德国的数十个组织来传播 Rhadamanthy…...
微服务之Consul 注册中心介绍以及搭建
一、微服务概述 1.1单体架构 单体架构(monolithic structure):顾名思义,整个项目中所有功能模块都在一个工程中开发;项目部署时需要对所有模块一起编译、打包;项目的架构设计、开发模式都非常简单。 当项…...
MES生产管理系统:私有云、公有云与本地化部署的比较分析
随着信息技术的迅猛发展,云计算作为一种新兴的技术服务模式,已经深入渗透到企业的日常运营中。在众多部署方式中,私有云、公有云和本地化部署是三种最为常见的选择。它们各自具有独特的特点和适用场景,并在不同程度上影响着企业的…...
【core analyzer】core analyzer的介绍和安装详情
目录 🌞1. core和core analyzer的基本概念 🌼1.1 coredump文件 🌼1.2 core analyzer 🌞2. core analyzer的安装详细过程 🌼2.1 方式一 简单但不推荐 🌼2.2 方式二 推荐 🌻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,支持 Github部署,只需简单操作,即可发布,方便快捷! 第一步、注册与登录 进入vercel【官网】,在右上角 login on,可登…...
软考 - 系统架构设计师 - 质量属性例题 (2)
问题1: 、 问题 2: 系统架构风险:指架构设计中 ,潜在的,存在问题的架构决策所带来的隐患。 敏感点:指为了实现某个质量属性,一个或多个构件所具有的特性 权衡点:指影响多个质量属性…...
基于Python豆瓣电影数据可视化分析系统的设计与实现
大数据可视化项目——基于Python豆瓣电影数据可视化分析系统的设计与实现 2024最新项目 项目介绍 本项目旨在通过对豆瓣电影数据进行综合分析与可视化展示,构建一个基于Python的大数据可视化系统。通过数据爬取收集、清洗、分析豆瓣电影数据,我们提供了…...
【已开源】基于stm32f103的爬墙小车
基于stm32f103的遥控器无线控制爬墙小车,实现功能为可平衡在竖直墙面上,并进行移动和转向,具有超声波防撞功能。 直接上: 演示视频如:哔哩哔哩】 https://b23.tv/BzVTymO 项目说明: 在这个项目中&…...
PCL 基于马氏距离KMeans点云聚类
文章目录 一、简介二、算法步骤三、代码实现四、实现效果参考资料一、简介 在诸多的聚类方法中,K-Means聚类方法是属于“基于原型的聚类”(也称为原型聚类)的方法,此类方法均是假设聚类结构能通过一组原型刻画,在现实聚类中极为常用。通常情况下,该类算法会先对原型进行初始…...
libVLC 视频窗口上叠加透明窗口
很多时候,我们需要在界面上画一些三角形、文字等之类的东西,我们之需要重写paintEvent方法,比如像这样 void Widget::paintEvent(QPaintEvent *event) 以下就是重写的代码。 void Widget::paintEvent(QPaintEvent *event) {//创建QPainte…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
智能职业发展系统:AI驱动的职业规划平台技术解析
智能职业发展系统:AI驱动的职业规划平台技术解析 引言:数字时代的职业革命 在当今瞬息万变的就业市场中,传统的职业规划方法已无法满足个人和企业的需求。据统计,全球每年有超过2亿人面临职业转型困境,而企业也因此遭…...
针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
云原生安全实战:API网关Envoy的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口,负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...
Django RBAC项目后端实战 - 03 DRF权限控制实现
项目背景 在上一篇文章中,我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统,为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...
