[数据结构与算法]基于动态规划解决TSP旅行商问题

标题

TSP（Traveling Salesman Problem）旅行商问题的概念，基于动态规划**算法实现的基本原理我就不再赘述了，下面的文章讲的很好了。如果还看不明白的话，建议好好看看司守奎的黄皮书，理解动态规划的思想。

https://blog.csdn.net/joekwok/article/details/4749713

想分享的是递归实现的一种思路，理解了动态规划求解TSP的基本原理之后，会发现，计算相邻两个状态的距离d可以同归递归求解。

直接附上代码吧（仅作分享交流，大佬勿喷）：

TSP.m

% 基于动态规划解决TSP问题
function y =TSP(c,s)
% c是代价矩阵
% s是起始地点
% 输出y为最小花费
[m,~]=size(c);
v=1:m;
y=d(s,v,c);
end

d.m

% 基于递归的方法
% 计算相邻两个状态的距离d
function result=d(s,v,c)
v(v==s)=[];
if isempty(v)==1
    result = c(s,1);
else 
    [~,m]=size(v);
    flag = 1000;   % 设置一个较大的值进行比较
    for i =1:m     %遍历可行的方案选出最优方案
        if ( c(s,v(i))+d(v(i),v,c) ) <flag
            flag = c(s,v(i))+d(v(i),v,c);
        end
    end
    result = flag;   
end
end

测试主函数

clc,clear
c=[0,3,6,7;5,0,2,3;6,4,0,2;3,7,5,0];
s=1;
y=TSP(c,s);
disp(['最少花费为：   ',num2str(y)])

输出结果：

最少花费 路径依次是 1->2->3->4 可以自己思考一下返回正确路径

动态规划本质上还是遍历了全部可行的路径比较，对于大规模的TSP建议还是利用遗传算法、模拟退火等智能优化算法求解。