%ants 算法求解tsp，c為鄰接矩陣,p is the start city
function [minrout,minlen]=ants(c,p)
num=20;% ants number
t=100; %the times of overcover
hs=0.1;% huisanxishu
a1=1;%初始信息素系數
%p_sum=p_sum+tao(np,j)^alpha*ada^beta;
[mm,nn]=size(c);
infc=zeros(nn,nn)+a1/mm;%初始信息素
a=find(c>1e5);
infc(a)=0;
for i=1:nn
    infc(i,i)=0;
end
routall=zeros(num,mm);
for i=1:t
    routall=creatroute(c,infc,p);
    [minlen1,routmin,lengall]=minlenth(routall,c);
    infc=infcc(lengall,infc,routall);
end
minrout=routmin;
minlen=minlen1;
%求當前最短路
function [minlen1,routmin,lengall]=minlenth(rr,c)%rr is all-route,c is 鄰接矩陣，minlen1 is the shortest length,
%routmin is the minrout,lengall is the all of the length.
[m1,n1]=size(rr);
lengall=zeros(m1,1);
routmin=zeros(1,n1);
for i=1:m1
   for j=1:(n1-1)
   lengall(i)=lengall(i)+c(rr(i,j),rr(i,j+1));
   end
   lengall(i)=lengall(i)+c(rr(i,m1),1);
end
minlen1=min(lengall);
routmin=rr(find(lengall==minlen1),:);

%信息素分配 ：lengall 是所生成的距離，rr1是所生成的路由，inf是當前信息素矩陣
function infc1=infcc(lengall1,infc,rr1)
[m1,n1]=size(rr1);
infc1=infc;
Q=1;
for i=1:m1
    for j=1:n1-1
    infc1(rr1(i,j),rr1(i,j+1))=infc1(rr1(i,j),rr1(i,j+1))+Q/lengall1(i);
    infc1(rr1(i,j+1),rr1(i,j))=infc1(rr1(i,j+1),rr1(i,j))+Q/lengall1(i);
    end
    infc1(rr1(i,n1),1)= infc1(rr1(i,n1),1)+Q/lengall1(i);
    infc1(1,rr1(i,n1))= infc1(1,rr1(i,n1))+Q/lengall1(i);
end

%creat new route    r is all routes 
function r=creatroute(c,infc11,pp)
[m2,n2]=size(infc11);
r=zeros(m2,n2);
p1=zeros(1,n2);
for i=1:m2
    l=[];
    l(1)=pp;
    for j=2:n2
        aa=rand;
        p1=cumsum(infc11(:,l(j-1)))./sum(infc11(:,l(j-1)));
        b=find(p1-aa>=0);
        l=[l,b(1)];
        for k=1:n2
            if sum(ismember(l(1:j-1),l(j)))~=0
                aa=rand;
                b=find(p1-aa>0);
                l(j)=b(1);
            end
        end
    end
      r(i,:)=l;
end