中国地图着色dlg.cpp

一般回溯算法

				GrowRegiony[nEnd] = yy;	
		   		// 同时也表明该象素处理过
				p_bw[yy*624+xx] = 255;
				if(color[l]==1)
					dc.SetPixel(xx+11,512+10-yy,RGB(255,0,0));
				else if(color[l]==2)
					dc.SetPixel(xx+11,512+10-yy,RGB(0,255,0));
				else if(color[l]==3)
					dc.SetPixel(xx+11,512+10-yy,RGB(0,0,255));
				else
					dc.SetPixel(xx+11,512+10-yy,RGB(255,0,255));
   			}
		}
		nStart++;
	}

	delete []GrowRegionx;
	delete []GrowRegiony;
    GrowRegionx = NULL ;
	GrowRegiony = NULL ;// 释放内存*/
}

void CMyDlg::MultipleRegionGrow(BYTE *bwImage)
{

	static int nDx[]={-1,0,1,0};
	static int nDy[]={ 0,1,0,-1};

	// 定义堆栈的起点和终点
	// 当nStart=nEnd, 表示堆栈中只有一个点
	long int nStart=0 ;
	long int nEnd=0   ;
//	p_bw=new BYTE(512*624);

	int *GrowRegionx = new int [512*624];
	int *GrowRegiony = new int [512*624];

	// 当前正在处理的象素
	int nCurrx ;
	int nCurry ;

	// 循环控制变量
	int k ;

	// 图象的横纵坐标,用来对当前象素的4邻域进行遍历
	int xx;
	int yy;

	CClientDC dc(this);

	memset(p_bw,0,sizeof(BYTE)*319488);	
	nStart=0;
	nEnd=0;
//	Sleep(1000);
	// 把种子点的坐标压入栈
	for(int i=0;i<32;i++)
	{
		GrowRegionx[nEnd] = center_y[i]+color[i]*1000;		//千位数表示颜色
		GrowRegiony[nEnd] = center_x[i];
		nEnd++;
	}
	nEnd--;

	while (nStart<=nEnd)
	{
		// 当前种子点的坐标
		nCurrx = GrowRegionx[nStart];
		nCurry = GrowRegiony[nStart];
//		Sleep(1);

		// 对当前点的4邻域进行遍历
		for (k=0; k<4; k++)	
		{	
			// 4邻域象素的坐标
			xx = nCurrx+nDx[k];
			yy = nCurry+nDy[k];
			
			// 判断象素(xx，yy) 是否在图像内部
			if (	((xx%1000) < 624) && ((xx%1000)>=0) && (yy<512) && (yy>=0) 
					 &&p_bw[yy*624+(xx%1000)]==0
					 &&bwImage[yy*624+(xx%1000)]==255)
			{
				// 堆栈的尾部指针后移一位
				nEnd++;

				// 象素(xx，yy) 压入栈
				GrowRegionx[nEnd] = xx;
				GrowRegiony[nEnd] = yy;
		   		// 同时也表明该象素处理过
				p_bw[yy*624+(xx%1000)] = 255;
				if((xx/1000)==1)
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(255,0,0));
				else if((xx/1000)==2)
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(0,255,0));
				else if((xx/1000)==3)
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(0,0,255));
				else
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(255,0,255));
   			}
		}
		nStart++;
	}

	delete []GrowRegionx;
	delete []GrowRegiony;
    GrowRegionx = NULL ;
	GrowRegiony = NULL ;// 释放内存*/
}

void CMyDlg::NormalBacktrackingSearch()
{
	int i,k=0;
	CString tempstring;
	for(i=0;i<32;i++)	//初始化
		color[i]=0;

	while(k<32)
	{
		color[k]++;

		for(i=0;i<k;i++)
		{
			if(color[i]==color[k]&&NeighbourMatrix[i][k]==1)
			{
				color[k]++;
				i=0;		//从头重新检索
			}
			if(color[k]>=5)
			{
				tempstring.Format("%s",province[k]);
				info+="在";
				info+=tempstring;
				info+="处发生了回溯！";
				info+="\r\n";		
				ShowWindow();
				info.Empty();

				color[k]=0;
				k--;
				k--;
				break;		//跳出内层循环，回溯到上一层
			}
		}
		RegionGrow(*bmpTwo,k);
		k++;
	}
	MessageBox("Mission Complete!");
//	for(i=0;i<32;i++)
//		fout<<color[i]<<endl;
}

