tabusearch.txt

蚁群算法实现紧急搜索tabuserach

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

#define N 6 /*具有 6 个节点的五向图*/

main()
{
 int G[N][N];                        /*利用二维数组存放图，数值大小为边的权值，对不连同的边权为1000*/
 int xnext[N][N],xnow[N][N],xt[N][N];/*利用二维数组存放生成树，数值大小为边的权值，对不存在的边权为1000*/
 int tabulist[N][N];                 /*利用二维数组存禁忌表 禁忌长度初始为3*/
 int cycle[N];                       /*利用一维数组存放环*/
 int i,j,m,n,k,x,y;
 
 void ReadGraph(G[N][N]);	         /*从文件graph.txt中读取图，放在G[N][N]中*/
 void Intialize(xnext[N][N],G[N][N]);    /*在图G[N][N]中随即找生成树，存放在xnext[N][N]中*/
 void FindCycle(xt[N][N]),i,j,cycle[N]); /*在树xt[N][N]中找加边(i,j)后生成的环，存放在cycle[N]中*/
 int  Evaluate(x[N][N]);                 /*计算生成树的代价*/

 ReadGraph(G[N][N]);
 Intialize(xnext[N][N],G[N][N]);
 
 for(i=0;i++;i<N)
     for(j=0;j++;j<N) tabulist[i][j]=0;
 
 Repeat 
	for(i=0;i++;i<N)
	    for(j=0;j++;j<N) xnow[i][j]=xnext[i][j];

	for(i=0;i++;i<N)
	    for(j=0;j++;j<N)
		{
		 for(m=0;m++;m<N)
	             for(n=0;n++;n<N) xt[i][j]=xnow[i][j];
		 if((G[i][j]<1000)and(xt[i][j])=1000)
 		     xt[i][j]=G[i][j];
		 FindCycle(xt[N][N]),i,j,cycle[N]);
		 for(k=1;k++;k<N)
		     {
		      if(tabulist[cycle[k-1]][cycle[k]]>0) tabulist[cycle[k-1]][cycle[k]]--;
			else
			{
			 xt[cycle[k-1]][cycle[k]]=1000;
			 if (Evalvate(xt[N][N])<Evaluate(xnext[N][N]))
				{
				 for(m=0;m++;m<N)
				     for(m=0;m++;m<N) xnext[m][n]=xt[m][n];
				 x=cycle[k-1];y=cycle[k];	
				}
			}
		     }	 
		} 
	tabulist[x][y]=3;
 Until  (Evalvate(xnext[N][N])>Evaluate(xnow[N][N]))  
}/*End Main*/

void ReadGraph(int G[N][N]);/*从文件graph.txt中读取图，放在G[N][N]中*/
{
 FILE * inxyfile;
 char c;

 for(i=0;i++;i<N)
     for(j=0;j++;j<N) G[i][j]=0;
 i=0;
 j=0;
 
 if ((inxyfile=fopen("cityxy.txt","r")) == NULL)
   {
    printf("can not open file\n");
    exit(0);
   }
 while(!feof(inxyfile))
      {
       c=fgetc(inxyfile);
       while(c!=' ')
	 {
	  G[i][j]=G[i][j]*10+(int)(c)-48;
	  c=fgetc(inxyfile);
	 }
       ++j;
       if(j=N) 
	{
	 j=0;
	 i++;
	}
      }
 fclose(inxyfile);
}/*End ReadGraph*/

void Intialize(int xnext[N][N],int G[N][N]);/*在图G[N][N]中随即找生成树，存放在xnext[N][N]中*/
{
 int i,j,f,p[N];
 
 f=1;p[0]=1;
 for(i=1;i++;i<N) p[i]=0;
 while(f<N)
 {
  f=0;
  for(i=0;i++;i<N)
     if(p[i]=1) 
	for(j=0;j++;j<N)  
	   {
 	    xnext[i][j]=G[i][j];
	    if(G[i][j]<1000) p[j]=1;
           }
  for(i=0;i++;i<N) f=f+p[i];
 }
}/*End Intialize*/

/*FindCycle在树xt[N][N]中找加边(x,y)后生成的环，存放在cycle[N]中*/
/*FindCycle利用Floyd算法求解一条路经*/
int AddNodeToPath(PathPtr pathptr, int node)
{
 typedef struct  PathType
    {
     int    nodes[N+1];
     int    last;
    }Path, *PathPtr;
 int k;
 if((0 <= pathptr->last) && (pathptr->last < N))
   {
    pathptr->last += 1;
    k = pathptr->last;
    pathptr->nodes[k] = node;
   }    
}    

void FindCycle(int xt[N][N]),int x,int y,int cycle[N]); 
{
    int i, j, k;
    
    for (i = 1; i <= N; i++){
        for (j = 1; j <= N; j++){
            if (xt[i][j] < INF){
                AddNodeToPath(&xt[i][j], i);
                AddNodeToPath(&xt[i][j], j);
            }
        }
    }            
    for (k = 1; k <= N; k++){
        for (i = 1; i <= N; i++){
            for (j = 1; j <= N; j++){
                if (xt[i][k] + xt[k][j] < xt[i][j]){
                    xt[i][j] = PathLenMatrix[i][k] + xt[k][j];
                    MergePath(&xt[i][j], &xt[i][k], &xt[k][j]);
                }
            }
        }
    }                
    for (i = 1; i <= N; i++){      // prohibit cyclic
        xt[i][i].last = 0;
        xt[i][i] = 1000;
    } 
   for(i = 1; i <= N; i++)
       if(xt[i][j] < 1000) cycle[i]=xt[x][i];
}/*End FindCycle*/

int  Evaluate(int x[N][N]);/*计算生成树的代价*/
{
 int i,j,e;
 
 e=0;
 for(i=0;i++;i<N)
     for(j=i+1;j++;j<N) 
        if(x[i][j]<1000) e=e+x[i][j];
 return e;
}/*End Evaluate*/