tspgreedy.m

清华大学运筹学课件

clc,clear
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(6,:)=0;
a=a+a';
c1=[5 1:4 6];
L=length(c1);
flag=1;
while flag>0
      flag=0;
   for m=1:L-3
      for n=m+2:L-1
        if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
           flag=1;
           c1(m+1:n)=c1(n:-1:m+1);
        end
     end
  end
end
sum1=0;
for i=1:L-1
   sum1=sum1+a(c1(i),c1(i+1));
end
circle=c1;
sum=sum1;

%%%%%%%%%%%%%%%%%%%%%%%%

c1=[5 6 1:4]; % 改变初始圈，该算法的最后一个顶点不动
flag=1;
while flag>0
      flag=0;
   for m=1:L-3
      for n=m+2:L-1
         if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...
               a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
           flag=1;
           c1(m+1:n)=c1(n:-1:m+1);
        end
     end
  end
end
sum1=0;
for i=1:L-1
   sum1=sum1+a(c1(i),c1(i+1));
end
if sum1<sum
   sum=sum1;
   circle=c1;
end
circle,sum