数学建模常用Matlab/Lingo/c代码总结系列——hamilton回路

  提供一种求解最优哈密尔顿的算法---三边交换调整法，要求在运行jiaohuan3（三交换法）之前，给定邻接矩阵C和节点个数N，结果路径存放于R中。
  bianquan.m文件给出了一个参数实例，可在命令窗口中输入bianquan,得到邻接矩阵C和节点个数N以及一个任意给出的路径R,，回车后再输入jiaohuan3,得到了最优解。

由于没有经过大量的实验，又是近似算法，对于网络比较复杂的情况，可以尝试多运行几次jiaohuan3,看是否能到进一步的优化结果。

%%%%%%bianquan.m%%%%%%%
N=13;
for i=1:N
    for j=1:N
        C(i,j)=inf;
    end
end
for i=1:N
    C(i,i)=0;
end
C(1,2)=6.0;C(1,13)=12.9;
C(2,3)=5.9;C(2,4)=10.3;
C(3,4)=12.2;C(3,5)=17.6;
C(4,13)=8.8;C(4,7)=7.4;
C(4,5)=11.5;
C(5,2)=17.6;C(5,6)=8.2;
C(6,9)=14.9;C(6,7)=20.3;
C(7,9)=19.0;C(7,8)=7.3;
C(8,9)=8.1;C(8,13)=9.2;
C(9,10)=10.3;
C(10,11)=7.7;
C(11,12)=7.2;
C(12,13)=7.9;
for i=1:N
    for j=1:N
        if  C(i,j) < inf
            C(j,i)=C(i,j);
        end
    end
end
for i=1:N
    C(i,i)=0;
end

R=[4 7 6 5 3 2 1 13 12 11 10 9 8];

%%%%%%%%jiaohuan3.m%%%%%%%%%%n=0;for I=1:(N-2)    for J=(I+1):(N-1)        for K=(J+1):N            n=n+1;            Z(n,:)=[I J K];        end    endendR=1:Nfor m=1:(N*(N-1)*(N-2)/6)    I=Z(m,1);J=Z(m,2);K=Z(m,3);    r=R;    if J-I~=1&K-J~=1&K-I~=N-1        for q=1:(J-I)            r(I+q)=R(J+1-q);        end        for q=1:(K-J)            r(J+q)=R(K+1-q);        end    end    if J-I==1&K-J==1        r(K)=R(J);r(J)=R(K);    end    if J-I==1&K-J~=1&K-I~=N-1        for q=1:(K-J)            r(I+q)=R(I+1+q);        end        r(K)=R(J);    end    if K-J==1&J-I~=1&K~=N        for q=1:(J-I)            r(I+1+q)=R(I+q);        end        r(I+1)=R(K);    end    if I==1&J==2&K==N        for q=1:(N-2)            r(1+q)=R(2+q);        end        r(N)=R(2);    end    if I==1&J==(N-1)&K==N        for q=1:(N-2)            r(q)=R(1+q);        end        r(N-1)=R(1);    end    if J-I~=1&K-I==N-1        for q=1:(J-1)            r(q)=R(1+q);        end        r(J)=R(1);    end    if J==(N-1)&K==N&J-I~=1        r(J+1)=R(N);        for q=1:(N-J-1)            r(J+1+q)=R(J+q);        end    end    if cost_sum(r,C,N)<cost_sum(R,C,N)        R=r    endendfprintf('总长为%f\n',cost_sum(R,C,N))
%%%%%%cost_sum.m%%%%%%%%function y=cost_sum(x,C,N)y=0;for i=1:(N-1) y=y+C(x(i),x(i+1));endy=y+C(x(N),x(1));