eight_codes.cpp

hws01:野人和传教士问题 hws02:用Romberg外推法求积分近似值 hws03:八数码问题 hws04:模拟退火算法 hws05:遗传算法解决旅行商问题

#include<iostream>
#include<map>
#include<cmath>
#include<string>
using namespace std;

int Step=0; // 用于记录搜索步数
const int Terminal[3][3] ={ {1,2,3},{8,0,4},{7,6,5} };//二维数组Terminal表示目标状态


class Statement                                           
{
public :             
	int **A;        // 数据
	string Parent; // 父节点形状
	int F_value;
    Statement()   // 默认构造
	{
	    A=new int*[3];
        for(int i=0;i<3;i++)
	      A[i]=new int[3];
	}
	
	Statement(int **Array,string parent,int fv)  // 带参数的构造函数
	{
	   A=new int*[3];
       for(int i=0;i<3;i++)
	      A[i]=new int[3];
	   for(int i=0;i<3;i++)
		   for(int j=0;j<3;j++)
			   A[i][j]=Array[i][j];
       Parent=parent;
	   F_value=fv;
	}
};

map<string,Statement> OPEN,CLOSE; // 采用map 作为存储介质

int Get_f_value(int **A,int Depth)//评价函数 f(n)=g(n)+h(n)
{
	int Dis_sum=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			if(A[i][j]!=0)
			{
			   for(int p=0;p<3;p++)
				   for(int q=0;q<3;q++)
					   if(A[i][j]==Terminal[p][q])
						   Dis_sum+=abs(i-p)+abs(j-q);
			}
		}
    return Depth+Dis_sum;
}


string Get_Shape(int **A)  // 节点的形状：用数据串来抽象
{
   string str;
   for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			str+=(char)(A[i][j]+48);  
   return str;
}

string Get_first()  // 获取OPEN表中耗散值最小的节点形状
{
	string str;
	int min_F=OPEN.begin()->second.F_value;
	for(map<string,Statement>::iterator it =OPEN.begin();it!=OPEN.end();++it)
		if(it->second.F_value<=min_F)
		{
			str=it->first;
			min_F=it->second.F_value;
		}
		return str;
}

bool Distorte(int n,int **Array)  // 九宫格的变形，该函数用于判断是否有变形
{
	int x,y;
    for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			if(Array[i][j]==0)
			{
			   x=i ;  y=j;
			}
		}
    switch(n)
	{
	case 0:
		if(y-1<0)  return false;
		else 
		{
		   Array[x][y]=Array[x][y-1];
           Array[x][y-1]=0;
		   break;
		}
	case 1:
        if(y+1>2)  return false;
		else 
		{
		   Array[x][y]=Array[x][y+1];
           Array[x][y+1]=0;
		   break;
		}
	case 2:
		if(x+1>2)  return false;
		else 
		{
		   Array[x][y]=Array[x+1][y];
           Array[x+1][y]=0;
		   break;
		}
	case 3:
		if(x-1<0)  return false;
		else 
		{
		   Array[x][y]=Array[x-1][y];
           Array[x-1][y]=0;
		   break;
		}
	default: break;
	}
	return true;
}

bool Is_Goal( int **A)         //  判断是否到达终止状态
{
    for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(A[i][j]!=Terminal[i][j])
				return false;
	return true;
}


bool Can_Solve(int **A)          // 判断是否有解
{
    int N[9];
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			N[i*3+j]=A[i][j];
	int sum=0;
	for(int i=0;i<9;i++)
	{
		int k=0;
		if(N[i]!=0)
		{
		   for(int j=0;j<i;j++)
			   if(N[j]!=0&&N[j]<N[i])
				   k++;
		}
		sum+=k;
	}
	if(sum%2==1)return true;
	else return false;
}

void Disp(string key,string start)    // 回溯法，输出最佳路径
{
	Step++;
	if(key==start) return;
	else 
	{
		Disp(CLOSE[key].Parent,start);
	    for(int i=0;i<3;i++)
		    for(int j=0;j<3;j++)
		    {
			    cout<<CLOSE[key].A[i][j]<<" ";
        	    if(j==2)cout<<endl;
		    }
		  cout<<endl;
	}
}

bool EIGHT_CODES(int **A)     // A* 算法的主体函数
{
	int Depth=0;
	int fv=Get_f_value(A,Depth);
	string Start_shape=Get_Shape(A);         
    Statement start(A,"Over",fv);
	OPEN[Start_shape]=start;                  
	while(!OPEN.empty())
	{
		 string first=Get_first();
		 Statement  node(OPEN[first].A,OPEN[first].Parent,OPEN[first].F_value);   
		 if(Is_Goal(node.A)) 
		 {
			 Disp(node.Parent,Start_shape);
             for(int i=0;i<3;i++)
		        for(int j=0;j<3;j++)
		        {
			       cout<<node.A[i][j]<<" ";
        	        if(j==2)cout<<endl;
		         }
				cout<<endl;
				cout<<"Total Steps: "<<Step<<endl;
			 return true;
		 }
		 OPEN.erase(first);
		 CLOSE[first]=node;
         Depth++;
         for(int i=0;i<4;i++)                   // 节点展开
		 {  
			 Statement expand(node.A,node.Parent,node.F_value);
			 if(!Distorte(i,expand.A)) continue;
			 else 
			 {  
				 string New_shape=Get_Shape(expand.A);
				 int New_fv=Get_f_value(expand.A,Depth);
				 if(OPEN.count(New_shape)!=0)                     //mk 类节点
				 {   
					 if(OPEN[New_shape].F_value>New_fv)
					 {
                       OPEN[New_shape].F_value=New_fv;
					   OPEN[New_shape].Parent=Get_Shape(node.A);
					 }
				 }
				 else if(CLOSE.count(New_shape)!=0&&New_shape!=Start_shape) //m1 类节点
				 {
				     
					 if(CLOSE[New_shape].F_value>New_fv)
					 {
						 OPEN[New_shape]=expand;
                         OPEN[New_shape].F_value=New_fv;
					     OPEN[New_shape].Parent=Get_Shape(node.A);
					     CLOSE.erase(New_shape);
					 }
				 }
				 else if(New_shape!=Start_shape)                     //mi 类节点
				 {  
					 OPEN[New_shape]=expand;
					 OPEN[New_shape].Parent=Get_Shape(node.A);
                     OPEN[New_shape].F_value=New_fv;
				 }
			 }
		 }
	}
	return false;
}


int main()
{
	
   cout<<"请输入8数码问题初始状态："<<endl;
   int **A=new int*[3];       //创建二维数组
   for(int i=0;i<3;i++)
	   A[i]=new int[3];
   for(int i=0;i<3;i++)
   {
	   for(int j=0;j<3;j++)
	   {
		   cin>>A[i][j];
	   }

   }

   if(!Can_Solve(A))
	   cout<<"no solution";
   else 
   {
	   cout<<"求解过程如下："<<endl;
	   EIGHT_CODES(A);
   }

   return 0;
}