MATLAB 旅行商问题（动态规划法）程序

利用亲子旅游指南或应用程序规划行程 #生活乐趣# #旅行建议# #家庭友好旅行#

具体实现方法可以参考这一篇呀：
旅行商问题（动态规划方法，超级详细的）
在这就不细说了

直接看代码：
完整代码：

function [circle,dis]=minCycle_dp(adjMat,pntSet,startPnt) %该函数使用动态规划法求解旅行商问题，点数不宜过多 %变量 类型 　释义 %====================================================== %adjMat | 矩阵 | 临接矩阵（Adjacency matrix） %pntSet　 | 向量 | 各个点编号集合，无输入默认为1:N %startPnt | 数值 | 圈起始点，无输入默认编号集的第一个 %------------------------------------------------------ %circle　 | 向量 | 路径最小圈 %dis | 数值 | 最短路程 %实例： %adjMat=[0 3 inf 8 9; % 3 0 3 10 5; % inf 3 0 4 3; % 8 10 4 0 20; % 9 5 3 20 0]; % % 邻接矩阵 编号 % ↓ ↓ %[circle,dis]=minCycle_dp(adjMat,(0:4)) %-------------------------- %实例运行结果： %circle = % 0 1 4 2 3 0 %dis = % 23 %输入变量的初步处理、缺省参数赋值========================================== N=size(adjMat,1); switch 1 case nargin==1,pntSet=1:N;startPnt=1; case nargin==2,startPnt=pntSet(1); end pntSet=pntSet(:); %动态规划法程序主要部分：dp数组表格计算==================================== dpSheet=inf.*ones(N,2^(N-1)); for m=1:N dpSheet(m,1)=adjMat(m,1); end for m=1:2^(N-1) for n=1:N binNum=dec2bin(m-1); binNum=binNum(length(binNum):-1:1); comSet=find(binNum=='1'); for k=1:length(comSet) subSet=comSet; subSet(subSet==comSet(k))=[]; decNum=sum(2.^(subSet-1))+1; if dpSheet(n,m)>adjMat(n,comSet(k)+1)+dpSheet(comSet(k)+1,decNum) dpSheet(n,m)=adjMat(n,comSet(k)+1)+dpSheet(comSet(k)+1,decNum); end end end end %通过dp数组表格还原路径==================================================== circlePath=1; comSet=2:N; while ~isempty(comSet) tempNum=1; tempD=inf; for m=1:length(comSet) subSet=comSet; subSet(subSet==comSet(m))=[]; decNum=sum(2.^(subSet-2))+1; if tempD>adjMat(circlePath(end),comSet(m))+dpSheet(comSet(m),decNum) tempD=adjMat(circlePath(end),comSet(m))+dpSheet(comSet(m),decNum); tempNum=comSet(m); end end circlePath=[circlePath,tempNum]; comSet(comSet==tempNum)=[]; end %为圈中节点赋予编号，改变圈起点，计算圈总长================================ circle=pntSet(circlePath)'; startPntPos=find(circle==startPnt); circle=[circle(startPntPos:end),circle(1:startPntPos)]; dis=sum(adjMat((circlePath-1)*N+circlePath([end 1:(end-1)]))); end

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687

.
使用实例：

网址：MATLAB 旅行商问题（动态规划法）程序 https://www.yuejiaxmz.com/news/view/488488

相关内容

旅行商问题（动态规划方法，超级详细的）
基于麻雀搜索算法的线性规划问题求解matlab程序
旅游路线规划：用数学建模优化旅行体验
程序员如何用技术解决旅行的规划问题
算法动态规划01背包问题
旅行商问题+背包问题
动态规划在实际生活中的应用
【创新未发表】基于鱼鹰OOA求解带时间窗的骑手外卖配送路径规划问题，最优路径成本附Matlab代码
动态规划问题dp问题以及经典问题
动态规划特训：旅行商问题（回溯法或记忆搜索法）

随便看看