wdm.cpp

一个蚁群算法的简单实现。10*10格子中用蚁群算法实现路径寻找。

#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 
#include <iostream.h>

#define ro 0.2

struct MaYi
{
int road[100];
int l;
int life;
int flag[10][10];
};


int main(void) 
{ 
	int mn=0,key=0;
	int direction,opti;
	double total=0,sd[8]={0,0,0,0,0,0,0,0};
	int bushu;
	int i,i1,j,j1,k,k1,minl,mini,minr[50],m=10;
	int di[8]={0,1,1,1,0,-1,-1,-1};
	int dj[8]={1,1,0,-1,-1,-1,0,1};
	int M[10][10];
	int Ant[100][5];/////到达局部最短路径的蚂蚁
	int b1,b2;
	MaYi mayi[20];
	double P[10][10];
	time_t t;
	while(key!=1)
{
	///////////////////////////////
	for(i=0;i<10;i++)
		for(j=0;j<10;j++)
		{
			M[i][j]=0;
//			for(k=0;k<5;k++)
//			Ant[i*10+j][k]=0;
		}


	///////////////////////////////

	srand((unsigned)time(&t));
	for(i=0;i<30;i++)
	{
		k=rand()%100;
		if(M[k/10][k%10]==0)
		{
			M[k/10][k%10]=1;
		}
		else
			i--;
	}

	///////////////////////////////
	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
		{
		 	printf("%d ",M[i][j]);
			P[i][j]=0.2;
			
		}
		printf("\n");
	}
//////////////////////////////////////
///////蚂蚁初始化/////////////////////
//////////////////////////////////////
	b1=0;
	while(M[b1/10][b1%10]==1) b1++;   
	b2=100;
    while(M[b2/10][b2%10]==1) b2--;


	for(k=0;k<2*m;k++) 
	{
		for(i=0;i<10;i++)
		for(j=0;j<10;j++)
		{
		    mayi[k].flag[i][j]=0;
		}
	    if(k<m)
		{
			mayi[k].road[0]=b1;
			mayi[k].flag[b1/10][b1%10]=1;
		}
		else
		{
			mayi[k].road[0]=b2;
			mayi[k].flag[b2/10][b2%10]=1;
		}
		mayi[k].l=0;
		mayi[k].life=1;
		
	}

//////////////////////////////////////
	
	
	minl=1000;

for(opti=0;opti<50;opti++)
{
    mini=minl;

	i=b1/10;j=b1%10;
	i1=b2/10;j1=b2%10;
	for(i=0;i<100;i++)
		for(k=0;k<5;k++)
			Ant[i][k]=0;

    for(bushu=0;bushu<50;bushu++)
	{
		////////////////////////
		///头蚂蚁1/////////////
		///////////////////////
		
		
	   for(mn=0;mn<10;mn++)
	   {
		if(mayi[mn].life==1)
		{
			i=mayi[mn].road[mayi[mn].l]/10;
			j=mayi[mn].road[mayi[mn].l]%10;
		total=0;
		for(k=0;k<8;k++)
			sd[k]=0;
		for(k=0;k<8;k++)
		{
			if((i+di[k]<0)||(i+di[k]>9)||(j+dj[k]<0)||(j+dj[k]>9))
			{
				continue;
			}
			else if(M[i+di[k]][j+dj[k]]==1)
			{
				P[i+di[k]][j+dj[k]]=0;
			}
			else
			if(mayi[mn].flag[i+di[k]][j+dj[k]]==0)
			{
				total+=P[i+di[k]][j+dj[k]];
				sd[k]=total;
			}
		}
			direction=rand()%160;
		 for(k=0;k<8;k++)		
			if (direction<160*sd[k]/total)
				{					
					mayi[mn].l++;
					mayi[mn].road[mayi[mn].l]=(i+di[k])*10+j+dj[k];
					
					i+=di[k];
					j+=dj[k];
					mayi[mn].flag[i][j]=1;

                    if(Ant[i*10+j][0]==0) 
					{
						Ant[i*10+j][0]=mn;
                        Ant[i*10+j][3]=mayi[mn].l;
					}
					if(Ant[i*10+j][1]!=0) Ant[i*10+j][2]=1;
					break;
				}
			if((i==b2/10)&&(j==b2%10)) 
			{
				mayi[mn].life=2;
			}
			if(k==8)
			{
				mayi[mn].life=0;
			}


		}
	   }

	


			/////底部蚂蚁2////////


			
	   for(mn=m;mn<m+10;mn++)
	   {
		if(mayi[mn].life==1)
		{
			i1=mayi[mn].road[mayi[mn].l]/10;
			j1=mayi[mn].road[mayi[mn].l]%10;
			total=0;
		for(k1=0;k1<8;k1++)
			sd[k1]=0;
		
		for(k1=0;k1<8;k1++)
		{
			if((i1+di[k1]<0)||(i1+di[k1]>9)||(j1+dj[k1]<0)||(j1+dj[k1]>9))
			{
				continue;
			}
			else if(M[i1+di[k1]][j1+dj[k1]]==1)
			{
				P[i1+di[k1]][j1+dj[k1]]=0;
			}
			else if(mayi[mn].flag[i1+di[k1]][j1+dj[k1]]==0)
			{
				total+=P[i1+di[k1]][j1+dj[k1]];
				sd[k1]=total;

			}
		}

		direction=rand()%160;
		 for(k1=0;k1<8;k1++)		
			if (direction<160*sd[k1]/total)
				{
			
					mayi[mn].l++;
					mayi[mn].road[mayi[mn].l]=(i1+di[k1])*10+j1+dj[k1];
								
					i1+=di[k1];
					j1+=dj[k1];
					mayi[mn].flag[i1][j1]=1;
					if(Ant[i1*10+j1][1]==0) 
					{
						Ant[i1*10+j1][1]=mn;
						Ant[i1*10+j1][4]=mayi[mn].l;
					}
					if(Ant[i1*10+j1][0]!=0) Ant[i1*10+j1][2]=1;
					break;
				}
			if((i1==b1/10)&&(j1==b1%10)) 
			{
				mayi[mn].life=2;

			}
			if(k==8)
			{
				mayi[mn].life=0;

			}

		}
	   }
	  
   }
////////////因为相遇找到最优解//////////////////////////////
     for(i=0;i<100;i++)      
		   if((Ant[i][2]==1)&&((Ant[i][3]+Ant[i][4])<minl))
		   {
			   minl=Ant[i][3]+Ant[i][4];
               for(j=0;j<Ant[i][3];j++)
				   minr[j]=mayi[Ant[i][0]].road[j];
               for(k=Ant[i][3];k<minl+1;k++)
				   minr[k]=mayi[Ant[i][1]].road[Ant[i][4]-k+Ant[i][3]];
		   }
 
/////////////头部蚂蚁找到最优解/////////////////////
	 for(mn=0;mn<10;mn++)
	 {
		 if((mayi[mn].life!=0)&&(mayi[mn].life!=1)&&(mayi[mn].l<minl)) 
		 {
			 minl=mayi[mn].l;k=mn;
			 for(i=0;i<=minl;i++)
				 minr[i]=mayi[mn].road[i];
		 }
	 }

////////////底部蚂蚁找到最优解//////////////////////////
	 for(mn=m;mn<m+10;mn++)
	 {
		 if((mayi[mn].life!=0)&&(mayi[mn].life!=1)&&(mayi[mn].l<minl)) 
		 {
			 minl=mayi[mn].l;k=mn;
			 for(i=minl;i>=0;i--)
				 minr[i]=mayi[mn].road[i];

		 }
	 }

		       
////////////////////重新分配信息素//////////////////
	 if(minl<mini)
	 {
		 for(i=0;i<10;i++)
			 for(j=0;j<10;j++)
				 P[i][j]=ro*P[i][j];
		 for(k=0;k<minl;k++)
		 {
			 i=minr[k]/10;
			 j=minr[k]%10;
	         P[i][j]+=1/double(minl);
		 }
				 
	 }

	 for(k=0;k<2*m;k++) 
	{
		for(i=0;i<10;i++)
		for(j=0;j<10;j++)
		{
		    mayi[k].flag[i][j]=0;
		}
	    if(k<m)
		{
			mayi[k].road[0]=b1;
			mayi[k].flag[b1/10][b1%10]=1;
		}
		else
		{
			mayi[k].road[0]=b2;
			mayi[k].flag[b2/10][b2%10]=1;
		}
		mayi[k].l=0;
		mayi[k].life=1;
		
	}
			 
}



	////////////////////////////////////////////////////////
	
	cout<<"步长为:"<<minl<<endl;
	cout<<"路径为:";
	if(minl<1000)
		for(i=0;i<=minl;i++)
			cout<<" "<<minr[i];
		cout<<endl;
	cout<<"0继续，1结束：:";
	cin>>key;
			
}		



   return 0; 
}