void CMyDlg::HeuristicBacktrackingSearch()
{
	bool JudgeMatrix[32][4]={0};	//32个变量的值域
	int Number[32]={0};		//可行值的个数
	int i,j,k=1;
	int ConstraintNumber[32]={0};		//跟该变量有关的约束个数
	int FirstVariable=0;
	bool Flag[32]={0};		//标识该变量是否已经赋过值
	int temp_max=0,temp_min=0,temp=0,temp_number[4]={0},temp2=0;

	CString tempstring;

	for(i=0;i<32;i++)		//初始化
		Number[i]=4;
	for(i=0;i<32;i++)
		for(j=0;j<4;j++)
			JudgeMatrix[i][j]=true;
	
	for(i=0;i<32;i++)			//度启发式，选择涉及约束条件最多的变量先赋值颜色1；
	{
		for(j=0;j<32;j++)
			if(NeighbourMatrix[i][j]==1)
				ConstraintNumber[i]++;
	}

	for(i=0;i<32;i++)
	{
		if(ConstraintNumber[i]>temp_max)
		{
			temp_max=ConstraintNumber[i];
			FirstVariable=i;
		}
	}

	color[FirstVariable]=1;
	info+="由度启发式，第一个要赋值的变量是";
	tempstring.Format("%s",province[FirstVariable]);
	info+=tempstring;
	info+="。\r\n";
	ShowWindow();

	RegionGrow(*bmpTwo,FirstVariable);
	Sleep(1000);
	fout<<FirstVariable<<"  "<<"1"<<endl;

	Flag[FirstVariable]=true;

	for(i=0;i<32;i++)		//前向检验
	{
		if(NeighbourMatrix[FirstVariable][i]==1)
		{
			JudgeMatrix[i][0]=false;
			Number[i]--;
		}
	}

	while(k<32)
	{
		temp_min=5;
		for(i=0;i<32;i++)		//最少剩余值启发式
		{
			if(Number[i]<temp_min&&!Flag[i])
			{
				temp_min=Number[i];
				temp=i;
			}
		}
		Flag[temp]=true;
		info+="由最少剩余值启发式，下一个要赋值的变量是  ";
		tempstring.Format("%s",province[temp]);
		info+=tempstring;
		info+="  。";
		ShowWindow();

		for(i=0;i<4;i++)
			temp_number[i]=0;
		for(i=0;i<4;i++)		//最少约束值启发式，temp_number[i]表示第i个颜色影响到的剩余变量数
		{
			if(JudgeMatrix[temp][i]==false)
				temp_number[i]=100;
			else
			{
				for(j=0;j<32&&!Flag[j];j++)
					if(NeighbourMatrix[temp][j]==1&&JudgeMatrix[j][i]==true)
						temp_number[i]++;
			}
		}
		temp_min=100;
		temp2=0;
		for(i=0;i<4;i++)
		{
			if(temp_number[i]<temp_min)
			{
				temp_min=temp_number[i];
				temp2=i;
			}
		}
		color[temp]=temp2+1;

		info+="根据最少约束值启发式，为其着的颜色为  ";
		tempstring.Format("%s",colorname[temp2]);
		info+=tempstring;
		info+="  。\r\n\r\n";
		ShowWindow();
		Sleep(500);
		RegionGrow(*bmpTwo,temp);
		Sleep(1000);
//		fout<<temp<<"  "<<temp2+1<<endl;

		for(i=0;i<32;i++)		//前向检验
		{
			if(NeighbourMatrix[temp][i]==1&&!Flag[i])
			{
				JudgeMatrix[i][temp2]=false;
				Number[i]--;
			}
		}
		k++;
	}
	info.Empty();
	MessageBox("Mission Complete!");
}


