hi,everyone ,
one Runtime error occur when running , maybe it's about assigning
memory .
I need your help , thanks.
It's about the travelling sellman problem .
//#include "stdafx.h"
//TSPÎÊÌâµÄ½â·¨
#include<stdlib .h>
#include<math.h >
#include<time.h >
#include "assert.h"
#include "iostream"
using namespace std;
struct city{
double x,y;};
city * cities;
double * dis;
double random1()//·µ»Ø[0,1)Ö®¼äµÄdoubl e
{
return ((double)rand() )/RAND_MAX;
}
/*
template <class T>
void swap( T& a, T& b)
{ T c = a; a = b; b=c;}*/
int random()
{ return rand();}
inline double distance(int CityCnt, char a, char b)
{
double disX = cities[a].x -cities[b].x;
double disY = cities[a].y -cities[b].y;
return sqrt(disX*disX+ disY*disY);
}
class Generation;
class Member{
public:
char * bytes;//ȾɫÌå
double dist;
static int Length ; // to denote using how many bytes
static double p; //±äÒì¸ÅÂÊ
Member(const Member &a) ;
Member();
~Member();
void bianyi();
double Adaptablity (double miniS); //¸æËßÕâÒ»´úµÄ×î¶ Ì·¾¶£¬ÇóAdapta bility
void diyidai();
void birth(Generatio n& g);
double Dis();
Member& operator=(Membe r& x);
};
class Generation {
public:
static int msize; // mn means MemberSize£¨ÖÖÈ ºµÄ´óС£©
int GCount; //¼Ç¼ÏÖÔÚ´¦ÓÚµÚ¼ ¸´ú
double * board; //ÂÖÅÌ
static double p; // ±äÒì»ú»á
class Member * members; //¸öÌåÊý×é
double miniS;//µ±Ç°´úµÄ×î¶Ì·³ Ì
double CalcMiniDis();
void PrintAllDis();
void CalcDis();
void setBoard(); //ÉèÖÃÂÛÅÌ
void PrintBoard();
void jiaocha(Member & a, Member & b); //½»²æ
void bianyi();//¸öÌå±äÒì
void FG();
Generation& birth();
~Generation(){ delete [] board; delete[] members;}
Generation(){
board = new double[msize];
members = new Member[msize];
}
};
void Generation::Cal cDis()
{
for(int i=0;i<msize;i++ )
members[i].dist = members[i].Dis();
}
double Generation::Cal cMiniDis()
{
double s =members[0].dist;
for(int i=0;i<msize;i++ )
{
if(s>members[i].dist) s=members[i].dist;
}
this->miniS= s;
return s;
}
void Generation::Pri ntBoard()
{
cout<<endl;
for(int i=0;i<msize;i++ )
cout<<board[i]<< " ";
cout<<endl;
}
void Generation::bia nyi()
{
for(int i=1;i<Generatio n::msize;i++)
{
this->members[i].bianyi();
}
}
Member::~Member ()
{
delete []bytes;
}
Member::Member( const Member &a)
{
this->bytes = new char[Length];
for(int i =0 ;i<Member::Leng th;i++)
{ this->bytes[i] = a.bytes[i];}
}
void Member::bianyi( ) //±äÒì
{
double p1=random1();
while (p1<p)
{
int x1 = rand()%Member:: Length; int x2 = rand()%Member:: Length;
swap<char>(byte s[x1],bytes[x2]);
p1 = random1();
}
//
cout<<endl;
for(int i=0;i<Member::L ength;i++)
{ cout<<(int)byte s[i]<<" ";}
cout<<endl;
}
void Member::diyidai () //µÚÒ»´úµÄmembers
{
int i,j;
for( i=0;i<Member::L ength;i++)
{bytes[i] = i;}
for( i=0;i<Member::L ength;i++)
{ j = random()%Member ::Length; swap<char>(byte s[i],bytes[j]);}
//
cout<<endl;
for(i=0;i<Membe r::Length;i++)
{ cout<<(int)byte s[i]<<" ";}
cout<<endl;
}
Member::Member( )
{
bytes = new char[Member::Length];
}
void Generation::Pri ntAllDis()
{
cout<<endl;
for(int i=0;i<Generatio n::msize;i++)
cout<<members[i].dist<<" ";
cout<<endl;
}
inline double Member::Dis()
{
double s = 0 ;
for(int i=0;i<Length-1;i++)
{ double temp = dis[bytes[i]*Member::Length +bytes[i+1]];
s+=temp;
}
s+= dis[bytes[0]*Member::Length +bytes[Member::Length]];
this->dist = s;
return s;
}
inline double Member::Adaptab lity(double miniS)//¼ÆËãÊÊÓ¦¶È //Ϊ×Ü·³ÌµÄƽ·½µ ĵ¹Êý
{ double s =this->dist;
s -= 0.9 * miniS; s*=s;
return 1000000/s;
}
void Generation::FG( ) //FirstGeneration
{
for(int i = 0; i<Generation::m size;i++)
members[i].diyidai();
}
Generation& Generation::bir th()
{
Generation * child = new Generation();
for(int i=0;i<msize;i++ )
{
double p1 = random1();
int j;
for(j=0;j<Gener ation::msize && this->board[j]<p1;j++);
//delete[] child->members[i].bytes;
child->members[i] = this->members[j];
cout<<i<<endl;
}
return *child;
}
Member& Member::operato r=(Member& x) //
{
if(this->bytes != NULL) delete[] this->bytes;
if(NULL==(this->bytes = new char[Member::Length])) cout<<"memory
error";
for(int i=0;i<Member::L ength;i++)
this->bytes[i]=x.bytes[i];
return *this;
}
void Generation::jia ocha(Member &a,Member &b) //½»²æ
{
//
cout<<"position xxx"<<endl;
cout<<endl;
for(int p=0;p<Member::L ength;p++) cout<<(int)b.by tes[p]<<" ";
cout<<endl;
bool *flagA=new bool[Member::Length];
bool *flagB=new bool[Member::Length];
memset(flagA,0, sizeof(flagA));
memset(flagB,0, sizeof(flagB));
char * Abytes = new char[Member::Length];
char * Bbytes = new char[Member::Length];
for(int i=0;i<Member::L ength;i++)
{Abytes[i]=a.bytes[i];Bbytes[i]=b.bytes[i];}
int x1 = random()%Member ::Length;
int x2 = random()%Member ::Length;
if(x1>x2) swap<int>(x1,x2 );
i=x1;int j=0;
for(;i<=x2;i++, j++)
{ Abytes[j]=a.bytes[i];Bbytes[j]=a.bytes[i];
flagA[Abytes[j]]=true; flagB[Bbytes[j]]=true;}
int j1=j,j2=j;
for(int k=0;k<Member::L ength;k++)
{
char temp = b.bytes[k];
if(flagA[temp]==false) Abytes[j1++] =temp;
} assert(j1==Memb er::Length);
for(k=0;k<Membe r::Length;k++)
{
char temp = a.bytes[k];
if(flagB[temp]==false) Bbytes[j2++] = temp;
} assert(j2==Memb er::Length);
delete[] a.bytes;
delete[] b.bytes;
a.bytes = Abytes; b.bytes = Bbytes;
delete [] flagA; delete [] flagB;
}
void Generation::set Board()
{ double s = 0;
for(int i=0;i<msize;i++ )
{ s+=members[i].Adaptablity(th is->miniS); board[i]=s;}
for(i=0;i<msize ;i++)//normalize
{ board[i]/=board[msize-1];}
}
//DEL void Generation::Ini t()
//DEL {
//DEL
//DEL }
int Member::Length= 0;
double Member::p = 0.1;
int Generation::msi ze = 10;
void main()
{
freopen("f:\\ol iver30.txt","r" ,stdin);
srand((int)time (0));
int CntCity,i,j;
cin>>CntCity;
Member::Length = CntCity;
cities = new city[CntCity];
double temp;
for( i=0;i<CntCity;i ++)
{ cin>>temp>>citi es[i].x>>cities[i].y>>temp;}
for(i=0;i<CntCi ty;i++)
{cout<<cities[i].x<<" "<<cities[i].y<<endl;}
dis = new double[CntCity*CntCity]; //done
for(i=0;i<CntCi ty;i++)
{
for(j=0;j<CntCi ty;j++)
{ dis[i*CntCity+j]= distance(CntCit y,(char)i,(char )j);
cout<<dis[i*CntCity+j]<<" ";}cout<<en dl;
}
Generation * g1 = new Generation(),gt ;
g1->FG();g1->CalcDis();g1->CalcMiniDis( );
g1->setBoard();g 1->PrintAllDis(); g1->PrintBoard() ;
for(i=0;i<=100; i++)
{
Generation * g2 = &(g1->birth());
for(j=0;j<Gener ation::msize/2;j++)
{g2->jiaocha(g2->members[i],g2->members[i+Generation::m size]);}
g2->CalcDis();
g2->CalcMiniDis( );
g2->setBoard();
g2->PrintAllDis( );
g2->PrintBoard() ;
cout<<g1->miniS<<endl;
delete g1;
cout<<" xxxxxxxxxxxx"<< endl;
g1 = g2;
}
}
//#include "stdafx.h"
//TSPÎÊÌâµÄ½â·¨
#include<stdlib .h>
#include<math.h >
#include<time.h >
#include "assert.h"
#include "iostream"
using namespace std;
struct city{
double x,y;};
city * cities;
double * dis;
double random1()//·µ»Ø[0,1)Ö®¼äµÄdoubl e
{
return ((double)rand() )/RAND_MAX;
}
/*
template <class T>
void swap( T& a, T& b)
{ T c = a; a = b; b=c;}*/
int random()
{ return rand();}
inline double distance(int CityCnt, char a, char b)
{
double disX = cities[a].x -cities[b].x;
double disY = cities[a].y -cities[b].y;
return sqrt(disX*disX+ disY*disY);
}
class Generation;
class Member{
public:
char * bytes;//ȾɫÌå
double dist;
static int Length ; // to denote using how many bytes
static double p; //±äÒì¸ÅÂÊ
Member(const Member &a) ;
Member();
~Member();
void bianyi();
double Adaptablity (double miniS); //¸æËßÕâÒ»´úµÄ×î¶ Ì·¾¶£¬ÇóAdapta bility
void diyidai();
void birth(Generatio n& g);
double Dis();
Member& operator=(Membe r& x);
};
class Generation {
public:
static int msize; // mn means MemberSize£¨ÖÖÈ ºµÄ´óС£©
int GCount; //¼Ç¼ÏÖÔÚ´¦ÓÚµÚ¼ ¸´ú
double * board; //ÂÖÅÌ
static double p; // ±äÒì»ú»á
class Member * members; //¸öÌåÊý×é
double miniS;//µ±Ç°´úµÄ×î¶Ì·³ Ì
double CalcMiniDis();
void PrintAllDis();
void CalcDis();
void setBoard(); //ÉèÖÃÂÛÅÌ
void PrintBoard();
void jiaocha(Member & a, Member & b); //½»²æ
void bianyi();//¸öÌå±äÒì
void FG();
Generation& birth();
~Generation(){ delete [] board; delete[] members;}
Generation(){
board = new double[msize];
members = new Member[msize];
}
};
void Generation::Cal cDis()
{
for(int i=0;i<msize;i++ )
members[i].dist = members[i].Dis();
}
double Generation::Cal cMiniDis()
{
double s =members[0].dist;
for(int i=0;i<msize;i++ )
{
if(s>members[i].dist) s=members[i].dist;
}
this->miniS= s;
return s;
}
void Generation::Pri ntBoard()
{
cout<<endl;
for(int i=0;i<msize;i++ )
cout<<board[i]<< " ";
cout<<endl;
}
void Generation::bia nyi()
{
for(int i=1;i<Generatio n::msize;i++)
{
this->members[i].bianyi();
}
}
Member::~Member ()
{
delete []bytes;
}
Member::Member( const Member &a)
{
this->bytes = new char[Length];
for(int i =0 ;i<Member::Leng th;i++)
{ this->bytes[i] = a.bytes[i];}
}
void Member::bianyi( ) //±äÒì
{
double p1=random1();
while (p1<p)
{
int x1 = rand()%Member:: Length; int x2 = rand()%Member:: Length;
swap<char>(byte s[x1],bytes[x2]);
p1 = random1();
}
//
cout<<endl;
for(int i=0;i<Member::L ength;i++)
{ cout<<(int)byte s[i]<<" ";}
cout<<endl;
}
void Member::diyidai () //µÚÒ»´úµÄmembers
{
int i,j;
for( i=0;i<Member::L ength;i++)
{bytes[i] = i;}
for( i=0;i<Member::L ength;i++)
{ j = random()%Member ::Length; swap<char>(byte s[i],bytes[j]);}
//
cout<<endl;
for(i=0;i<Membe r::Length;i++)
{ cout<<(int)byte s[i]<<" ";}
cout<<endl;
}
Member::Member( )
{
bytes = new char[Member::Length];
}
void Generation::Pri ntAllDis()
{
cout<<endl;
for(int i=0;i<Generatio n::msize;i++)
cout<<members[i].dist<<" ";
cout<<endl;
}
inline double Member::Dis()
{
double s = 0 ;
for(int i=0;i<Length-1;i++)
{ double temp = dis[bytes[i]*Member::Length +bytes[i+1]];
s+=temp;
}
s+= dis[bytes[0]*Member::Length +bytes[Member::Length]];
this->dist = s;
return s;
}
inline double Member::Adaptab lity(double miniS)//¼ÆËãÊÊÓ¦¶È //Ϊ×Ü·³ÌµÄƽ·½µ ĵ¹Êý
{ double s =this->dist;
s -= 0.9 * miniS; s*=s;
return 1000000/s;
}
void Generation::FG( ) //FirstGeneration
{
for(int i = 0; i<Generation::m size;i++)
members[i].diyidai();
}
Generation& Generation::bir th()
{
Generation * child = new Generation();
for(int i=0;i<msize;i++ )
{
double p1 = random1();
int j;
for(j=0;j<Gener ation::msize && this->board[j]<p1;j++);
//delete[] child->members[i].bytes;
child->members[i] = this->members[j];
cout<<i<<endl;
}
return *child;
}
Member& Member::operato r=(Member& x) //
{
if(this->bytes != NULL) delete[] this->bytes;
if(NULL==(this->bytes = new char[Member::Length])) cout<<"memory
error";
for(int i=0;i<Member::L ength;i++)
this->bytes[i]=x.bytes[i];
return *this;
}
void Generation::jia ocha(Member &a,Member &b) //½»²æ
{
//
cout<<"position xxx"<<endl;
cout<<endl;
for(int p=0;p<Member::L ength;p++) cout<<(int)b.by tes[p]<<" ";
cout<<endl;
bool *flagA=new bool[Member::Length];
bool *flagB=new bool[Member::Length];
memset(flagA,0, sizeof(flagA));
memset(flagB,0, sizeof(flagB));
char * Abytes = new char[Member::Length];
char * Bbytes = new char[Member::Length];
for(int i=0;i<Member::L ength;i++)
{Abytes[i]=a.bytes[i];Bbytes[i]=b.bytes[i];}
int x1 = random()%Member ::Length;
int x2 = random()%Member ::Length;
if(x1>x2) swap<int>(x1,x2 );
i=x1;int j=0;
for(;i<=x2;i++, j++)
{ Abytes[j]=a.bytes[i];Bbytes[j]=a.bytes[i];
flagA[Abytes[j]]=true; flagB[Bbytes[j]]=true;}
int j1=j,j2=j;
for(int k=0;k<Member::L ength;k++)
{
char temp = b.bytes[k];
if(flagA[temp]==false) Abytes[j1++] =temp;
} assert(j1==Memb er::Length);
for(k=0;k<Membe r::Length;k++)
{
char temp = a.bytes[k];
if(flagB[temp]==false) Bbytes[j2++] = temp;
} assert(j2==Memb er::Length);
delete[] a.bytes;
delete[] b.bytes;
a.bytes = Abytes; b.bytes = Bbytes;
delete [] flagA; delete [] flagB;
}
void Generation::set Board()
{ double s = 0;
for(int i=0;i<msize;i++ )
{ s+=members[i].Adaptablity(th is->miniS); board[i]=s;}
for(i=0;i<msize ;i++)//normalize
{ board[i]/=board[msize-1];}
}
//DEL void Generation::Ini t()
//DEL {
//DEL
//DEL }
int Member::Length= 0;
double Member::p = 0.1;
int Generation::msi ze = 10;
void main()
{
freopen("f:\\ol iver30.txt","r" ,stdin);
srand((int)time (0));
int CntCity,i,j;
cin>>CntCity;
Member::Length = CntCity;
cities = new city[CntCity];
double temp;
for( i=0;i<CntCity;i ++)
{ cin>>temp>>citi es[i].x>>cities[i].y>>temp;}
for(i=0;i<CntCi ty;i++)
{cout<<cities[i].x<<" "<<cities[i].y<<endl;}
dis = new double[CntCity*CntCity]; //done
for(i=0;i<CntCi ty;i++)
{
for(j=0;j<CntCi ty;j++)
{ dis[i*CntCity+j]= distance(CntCit y,(char)i,(char )j);
cout<<dis[i*CntCity+j]<<" ";}cout<<en dl;
}
Generation * g1 = new Generation(),gt ;
g1->FG();g1->CalcDis();g1->CalcMiniDis( );
g1->setBoard();g 1->PrintAllDis(); g1->PrintBoard() ;
for(i=0;i<=100; i++)
{
Generation * g2 = &(g1->birth());
for(j=0;j<Gener ation::msize/2;j++)
{g2->jiaocha(g2->members[i],g2->members[i+Generation::m size]);}
g2->CalcDis();
g2->CalcMiniDis( );
g2->setBoard();
g2->PrintAllDis( );
g2->PrintBoard() ;
cout<<g1->miniS<<endl;
delete g1;
cout<<" xxxxxxxxxxxx"<< endl;
g1 = g2;
}
}
