【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, &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的机器学习模块。