分支定界实现源程序.c

分支定界算法C语言实现源程序,标准C源代码

/*  用记事本阅读程序源代码时,请将“格式”-〉“自动换行”去掉 */
/*  程序源代码如下，在VC++6.0上编译运行通过  */
/*  本程序用C语言实现，故依据C语言的语法，数字0表示甲城市，数字49表示乙城市 */
#include   <stdio.h>
#include   <stdlib.h>
#include   <string.h>
#define MAX  500            /* 用栈来实现深度优先遍历，MAX表示栈的最大容量 */
#define N 50                /* 城市的数目 */
#define TRUE 1
#define FALSE 0
void Floyd(int d[N][N]);    /* 弗洛伊德算法的实现函数 */
void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]);  /* 分枝定界算法的实现函数 */
void input(int a[N][N],int b[N][N]);                /* 把矩阵b赋值给矩阵a */
int p[N][N][N];                                     /* 三维数组p[N][N][N]是用来实现弗洛伊德算法的辅助矩阵 */
int visited[N],distBound=9999,costBound=1500;       /* 数组visited[N]用来标识所代表的城市是否被访问，1表示被访问，0表示未被访问 */
int bestPath[N],bestLength=0,shortestDist=0,minimumCost=0;  /* bestPath[N]用来记录寻找出的可行路径，bestLength 、shortestDist和minimumCost
                                                               分别表示所找到的可行路径的所经历城市的数目、距离和代价 */

