tendropsGA 十滴水 遗传算法

#include
#include
#include
#include
using namespace std;
#define maxb 6 //最长步数
#define maxt 36 //种群数
#define maxdep 8000 //代数
#define ps 0.6 //选择
#define pc 0.005 //交叉
#define pm 0.25 //变异
#define pn 0.01 //变态
#define nn 40
#define random(h) rand()%h;
#define imageb 4
int a[8][8],b[8][8];
int x[150],y[150],v[150],f[150];
int ans[maxb+5];
int best=21,bestf=-1;
int z[maxt+5][maxb+5]; //当前种族
int n[maxt+5][maxb+5];
double sy[maxt+5]; //适应度
int ff[maxt+5];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};



void get(int q,int &xx,int &yy)
{xx=(q/6)+1;
yy=(q%6)+1;
return;
}


int sum()
{int f=0;
for(int i=1;i<=6;i++)
for(int j=1;j<=6;j++)
f+=a[i][j];
return f;
}

int dropfly(int c,int d)
{a[c][d]=0;
int dropnum=4,num=4;
x[1]=x[2]=x[3]=x[4]=c;
y[1]=y[2]=y[3]=y[4]=d;
v[1]=1;v[2]=2;v[3]=3;v[4]=4;
f[1]=f[2]=f[3]=f[4]=1;
while (num)
{for (int i=1;i<=dropnum;i++)
if (f[i]) {x[i]+=dx[v[i]]; y[i]+=dy[v[i]];
if ((x[i]==0)||(x[i]==7)||(y[i]==0)||(y[i]==7)) {f[i]=0;num--;} //wall
if (a[x[i]][y[i]]) {f[i]=0; num--; a[x[i]][y[i]]++; } //drop
}
for (int ii=1;ii<=6;ii++)
for (int jj=1;jj<=6;jj++)
if (a[ii][jj]>4)
{a[ii][jj]=0;
dropnum++;x[dropnum]=ii;y[dropnum]=jj;v[dropnum]=1;f[dropnum]=1;num++;
dropnum++;x[dropnum]=ii;y[dropnum]=jj;v[dropnum]=2;f[dropnum]=1;num++;
dropnum++;x[dropnum]=ii;y[dropnum]=jj;v[dropnum]=3;f[dropnum]=1;num++;
dropnum++;x[dropnum]=ii;y[dropnum]=jj;v[dropnum]=4;f[dropnum]=1;num++;
}
}
return dropnum/12 ;
}


int getf(int *t ,int p)
{int xx,yy;
memcpy(a,b,sizeof(b));
for(int i=1;i<=p;i++) {int f=0;
get(t[i],xx,yy);
a[xx][yy]++;
if (a[xx][yy]>4) f+=dropfly(xx,yy);
if (!sum()) { if ((ibestf)) {best=i; bestf=f; memcpy(ans,t,sizeof(ans));}
return i;}
}
return p+1;
}



void sw(int &aa,int&bb)
{int t;
t=aa;aa=bb;bb=t;
return;
}

void create()
{int i,j;
for (i=1;i<=maxt;i++)
for (j=1;j<=maxb;j++)
z[i][j]=random(36);
}

void s()
{printf("%s","s");
int e,nw=0;
for (int i=1;i<=maxt;i++) sy[i]=getf(z[i],maxb);
for (int i=1;i<=maxt;i++) sy[i]=6/sy[i];
memset(ff,0,sizeof(ff));
double sumf=0;
for (int i=1;i<=maxt;i++) sumf+=sy[i];
for (int i=1;i<=maxt;i++) sy[i]/=sumf;
for (int i=2;i<=maxt;i++) sy[i]+=sy[i-1];
for (int i=1;i<=maxt;i++)
{e=1;
double r=rand()/(RAND_MAX+1.0);
while ((sy[e]double rr=rand()/(RAND_MAX+1.0);
if (rr}
for (int i=nw+1;i<=maxt;i++)
for (int j=1;j<=maxb;j++)
n[i][j]=random(36);
memcpy(z,n,sizeof(z));
}

void

c()
{printf("%s","c");
int i,j,k;
for (i=1;i<=maxt;i++) sy[i]=getf(z[i],maxb);
for (i=1;i<=maxt;i++)
for (j=1;j<=maxt;j++)
{double r=rand()/(RAND_MAX+1.0);
if (r{int rr=(rand()%maxb)+2;
for(k=rr;k<=maxb;k++)
sw(z[i][k],z[j][k]);
}
}
}

void m()
{printf("%s","m");
int i,rr;
for (i=1;i<=maxt;i++) sy[i]=getf(z[i],maxb);
for (i=1;i<=maxt;i++)
{double r=rand()/(RAND_MAX+1.0);
if (r{rr=(rand()%maxb)+1;
z[i][rr]=random(36);
}
}
}

void n1()
{printf("%s","n");
for (int i=1;i<=maxt;i++) sy[i]=getf(z[i],maxb);
for (int i=1;i<=maxt;i++)
for (int k=1;k<=nn;k++)
{double r=rand()/(RAND_MAX+1.0);
if (rint r1=(rand()%maxb)+1;
int r2=(rand()%maxb)+1;
sw(z[i][r1],z[i][r2]);
}
}
return;
}


void fread()
{ FILE *fp=fopen("in.txt","r");
memset(b,0,sizeof(b));
for (int i=1;i<=6;i++)
for (int j=1;j<=6;j++)
{fscanf(fp,"%d",&b[i][j]);}
}







void work()
{
for (int i=1;i<=maxdep;i++)
{
s();
c();
m();
n1();
if (best<=imageb)break;
}
for (int i=1;i<=maxt;i++) sy[i]=getf(z[i],maxb);
return;
}

void print()
{int xx,yy;
printf("\n%d\n",best);
for (int i=1;i<=best;i++)
{ get(ans[i],xx,yy);
printf("%d %d\n",xx,yy);}
return;
}

int main()
{fread();
create();
work();
print();
return 0;
}