tsp.m

来自「本程序是利用神经网络来计算五个城市的最短距离」· M 代码 · 共 125 行

%初始化t,a,d
clear
t=0;
a=50;
d=1;
%五个城市之间的距离矩阵
dxy=[0,7,6,10,13;
    7,0,7,10,10;
    6,7,0,5,9;
    10,10,5,0,6;
    13,10,9,6,0];
%当i==j,r(i,j)==1,否则，r(i,j)为0
r=[1,0,0,0,0;
   0,1,0,0,0;
   0,0,1,0,0;
   0,0,0,1,0;
   0,0,0,0,1];
%计算偏置矩阵I及权重矩阵T
I=2*a*ones(5);
dtu=zeros(5);
for x=1:1:5
    for i=1:1:5
        for y=1:1:5
          for j=1:1:5
        im=mod(i,5);
       T(x,i,y,j)=-a*r(x,y)-a*r(i,j)-d*dxy(x,y)*r(j,im+1);
          end
       end
    end 
end
%设置初始值u
u0=0.02;
u=0.2*rand(5,5)-0.1;
E=0;
EB=0;
ee=1;
sumv=0;
%当系统达到平衡（相邻两次的能量函数差值ee为0），
%最短路径矩阵中每行只有一个1（即：sumx==ones(1,5))，
%每列只有一个1（即：sumy==ones(1,5))，
%所有元素加起来共等于5（即：sumv==5)时，输出相应的最短路径矩阵
while (ee~=0) | (sumv~=5) | (sumx~=ones(1,5)) | (sumy~=ones(1,5))
   e1=0;
   e2=0;
   e3=0;
   e11=zeros(1,5);
   e22=zeros(1,5);
   e111=0;
   e222=0;
   v=(1+tanh(u/u0))/2;%计算最短路径矩阵v
   for x=1:1:5
     for i=1:1:5
      eu=0;     
       for y=1:1:5
          for j=1:1:5
            eu=eu+T(x,i,y,j)*v(y,j);
          end
       end
     dtu(x,i)=eu+I(x,i);%产生Δu
     end
    end
    u=u+dtu*0.5;%重新计算u值
    %计算能量函数的值
    for x=1:1:5
     for i=1:1:5
      e1=e1+v(x,i);
     end
    e11(x)=(e1-1).^2;
   end   
   for i=1:1:5
     for x=1:1:5
      e2=e2+v(x,i);
     end
     e22(i)=(e2-1).^2;
   end 
   for x=1:1:5
     for y=1:1:5
       for i=1:1:5
       im=mod(i,5);
       e3=e3+dxy(x,y)*v(x,i)*v(y,im+1);
       end
     end
    end 
    for x=1:1:5
      e111=e111+e11(x);
      e222=e222+e22(x);
    end
   E=a/2*(e111+e222)+d/2*e3;%计算能量函数的值
   ee=abs(E-EB);%相邻两次的能量函数差值
   sumv=0;
   sumy=zeros(1,5);
   sumx=zeros(1,5);
   for x=1:1:5
     for y=1:1:5
       sumy(y)=sumy(y)+v(y,x);%最短路径矩阵v每列元素的和
       sumx(x)=sumx(x)+v(x,y);%最短路径矩阵v每行元素的和
       sumv=sumv+v(x,y);%最短路径矩阵v所有元素的和
     end
   end
   EB=E;
end
  line=[1 2 3 4 5]*v %输出最短路径
  minline=0;
  for i=1:1:5
    j=mod(i,5)+1;
    minline=minline+dxy(line(i),line(j));
  end
  minline %输出最短路径的值
  %显示并画出最短路径
  x=0.2:0.2:1;
  y=[0.5 0.7 0.3 0.9 0.2];%假设有五个点
  y1=y+0.05;
  wx=[x(line(1)) x(line(2)) x(line(3)) x(line(4)) x(line(5)) x(line(1))];
  wy=[y(line(1)) y(line(2)) y(line(3)) y(line(4)) y(line(5)) y(line(1))];
  plot(wx,wy,'--or','LineWidth',2, 'MarkerSize',10);
  text(x(1),y1(1),['1']);
  text(x(2),y1(2),['2']);
  text(x(3),y1(3),['3']);
  text(x(4),y1(4),['4']);
  text(x(5),y1(5),['5']);
  title('TSP问题的最短路径','FontSize',18);
  text(0.3,0.9,['最短距离为',num2str(minline)],'FontSize',18);
  text(0.1,0.1,['最短路径的访问顺序为',num2str(line)],'FontSize',18);
  axis ([0 1.1 0 1]);