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 1case 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:NdpSheet(m,1)=adjMat(m,1);
end
for m=1:2^(N-1)for n=1:NbinNum=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);endendend
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);endendcirclePath=[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

.
使用实例：