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

. 使用实例：