首页 > 其他分享 >蒙特卡洛模拟(6)————旅行商问题

蒙特卡洛模拟(6)————旅行商问题

时间:2024-08-07 18:55:18浏览次数:12  
标签:旅行 min 城市 coord result path 蒙特卡洛 模拟

旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。

目录

一、问题提出

二、代码预备

1.plot([a,b],[c,d])

plot([1,2],[5,10],'-o')
画出一条线段,x范围是[1, 2] ,y范围是[5,10]。这个命令用来实现坐标之间的连接

2.randperm(n)

randperm(5)
生成由1-5组成的一个随机序列(类似于洗牌的操作)
ans= 3 5 1 2 4

三、代码实现

1.输入城市坐标数据

下方是只有是个数据的简单情况:第一行是所有数据的横坐标,第二行则是纵坐标。
经过转置之后,就变成了横轴是城市编号,纵轴的第一列是城市横坐标,第二列则是纵坐标。
这样就可以用n来提取行数,得到城市的数目

coord =[0.6683 0.6195 0.4    0.2439 0.1707 0.2293 0.5171 0.8732 0.6878 0.8488 ;
               0.2536 0.2634 0.4439 0.1463 0.2293 0.761  0.9414 0.6536 0.5219 0.3609]' ;
n = size(coord,1);  % 城市的数目

2.画出城市的分布散点图

利用循环和num2str命令给城市标号

figure(1)  % 新建一个编号为1的图形窗口
plot(coord(:,1),coord(:,2),'o');   % 画出城市的分布散点图
for i = 1:n
    text(coord(i,1)+0.01,coord(i,2)+0.01,num2str(i))   % 在图上标上城市的编号(加上0.01表示把文字的标记往右上方偏移一点)
end
hold on % 等一下要接着在这个图形上画图的

3.得到城市距离矩阵

这个方法非常巧妙,如果遍历计算得到距离矩阵,是需要把每个城市之间的距离算两遍的,而经过下面的循环则避免了算两遍导致计算速度下降的情况。
首先行i从2开始,列j则从1到i。这样则避免了重复计算,最后算出来的是一个下三角矩阵。由于对角线上的元素均为0,通过转置则得到了一个上三角矩阵,将其相加就得到了完整的距离矩阵

d = zeros(n);   % 初始化两个城市的距离矩阵全为0
for i = 2:n  
    for j = 1:i  
        coord_i = coord(i,:);   x_i = coord_i(1);     y_i = coord_i(2);  % 城市i的横坐标为x_i,纵坐标为y_i
        coord_j = coord(j,:);   x_j = coord_j(1);     y_j = coord_j(2);  % 城市j的横坐标为x_j,纵坐标为y_j
        d(i,j) = sqrt((x_i-x_j)^2 + (y_i-y_j)^2);   % 计算城市i和j的距离
    end
end
d = d+d';

4.变量初始化

min_result = +inf;  % 假设最短的距离为min_result,初始化为无穷大,后面只要找到比它小的就对其更新
min_path = [1:n];   % 初始化最短的路径就是1-2-3-...-n
N = 10000000;  % 蒙特卡罗模拟的次数

5.进入循环,开始模拟

代码思想是蒙特卡洛模拟的常用思想,生成一个随机序列后,提取序列的索引进行数值相加得到总距离,最后进入判断,更新最优方案

for k = 1:N  % 开始循环
    result = 0;  % 初始化走过的路程为0
    path = randperm(n);  % 生成一个1-n的随机打乱的序列
    for i = 1:n-1  
        result = d(path(i),path(i+1)) + result;  % 按照这个序列不断的更新走过的路程这个值
    end
    result = d(path(1),path(n)) + result;  % 别忘了加上从最后一个城市返回到最开始那个城市的距离
    if result < min_result  % 判断这次模拟走过的距离是否小于最短的距离,如果小于就更新最短距离和最短的路径
        min_path = path;
        min_result = result
    end
end

6.得到结果

此处就用到了最初预备知识中,绘制坐标的命令

min_path
min_path = [min_path,min_path(1)];   % 在最短路径的最后面加上一个元素,即第一个点(我们要生成一个封闭的图形)
n = n+1;  % 城市的个数加一个(紧随着上一步)
for i = 1:n-1 
     j = i+1;
    coord_i = coord(min_path(i),:);   x_i = coord_i(1);     y_i = coord_i(2); 
    coord_j = coord(min_path(j),:);   x_j = coord_j(1);     y_j = coord_j(2);
    plot([x_i,x_j],[y_i,y_j],'-')    % 每两个点就作出一条线段,直到所有的城市都走完
    pause(0.5)  % 暂停0.5s再画下一条线段
    hold on
end

五、模型优化

