elicross.m

蚁群算法求解tsp问题后去交叉.数据为att48

function y=elicross(tour)
n=48;
load att482 att482; %data att48
t=att482;
 tour=[ 1  ,   8 ,   9   , 38  , 31  ,  44 ,    7  ,  18   , 36 ,   6   , 37 ,   19 ,   27,    43  ,  17,...
      30 ,   28   ,46    ,12  ,  15 ,  33  ,  20  , 47   , 11 ,  23   , 14 ,  25  ,  13  , 21 ,  32,...
    39 ,   5 ,   48 ,   42,    10,   24,   45   , 35  ,  26  ,   4 ,   2 ,  29 ,   34,     3 ,   22,...
    16 ,   41 ,   40]

subplot(1,2,1); % initial route
%axis([-1 7 -1 7]);
hold on;
for i=1:47
    drawline(t(tour(i),2:3),t(tour(i+1),2:3));
end;
drawline(t(tour(48),2:3),t(tour(1),2:3));
hold off;

%eliminate cross
tour=[tour tour(1)];
disp('tour0=');disp(tour);
for i=1:n-1
    for j=i+2:n
        if iscross(t(tour(i),2:3),t(tour(i+1),2:3),t(tour(j),2:3),t(tour(j+1),2:3))
            disp('tour(i)=');disp(tour(i));disp(tour(i+1));disp(tour(j));disp('tour(j+1)=');disp(tour(j+1));
            m=tour(i+1);tour(i+1)=tour(j);tour(j)=m;
            if (i+2)<(j-1)
                tour=nixu(tour,i+2,j-1);
            end;
             %for k=(i+2):floor((j-1)/2);
             %p=tour(k);  tour(k)=tour(j-i-2-k+1); tour(j-i-2-k+1)=p;
             %end;
           disp('tour='),disp(tour);
            
        end
    end
end

subplot(1,2,2); % initial route

% axis([-1 7 -1 7]);
hold on;
for i=1:48
    drawline(t(tour(i),2:3),t(tour(i+1),2:3));
end;
%drawline(t(tour(5),2:3),t(tour(1),2:3));
hold off;

function b=nixu(b,m,n)
b(m:n)=nixu2(b(m:n));
disp(b);
function a=nixu2(a)
n=length(a);
for i=1:floor(n/2);
 t=a(i);  a(i)=a(n-i+1);  a(n-i+1)=t;
end;
%disp(a);
   

function y=iscross(x,y,z,w)
D=(y(1)-x(1))*(z(2)-w(2))-(z(1)-w(1))*(y(2)-x(2));
m=((z(1)-x(1))*(z(2)-w(2))-(z(1)-w(1))*(z(2)-x(2)))/D;
n=((y(1)-x(1))*(z(2)-x(2))-(z(1)-x(1))*(y(2)-x(2)))/D;
if x(1)==w(1)&x(2)==w(2)
    y=0;
elseif D==0
    y=0;
else 
    if m>=0&m<=1&n>=0&n<=1
      y=1;
   else y=0;
   end;
end;
%% 画出二维空间中以点 X 和点 Y 为端点的直线
function y=drawline(x,y)
delx=y(1)-x(1);
dely=y(2)-x(2);
if delx==0
    if dely==0
        error('the same point!');
    elseif dely>0
        t=x(2):dely/100:y(2);
        s=x(1)*ones(size(t));
        plot(s,t);
    else
        t=y(2):abs(dely/100):x(2);
        s=x(1)*ones(size(t));
        plot(s,t);
    end
elseif delx>0
    if dely==0
        s=x(1):delx/100:y(1);
        t=x(2)*ones(size(s));
        plot(s,t);
    else
        s=x(1):delx/100:y(1);
        t=dely/delx.*(s-x(1))+x(2);
        plot(s,t);
    end
else
    if dely==0
        s=y(1):delx/100:x(1);
        t=x(2)*ones(size(s));
        plot(s,t);
    else
        s=y(1):abs(delx/100):x(1);
        t=dely/delx.*(s-x(1))+x(2);
        plot(s,t);
    end
end
%a=[1 2 3 4 5];
%n=5;
%for i=1:floor(n/2);
 %  t=a(i);  a(i)=a(n-i+1);  a(n-i+1)=t;
 %end;
 %disp(a);