void CMyDlg::GA()
{
	int SIZE;
	double CrossProbability,MutateProbability;
	long GENERATION;

	UpdateData(true);
	SIZE=m_size;
	CrossProbability=m_CrossProbability;
	MutateProbability=m_MutateProbability;
	GENERATION=m_GENERATION;

	int lable=0;	//临时存放的数组标识

	int i,j,k,l;
	double sum=0,sum1=0,sum2=0;
	double temp=0;
	int temp2=0;
	int num1,num2;

//	int allmatrix[SIZE][32]={0};
	int **allmatrix;
	allmatrix=new int *[SIZE];

	for(i=0;i<SIZE;i++)
	{
		allmatrix[i]=new int[32];
	}

//	int allmatrix_temp[SIZE][32]={0};	//临时存放的数组
	int **allmatrix_temp;
	allmatrix_temp=new int *[SIZE];

	for(i=0;i<SIZE;i++)
	{
		allmatrix_temp[i]=new int[32];
	}

//	double fitness[SIZE]={0};			//适应性度量
	double *fitness;					//录入B数组
	fitness=new double[SIZE];
	
	double best_fitness;		//显示用
	int best_number;

	CString tempstring;

	srand((unsigned)time(NULL));
	for(i=0;i<SIZE;i++)			//种群初始化
	{
		for(j=0;j<32;j++)
		{
			allmatrix[i][j]=int(4*double(rand())/(RAND_MAX+1));
//			fout<<allmatrix[i][j];
		}
//		fout<<endl;
	}

	for(l=0;l<=GENERATION;l++)
	{
		sum=0;
		sum1=0;
		sum2=0;
		
//		fout<<"第"<<l<<"代中："<<endl;
		for(i=0,fitness[i]=1;i<SIZE;i++,fitness[i]=1)				//计算适应度
		{
			for(j=0;j<32;j++)
				for(k=j+1;k<32;k++)
					if(NeighbourMatrix[j][k]==1&&allmatrix[i][j]==allmatrix[i][k])
						fitness[i]++;
//			fout<<fitness[i]<<"   ";
		}
//		fout<<endl;

		for(i=0;i<SIZE;i++)
			fitness[i]=1/fitness[i];

		best_fitness=fitness[0];
		best_number=0;
		for(i=1;i<SIZE;i++)
		{
			if(fitness[i]>best_fitness)
			{
				best_fitness=fitness[i];
				best_number=i;
			}
		}

		if(l%20==0)
		{
			tempstring.Format("%d",l);
			info+="第";
			info+=tempstring;
			info+="代中，最佳适应值为：";
			tempstring.Format("%f",best_fitness);
			info+=tempstring;
			info+="\r\n";
			ShowWindow();
		}

		if(best_fitness==1)
		{
			for(i=0;i<32;i++)
			{
				color[i]=allmatrix[best_number][i]+1;
//				RegionGrow(*bmpTwo,i);
//				fout<<color[i]<<"  ";
			}
			tempstring.Format("%d",l);
			info+="第";
			info+=tempstring;
			info+="代中，最佳适应值为：";
			tempstring.Format("%f",best_fitness);
			info+=tempstring;
			info+="\r\n";
			ShowWindow();
			info.Empty();

			MultipleRegionGrow(*bmpTwo);
			l=GENERATION+2;				//跳出循环
			MessageBox("Mission Complete!");
			break;
		}

		for(i=0;i<SIZE;i++)
			sum+=fitness[i];

		for(lable=0;lable<SIZE;lable=lable+2)		//一次完整的选择杂交过程
		{			
			temp=double(rand())/RAND_MAX;
			i=0;
			sum1=fitness[0];
			while(double(sum1/sum)<temp)	//轮转法选择交叉的母代num1
			{
				i++;
				sum1+=fitness[i];
			}
			num1=i;

			temp=double(rand())/RAND_MAX;
			i=0;
			sum2=fitness[0];
			while(double(sum2/sum)<temp)	//轮转法选择交叉的母代num2
			{
				i++;
				sum2+=fitness[i];
			}
			num2=i;

			temp2=int(32*double(rand())/(RAND_MAX+1));	//交叉的位置

//	fout<<"num1="<<num1<<"  num2="<<num2<<"  temp2="<<temp2<<endl;

			if(double(rand())/RAND_MAX<CrossProbability)	//是否交叉
			{
				for(i=0;i<temp2;i++)
				{
					allmatrix_temp[lable][i]=allmatrix[num1][i];
					allmatrix_temp[lable+1][i]=allmatrix[num2][i];
				}	
				for(i=temp2;i<32;i++)
				{
					allmatrix_temp[lable][i]=allmatrix[num2][i];
					allmatrix_temp[lable+1][i]=allmatrix[num1][i];
				}
			}
			else
			{
				for(i=0;i<32;i++)
				{
					allmatrix_temp[lable][i]=allmatrix[num1][i];
					allmatrix_temp[lable+1][i]=allmatrix[num2][i];
				}
			}
		}
		
		for(i=0;i<SIZE;i++)
		{
			if(double(rand())/RAND_MAX<MutateProbability)
			{
				temp2=int(32*double(rand())/(RAND_MAX+1));	//变异的位置
				allmatrix_temp[i][temp2]=int(4*double(rand())/(RAND_MAX+1));
			}
		}

		for(i=0;i<SIZE;i++)
		{
			for(j=0;j<32;j++)
			{
				allmatrix[i][j]=allmatrix_temp[i][j];
//		fout<<allmatrix[i][j];
			}
//	fout<<endl;
		}
	}

	if(l==GENERATION+1)
	{
		info+="无解！\r\n";
		ShowWindow();
		info.Empty();
	}
}


void CMyDlg::OnButton1() 
{
	// TODO: Add your control notification handler code here
	ShowWindow();
	Open();
	Thining();
	NormalBacktrackingSearch();
}

void CMyDlg::OnButton2() 
{
	// TODO: Add your control notification handler code here
	ShowWindow();
	Open();
	Thining();
	HeuristicBacktrackingSearch();
}

void CMyDlg::OnButton3() 
{
	// TODO: Add your control notification handler code here
	ShowWindow();
	Open();
	Thining();
	GA();
}

void CMyDlg::ShowWindow()
{
	CEdit*HInfo=(CEdit*)GetDlgItem(IDC_EDIT1);
	HInfo->SetWindowText(info);
	HInfo->LineScroll(HInfo->GetLineCount());
}

inline void CMyDlg::memError()
{
	MessageBox("Memory allocation error!");
	exit(1);
}