蒙特卡罗模拟是通过生成随机数来代替遍历计算的方法,但如果数量级过大,蒙特卡洛模拟也难以找到较好的解。本实验的城市数目只有10个,但其实换成30个,还用此方法就很难实现了。因为可能情况太多,即使通过模拟也难以找到最优的情况。
当遇到数量级过多的情况,需要启发式算法来解决。当然,另一种思路,也可以通过聚类分析,把距离相近的城市聚类为一类,然后再进行模拟,这种方法不如启发式算法

标签:旅行,min,城市,coord,result,path,蒙特卡洛,模拟
From: https://www.cnblogs.com/dlmuwxw/p/18347619

相关文章

  • 使用Streamlit构建一个web模拟HTTP请求工具
    目录前言HTTP工具功能点:1.导入库: 2.设置页面配置:3.Markdown格式的说明文本:4.用户输入界面:5.发送请求按钮和逻辑:6.发送HTTP请求并计算请求细节:7.总结 前言    最初就是因为在微信看到一篇文章中,看到此http工具的制作因为觉得Streamlit有无限......
  • [赛记] 暑假集训CSP提高模拟15
    原题还是没找串串49pts用的$manacher$,板子差点没打对,但好歹还是打对了。。。赛时写的时候没有考虑到不用管偶回文,导致递归的时候有点问题。。。其实根本用不到递归,将循环顺序改为倒序即可;有三种情况:回文半径+位置能够到达右端点;显然,这种情况是合法的;既到不了左......
  • fiddler - 对模拟器app抓包配置
    1.fiddler部分tools》options中, 这几个配置勾选跟我的一致,端口使用8888 然后导出证书 会导出到桌面 然后pc授信证书 然后重启fiddler 2.模拟器部分将证书拉入模拟器,然后点击证书安装,输入的名称可以随便写然后打开wlan,对wifi的修改代理为手动【模拟器有些......
  • 2024.8.7 模拟赛题解
    T1过于简单,不必阐述。T2给定一个仅包含\(A\)和\(P\)的字符串,每次操作可以删除相邻的\(AP\)或者\(PP\),问字符串最后的最小长度。$Sol:$为求最值问题,考虑贪心。先给出考场做法。发现若干的\(P\)是一定能合并掉的,于是贪心策略,就是如何最小化\(A\)的个数。对于每个......
  • 暑假集训CSP提高模拟15
    \[\color{red}{\huge囍挂111pts}\]叠词词恶心心T1串串一眼马拉车。我们来看看只翻转一次后就能得到答案的情况,就是如果某个位置的回文长度能到达这个字符串的末尾,那这个位置肯定能做翻转位置的,但是这种情况出现的位置只能在后半部分。如果是翻转多次的话,那么位置只能出现在......
  • 使用Cisco进行模拟配置OSPF路由协议
    OSPF路由协议1.实验目的1)理解OSPF2)掌握OSPF的配置方法3)掌握查看OSPF的相关信息2.实验流程开始→布置拓扑→配置IP地址→配置OSPF路由并验证PC路由的连通性→查看路由器路由信息→查看路由协议配置与统计信息→查看OSPF进程及区域信息→查看路由器OSPF数......
  • 在Python中抽象出具有相同接口的真实硬件和模拟设备
    我正在寻找一种更惯用或更简洁的OOP模式来实现与以下内容等效的功能。接口和实现fromabcimportABC,abstractmethodfromtypingimportoverrideclassDevice:"""Maininterfacethathideswhetherthedeviceisarealhardwaredeviceorasimulated......
  • 【题解】暑假集训CSP提高模拟14
    目录Rank&挂分A.BA题目内容部分分10pts10+20pts正解思路代码B.BB题目内容部分分5pts正解思路代码C.BCD.BDRank&挂分T4暴搜后来改了记搜,不知道哪里锅了,挂5pts。A.BA题目内容现在有\(m\)块烙板,\(n\)张饼,第\(i\)张饼需要烙\(a_i\)个单位时间,一张饼一个单位时刻只能......
  • Type-C协议(CC检测原理)-CC1和CC2接电阻-数字和模拟耳机兼容
    1简介USBType-C其实是USB的一种接口形态,USB的接口形态可以分为USBType-A、USBType-B、USBType-C,USBType-A和USBType-B还有两种不同规格的接口形态,分别是USBMini-A(B)和USBMicro-A(B)。USB各型号接口图解越来越多的手机开始采用Type-C作为充电和通信端口,Type-C连接器......
  • 蒙特卡洛模拟(5)————导弹追踪问题
    本章会介绍如何用数值模拟的方法解决导弹追踪问题目录一、问题提出二、建立示意图三、模型建立1.建立坐标轴(1)建立B船坐标(2)建立导弹坐标2.设置delta_t,进行模拟四、代码求解1.预备知识(1)mod(m,n)(2)axis([mnpq])(3)text(m,n,'xxx')2.变量初始化3.初始化画图参数4.进入循环,开始模拟(1)进......