参考书籍

参考司守奎写的数学建模算法与应用中的58页内容，并且对书中的代码进行详细解释。

注意事项

MATLAB代码

clc,clear
%旅行商问题简单来说就是计算出发地经过若干地点再返回原地的最短路径
% 这个程序围绕数学建模书59页问题,从地点5开始出发，最后再回到地点5
a=zeros(6);  %初始化邻接矩阵
a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;
a(4,5)=51;a(4,6)=61;a(5,6)=13;%对邻接矩阵进行赋值
a=a+a';%利用对称矩阵的性质获得最终得邻接矩阵
L=size(a,1); %获取矩阵的行数，如果是size(a,2)就是获取矩阵的列数
c=[5 1:4 6 5];  %这样写是为了方便，实际上c=[5 1 2 3 4 6 5],这个定义的是初始圈
[circle,long]=modifycircle(a,L,c); %调用下面的修改圈的子函数
circle,long  %注意如果在变量名后面加上分号的话就不会在窗口显示它的值，如果想显示值就不要加分号
function [circle,long]=modifycircle(a,L,c)
    for k=1:L  %因为要走过六个地方，于是要遍历循环
    flag=0;    %预先设置是否知道已经修改了边,如果循环后flag还是0，说明并没有修改初始圈
    long=0;    %初始化总路程
    for m=1:L-2 %因为算法中的i是1<=i<i+1<j<=n,i与n最少差2
        for n=m+2:L %原算法中的j是至少比i大2的
            if a(c(m),c(n))+a(c(m+1),c(n+1))<a(c(m),c(m+1))+a(c(n),c(n+1))%如果修改后的新圈比旧圈权重小
                c(m+1:n)=c(n:-1:m+1);  %将原来的路线倒过来，结合上面讲解的算法
                flag=flag+1;%如果修改了圈就将flag的值加1
            end
        end
    end
    if flag==0  %如果循环结束后都没有修改圈的话
        long=274 %那么所走路线就是初始圈，路程就是初始路线的总路程
    else
        for i=1:L
            long=long+a(c(i),c(i+1)) %遍历更新总路程
        end
        circle=c; %更新路线圈
        return % 在条件块（例如 if 或 switch）或循环控制语句（例如 for 或 while）使用 return 时需要小心。当 MATLAB 到达 return 语句时，它并不仅是退出循环，还退出脚本或函数，并将控制权交还给调用程序或命令提示符。
    end
    end
end

运行结果

long =

    51


long =

    72


long =

   107


long =

   128


long =

   198


long =

   211


circle =

     5     4     1     3     2     6     5


long =

   211