sa.cpp

vc7 MFC regular d

#include "stdafx.h"
#include "SA.h"

SA::SA(double* pArray,int width,double t,int l,int count,double lower)//tsp array;array width;tempature;count;lower rate
{
	pSAArray=pArray;
	T=t;
	L=l;
	Width=width;
	ct=0;
	COUNT=count;
	LOWER=lower;
}
int SA::Add(int x1,int x2)
{
	return x1+x2;
}
char* SA::Message()
{
	return "Hello World";
}

void SA::Initialize()//Initialize varibles
{
	NodeList *n=new NodeList();
	pHeader=n;
	pLast=n;
	n->str=new int[Width+1];
	n->t=T;
	for(int i=0;i<Width;i++)
		n->str[i]=i;
}
void SA::Simulate()//simulation annuel
{
	bool flag=true;
	double TT=T;
	ct=0;
	while(flag)
	{
		for(int i=1;i<=L;i++)
		{
			NodeList *n=new NodeList();
			n->str=GeneralS(pLast->str);
			n->order=pLast->order+1;
			n->t=TT;
			int len1=GetLength(pLast->str);
			int len2=GetLength(n->str);
			int delta=len2-len1;
			if(SimuCondition(delta,TT))
			{
				pLast->pNext=n;
				pLast=n;
				ct=0;
			}
			else 
			{
				ct++;
				delete(n);
			}
		}
		if(ct>=COUNT) {ct=0;break;}
		TT=LOWER*TT;
	}
}

int* SA::GeneralS(int* s)//new state generation 
{

	int k=(float)rand()/(float)RAND_MAX*(float)(Width);
	int w=(float)rand()/(float)RAND_MAX*(float)(Width);
	if(k==Width) k=k-1;
	if(w==Width) w=w-1;
	int* re=new int[Width];
	if(k>w)
	{
		int temp=k;
		k=w;
		w=temp;
	}
	if(k==w)
	{
		for(int i=0;i<Width;i++)
		{
			re[i]=s[i];
		}
	}
	else
	{
		for(int i1=0;i1<k;i1++)
		{
			re[i1]=s[i1];
		}
		for(int i2=w+1;i2<Width;i2++)
		{
			re[i2]=s[i2];
		}
		for(int i3=k;i3<=w;i3++)
		{
			re[i3]=s[w+k-i3];
		}
	}
	for(int j=0;j<Width;j++)
		if(re[j]<0)
		{
			int pp=0;
		}
	return re;
}

bool SA::SimuCondition(int delta,double TT)// break condition
{
	if(delta<0) return true;
	else
	{
		double cmp=rand()/(double)RAND_MAX;
		double c=exp(-delta/TT);
		if(c>cmp&&delta!=0) return true;
		else return false;
	}
}

double SA::GetLength(int * str)//get the object function
{
	double re=0;
	for(int i=0;i<Width-1;i++)
	{
		re+=pSAArray[str[i]*Width+str[i+1]];
	}
	re+=pSAArray[str[i-1]*Width+0];
	return re;
}
NodeList** SA::GetReturn() //return and build return data struct
{
	Initialize();
	Simulate();
	NodeList* p[2];
	p[0]=pHeader;
	p[1]=pLast;
	return p;
}