模拟退火算法-货郎担问题.txt

简单模拟退火算法-货郎担问题.txt（c语言）

/*模拟退火算法-货郎担问题*/
/*其中注意L,t值得选取*/
#include "Stdio.h"
#include "math.h"
#include "stdlib.h"
#include "Conio.h"
#include "graphics.h"
#include "time.h"
#define closegr closegraph
#define N 100   /*坐标个数*/

void initgr(void) /* BGI初始化 */
{
  int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果 */
  registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
  initgraph(&gd, &gm, "");
}

void generxy(int m[N],int n[N])/*生成个N随机坐标*/
{
  int i,j;
  srand((unsigned)time(NULL));
  m[0]=random(540)+50;
  n[0]=random(380)+50;
  for(i=1;i<N;i++)
     { loop:m[i]=random(540)+50;
            n[i]=random(380)+50;
            for(j=0;j<i;j++)
            if(abs(m[j]-m[i])<3&&abs(n[j]-n[i])<3)
            goto loop;
      }
}

void caculad(int m[N],int n[N],int o[N][N])/*生成距离矩阵*/
{ int i,j;
  long a,b,c;
  for(i=0;i<N-1;i++)
     for(j=i+1;j<N;j++)
        {b=abs(m[i]-m[j]);b*=b;
         c=abs(n[i]-n[j]);c*=c;
         a=b+c;a=sqrt(a);
         o[i][j]=o[j][i]=a;}
}

int caculaf(int m[N],int o[N][N])/*计算路径长度f*/
{
  int i,t,l,sum;
  t=m[0];l=m[1];
  sum=o[t][l];
  for(i=1;i<N-1;i++)
  {t=m[i];l=m[i+1];
   sum=sum+o[t][l];}
   t=m[0];l=m[N-1];
   sum=sum+o[t][l];
   return(sum);
}

int main(void)
{
  int x[N]={0},y[N]={0};/*xy坐标*/
  int d[N][N]={0};/*距离矩阵*/
  int a[N]={0};/*访问顺序矩阵*/
  int b[N]={0};/*计算过程中的暂时访问顺序矩阵*/
  int f,df;/*路径长度f,路径差df*/
  int u,v,w;/*生成新解的参数*/
  int L=10000;/*步长*/
  int s=0,g,r,q,p;/*中间参数*/
  float t=200;/*控制参数*/
  float dt=0.9;/*衰减参数*/
  int i,j,k,h,z=0;
    initgr(); /* BGI初始化 */
  /*************生成个N随机坐标***************/
  generxy(x,y);
  /*******************************************/

  /***************生成距离矩阵****************/
  caculad(x,y,d);
  /*******************************************/

  /***************生成初始解******************/
  a[0]=random(N);
  for(i=1;i<N;i++)
     { loop:a[i]=random(N);
            for(j=0;j<i;j++)
            if(a[i]==a[j])
            goto loop;
      }
  /*******************************************/

  /**************计算路径长度f****************/
  f=caculaf(a,d);
  /*******************************************/

do
  {
     p=f;

     srand((unsigned)time(NULL));

     for(i=0;i<L;i++)
       {

         for(j=0;j<N;j++)b[j]=a[j];

         r=2+random(2);

  /****************生成新解*******************/
         if(r==2)
           { w=0;
             u=random(N);
       loop1:v=random(N);
             if(v==u)goto loop1;
             if(u>v){k=u;u=v;v=k;}
             for(j=u;j<=(u+v)/2;j++)
              {k=b[j];b[j]=b[u+v-j];b[u+v-j]=k;}
            }

         if(r==3)
           {
             u=random(N);
       loop2:v=random(N);
             if(v==u)goto loop2;
       loop3:w=random(N);
             if(w==u||w==v)goto loop3;
             if(u>v){k=u;u=v;v=k;}
             if(u>w){k=u;u=w;w=k;}
             if(v>w){k=v;v=w;w=k;}
             for(j=0;j<v-u+1;j++)
                { k=b[u];
                  for(h=u;h<w;h++)b[h]=b[h+1];
                  b[w]=k;
                }
            }
  /*******************************************/

  /**************计算路径差df*****************/
             g=caculaf(b,d);
             df=g-f;
  /*******************************************/

  /*************Metropolis准则****************/
         q=(random(99)+1)/100;
         if(df<0||(exp(-df/t))>q)
           {for(j=0;j<N;j++)a[j]=b[j];
            f=f+df;}
  /*******************************************/
       }

   if(p==f)s=1;
   else s=0;

   t=t*dt;

   /*printf("%5d",f);*/
   z=z+1;
   }while(s==0);/*两个相继的Mapkob链中解无任何变化就终止算法*/

  printf("THE MIN LENGTH:%5d,%3d",f,z);/*显示最终的路径长度*/

  /*******************画图********************/
  setcolor(1);
  line(24,24,614,24);
  line(24,24,24,439);
  line(614,24,614,439);
  line(24,439,614,439);
  setcolor(4);
  for(i=0;i<N;i++)
  {circle(x[i],y[i],2);setfillstyle(1,4);floodfill(x[i],y[i],4);}
  setcolor(2);
  for(i=0;i<N-1;i++)
  {q=a[i];h=a[i+1];
   line(x[q],y[q],x[h],y[h]);}
   q=a[0];h=a[N-1];
   line(x[q],y[q],x[h],y[h]);
  /*******************************************/

  getch(); /* 暂停一下，看看前面绘图代码的运行结果 */
  closegr(); /* 恢复TEXT屏幕模式 */
  return 0;
}