void main()
{
   int   i,j,mindist[N][N],mincost[N][N],m1[N][N],m2[N][N];       /*  m1[N][N]和m2[N][N]分别代表题目所给的距离矩阵和代价矩阵 */
   FILE   *fp;                                                                  
   system("cls");
   for(i=0;i<N;i++)
   {
     visited[i]=0;
     bestPath[i]=0;
   }
   fp=fopen("m1.txt","r");           /* 把文件中的距离矩阵m1读入数组mindist[N][N]  */ 
   if(fp==NULL)
   {
     printf("can not open file\n");
     return;
   }
   for(i=0;i<N;i++)
     for(j=0;j<N;j++)
       fscanf(fp,"%d",&mindist[i][j]);
   fclose(fp);                       /* 距离矩阵m1读入完毕  */
   fp=fopen("m2.txt","r");           /* 把文件中的代价矩阵m2读入数组mincost[N][N]  */ 
   if(fp==NULL)
   {
     printf("can not open file\n");
     return;
   }
   for(i=0;i<N;i++)
     for(j=0;j<N;j++)
       fscanf(fp,"%d",&mincost[i][j]);
   fclose(fp);                     /* 代价矩阵m2读入完毕  */
   input(m1,mindist);              /* mindist[N][N]赋值给m1[N][N]，m1[N][N]代表题目中的距离矩阵 */
   input(m2,mincost);              /* mincost[N][N]赋值给m2[N][N]，m2[N][N]代表题目中的代价矩阵 */
   for(i=0;i<N;i++)                /*  把矩阵mindist[i][i]和mincost[i][i]的对角元素分别初始化，表明城市到自身不连通，代价为0 */
   {
     mindist[i][i]=9999;
     mincost[i][i]=0; 
   }
   Floyd(mindist);                /* 用弗洛伊德算法求任意两城市之间的最短距离，结果存储在数组mindist[N][N]中 */
   Floyd(mincost);                /* 用弗洛伊德算法求任意两城市之间的最小代价，结果存储在数组mincost[N][N]中 */
   fenzhi(m1,m2,mindist,mincost); /* 调用分支定界的实现函数，寻找出所有的可行路径并依次输出 */
   printf("请按任意键退出：");
   getchar();
}
void Floyd(int d[N][N])           /* 弗洛伊德算法的实现函数 */
{
   int v,w,u,i;
   for(v=0;v<N;v++)
     for(w=0;w<N;w++)
     {
       for(u=0;u<N;u++)
         p[v][w][u]=FALSE;
       if(d[v][w]!=9999)
       {
         p[v][w][v]=TRUE;
         p[v][w][w]=TRUE;
       }
     }
   for(u=0;u<N;u++)
     for(v=0;v<N;v++)
       for(w=0;w<N;w++)
         if(d[v][u]+d[u][w]<d[v][w])
         {
           d[v][w]=d[v][u]+d[u][w];
           for(i=0;i<N;i++)
             p[v][w][i]=p[v][u][i]||p[u][w][i];
         }
}
void input(int a[N][N],int b[N][N])       /* 把矩阵b赋值给矩阵a */
{
   int i,j;
   for(i=0;i<N;i++)
     for(j=0;j<N;j++)
       a[i][j]=b[i][j];
}
void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N])
{
   int stack[MAX],depth=0,next,i,j;      /* 定义栈，depth表示栈顶指针；next指向每次遍历时当前所处城市的上一个已经遍历的城市 */
   int cur,currentDist=0,currentCost=0;   /* cur指向当前所处城市，currentDist和currentCost分别表示从甲城市到当前所处城市的最短距离和最小代价，
                                             currentDist和currentCost初值为0表示从甲城市出发开始深度优先搜索 */ 
   stack[depth]=0;                        /* 对栈进行初始化 */
   stack[depth+1]=0;
   visited[0]=1;                          /* visited[0]=1用来标识从甲城市开始出发进行遍历，甲城市已被访问 */
   while(depth>=0)                    /* 表示遍历开始和结束条件，开始时从甲城市出发，栈空，depth=0；结束时遍历完毕，所有节点均被出栈，故栈也为空，depth=0 */          
                                      /* 整个while（）循环体用来实现从当前的城市中寻找一个邻近的城市 */
   {                                  
     cur=stack[depth];                /* 取栈顶节点赋值给cur，表示当前访问到第cur号城市 */
     next=stack[depth+1];             /* next指向当前所处城市的上一个已经遍历的城市 */
     for(i=next+1;i<N;i++)            /* 试探当前所处城市的每一个相邻城市 */
     {                                
       if(m1[cur][i]==9999)         continue;                     /* 所试探的城市不连通 */
       if(visited[i]==1)            continue;                     /* 所试探的城市已被访问 */
       if((currentCost+mincost[cur][N-1]>costBound)||(currentDist+mindist[cur][N-1]>=distBound))   /* 所试探的城市满足剪枝条件，进行剪枝 */    
         continue;    
       if(i<N)  break;     /* 所试探的城市满足访问条件，找到新的可行城市，终止for循环 */
     }
     if(i==N)              /* 判断for循环是否是由于搜索完所有城市而终止的，如果是（i==N），进行回溯 */                      
     {                     
       depth--;
       currentDist-=m1[stack[depth]][stack[depth+1]];
       currentCost-=m2[stack[depth]][stack[depth+1]];
       visited[stack[depth+1]]=0;
     } 
     else                  /* i!=N,表示for循环的终止是由于寻找到了当前城市的一个可行的邻近城市 */
     {                            
       currentDist+=m1[stack[depth]][i];     /* 把从当前所处城市到所找到的可行城市的距离加入currentDist */
       currentCost+=m2[stack[depth]][i];     /* 把从当前所处城市到所找到的可行城市的代价加入currentCost */
       depth++;                              /* 所找到的可行城市进栈  */
       stack[depth]=i;                       /* 更新栈顶指针，指向所找到的可行城市 */
       stack[depth+1]=0; 
       visited[i]=1;                         /* 修改所找到的城市的访问标志 */
       if(i==N-1)                            /* i==N-1表示访问到了乙城市，完成了所有城市的一次搜索，找到一条通路   */  
       {                                                  
         for(j=0;j<=depth;j++)               /* 保存当前找到的通路所经过的所有节点 */                   
           bestPath[j]=stack[j];                 
	 bestLength=depth;                   /* 保存当前找到的通路所经过的所有节点的节点数 */ 
         shortestDist=currentDist;           /* 保存当前找到的通路的距离之和 */ 
         minimumCost=currentCost;            /* 保存当前找到的通路的代价之和 */ 
         distBound=currentDist;              /* 更新剪枝的路径边界，如果以后所找到的通路路径之和大于目前通路的路径之和，就剪枝 */
         if(minimumCost>1500)    continue;   /* 如果当前找到的通路的代价之和大于1500，则放弃这条通路 */
	 printf("最短路径:%3d,路径代价:%3d,所经历的节点数目:%3d,所经历的节点如下:\n",shortestDist,minimumCost,bestLength+1); /* 输出找到的通路的结果 */
	 bestPath[bestLength]=49;            
	 for(i=0;i<=bestLength;i++)          /* 输出所找到的通路所经过的具体的节点 */
           printf("%5d",bestPath[i]);
	 printf("\n");
	 depth--;                             /* 连续弹出栈顶的两个值，进行回溯，开始寻找新的可行的通路 */
	 currentDist-=m1[stack[depth]][stack[depth+1]];
	 currentCost-=m2[stack[depth]][stack[depth+1]];
	 visited[stack[depth+1]]=0;
	 depth--;       
	 currentDist-=m1[stack[depth]][stack[depth+1]];
	 currentCost-=m2[stack[depth]][stack[depth+1]];
	 visited[stack[depth+1]]=0;
       }
     }
   }
}