eightnum.cpp

人工智能中的八数码难题 这个采用的是广度优先以及启发式算法

/*
*Copyright by 黄丽福  23020081153237@2009/4/16 
*/
#include<vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <WTYPES.H> 
#include "memory.h"
#define NUMOFDATA 3 //3*3
int CloseForUseId=0;
using namespace std;
typedef struct StatusSturct {
 	int  Board[NUMOFDATA][NUMOFDATA];//棋盘
    int blackPi;//空白棋子的位置
	int BlackPj;
    int Depth;//搜索的深度
	int PNOTRight;//启发式参数值1:位置不同
	int QLength;//启发式参数值2：距离不同
	int prev;//指针索引
	int id;
	struct StatusSturct *next;
	StatusSturct(){
	}
	StatusSturct(int init[][3],int x,int y){//自构函数
	   memcpy(Board,init,sizeof(int)*9);
	   blackPi=x;
	   BlackPj=y;
	   	Depth=QLength=PNOTRight=0;
		prev=0;
		next=NULL;
	}
	setStatusSturct(int init[][3],int x,int y){//自构函数
		memcpy(Board,init,sizeof(int)*9);
		blackPi=x;
		BlackPj=y;
		Depth=QLength=PNOTRight=0;
		prev=0;
		next=NULL;
	
	}
	void setDepth(int n){//设置深度
		Depth=n;
	}
	void print(){//设置深度
					int i,j;
						for(i=0;i<NUMOFDATA;i++){
							for(j=0;j<NUMOFDATA;j++){
								 printf("%d ",Board[i][j]);
							}
							printf("\n");
						} 			
		printf("\n");
	}
	int setPNotRight(struct StatusSturct &endStatus){//启发式参数求值1
        int i,j;
		PNOTRight=0;
		for(i=0;i<NUMOFDATA;i++)
			for(j=0;j<NUMOFDATA;j++){
				if (Board[i][j]!=0&&Board[i][j]!=endStatus.Board[i][j]) {
					PNOTRight++;
				}
			}
			PNOTRight+=Depth;
	
			return PNOTRight;
	}
	void setQLength(struct StatusSturct &endStatus){//启发式参数求值2
        int i,j;
		QLength=0;
		for(i=0;i<NUMOFDATA;i++)
			for(j=0;j<NUMOFDATA;j++){
				if (Board[i][j]!=0){
					int x,y;
				    getNXY(Board[i][j],x,y,endStatus);
			     	QLength+=abs(x-i)+abs(y-j);
				}
			}
				QLength+=Depth;
			
	}
	void getNXY(int n,int &x,int &y,struct StatusSturct &endStatus){//获得最终目标的坐标
		int i,j;
		for(i=0;i<NUMOFDATA;i++)
			for(j=0;j<NUMOFDATA;j++){
				if (endStatus.Board[i][j]==n) {
					x=i;
					y=j;
				}
			}
	}
}Status;
int judgeANDRpeate(Status &newStats);
int  initBoard[NUMOFDATA][NUMOFDATA]={//开始的棋盘状态
	{  2,8,3
	},{1,6,4
	},{7,0,5
	}
};
int  endBoard[NUMOFDATA][NUMOFDATA]={//终点的棋盘状态
	{  1,2,3
	},{8,0,4
	},{7,6,5
	}
};

int selecttype=0;//三种方法的选择变量
Status InitData;//开始的棋盘数据状态
Status endData;//终点的棋盘数据状态
Status *lastFindRecord;//记录访问的结果位置指针
vector<Status> Open;//open列表
vector<Status> Closed;//close列表
void swapdata(int &a,int &b){//交换数据
	int c=a;
	a=b;
	b=c;
}

int expendNodes(Status &curstats){//空白的四方向上移动，列出可能的走法
	int x=curstats.blackPi;
	int y=curstats.BlackPj;
	int  tmpBoard[NUMOFDATA][NUMOFDATA];
	//up
	if (x>0) {
		int tox=x-1;
	    int toy=y;	
		memcpy(tmpBoard,curstats.Board,sizeof(int)*9);//拷贝当前的棋盘状态
		Status tem;
		swapdata(tmpBoard[x][y],tmpBoard[tox][toy]);//走法的实行
		tem.setStatusSturct(tmpBoard,tox,toy);//生成新的走法状态结构
		tem.setDepth(curstats.Depth+1);//计算当前的搜索深度
		tem.setPNotRight(endData);//计算位置不对的个数
		tem.setQLength(endData);//计算位置不对的距离差值
		tem.prev=curstats.id;//用于重构计算的解
		int res=judgeANDRpeate(tem);//调用判断是不结束，或者是否重复，否则就放置这个对象到open列表中
		if (res==3) 
			return 1;
		else if (res==0) 
			Open.push_back(tem);
	}
	//down
	if (x<2) {
		int tox=x+1;
		int toy=y;	
		memcpy(tmpBoard,curstats.Board,sizeof(int)*9);
		Status tem;
		swapdata(tmpBoard[x][y],tmpBoard[tox][toy]);
		tem.setStatusSturct(tmpBoard,tox,toy);
		tem.setDepth(curstats.Depth+1);
		tem.setPNotRight(endData);
		tem.setQLength(endData);
		tem.prev=curstats.id;	
 
	
		
		int res=judgeANDRpeate(tem);
		if (res==3) 
			return 1;
		else if (res==0) 
			Open.push_back(tem);
	}
	//left
	if (y>0) {
		int tox=x;
		int toy=y-1;	
		memcpy(tmpBoard,curstats.Board,sizeof(int)*9);
		Status tem;
		swapdata(tmpBoard[x][y],tmpBoard[tox][toy]);
		tem.setStatusSturct(tmpBoard,tox,toy);
		tem.setDepth(curstats.Depth+1);
		tem.setPNotRight(endData);
		tem.setQLength(endData);
		tem.prev=curstats.id;
		int res=judgeANDRpeate(tem);
		if (res==3) 
			return 1;
		else if (res==0) 
		Open.push_back(tem);
	}
	//right
	if (y<2) {
		int tox=x;
		int toy=y+1;	
		memcpy(tmpBoard,curstats.Board,sizeof(int)*9);
		Status tem;
		swapdata(tmpBoard[x][y],tmpBoard[tox][toy]);
		tem.setStatusSturct(tmpBoard,tox,toy);
		tem.setDepth(curstats.Depth+1);
		tem.setPNotRight(endData);
		tem.setQLength(endData);
		tem.prev=curstats.id;	
		int res=judgeANDRpeate(tem);
		if (res==3) 
			return 1;
		else if (res==0) 
	  	Open.push_back(tem);
		 

	}
	return 0;
}
bool GreateThan(Status &p1,Status &p2){//sort 排序用到的比较方法传参1
     if (p1.PNOTRight>p2.PNOTRight) {
		return true;
	}else return false;
}

bool GreateThan2(Status &p1,Status &p2){//sort 排序用到的比较方法传参2
	
	if (p1.QLength>p2.QLength) {
		return true;
	}else return false;
}

int judgeANDRpeate(Status &newStats){////调用判断是不结束，或者是否重复，否则就放置这个对象到open列表中
     if (memcmp(&newStats.Board,&endData.Board,sizeof(int)*9)==0) {
	    Open.push_back(newStats);
		lastFindRecord=&Open[Open.size()-1];
		return 3;//找到一个解返回
    }
 	int in=Open.size();
 	while (in>0) {
		in--;
		Status curStatus=Open[in]; 
        int res=memcmp(&newStats.Board,&curStatus.Board,sizeof(int)*9);
 		if (res==0) {
 			return 1;//open里面有重复的
		} 
	}
    in=Closed.size();
	while (in>0) {
		in--;
		Status curStatus=Closed[in]; 
        int res=memcmp(&newStats.Board,&curStatus.Board,sizeof(int)*9);
  		if (res==0) {
			if (curStatus.Depth>newStats.Depth) {
				curStatus.Depth=newStats.Depth;
				curStatus.prev=newStats.prev;
			}
 			return 2;//Closed里面有重复的
		} 
	}
 	return 0;
}
void print(){//打印open列表的的项值
	int in=Open.size();
  	while (in>0) {
       in--;
	   Status curStatus=Open[in]; 
	   printf("this small is %d\n",curStatus.PNOTRight);
 	   break;
	}	 
}

void printProcessRes(int id){//搜索结果的列出走法
	if (id>0) {
		  int iid=Closed[id].prev;
		printProcessRes(iid);
	}	
     printf("step id is %d\n",id);
	 Closed[id].print(); 
}

void A_Star(){//A*搜索算法
	InitData.setDepth(0);
	InitData.prev=-1;
	Open.push_back(InitData);
    int cc=0;
	while (Open.size()>0) {
        Status curStatus=Open[Open.size()-1]; //从open列表取出一个元素
	 	Open.pop_back(); 
	    curStatus.id=Closed.size();//放置到closed列表中 
		Closed.push_back(curStatus);
	 	int res=expendNodes(curStatus);//扩展当前状态的走法
		if (selecttype==2) {//不同的启发的选择。
		}else
		if (selecttype==0) {
           sort(Open.begin(),Open.end(),GreateThan);
		}else 
           sort(Open.begin(),Open.end(),GreateThan2);
 			if (res==1) {//找到解，打印结果。						        
				   	int id=lastFindRecord->prev;
                    //printProcessRes(id);
                    //lastFindRecord->print();
				 	if (selecttype==2) {
						printf("static:\ntype 3:深度搜索：\nthe search Nodes is %d\n",Open.size()+Closed.size());
					}else
						if (selecttype==1) {

							 printProcessRes(id);
							 lastFindRecord->print();
							printf("三种不同的方法测试的测试结果如下\nstatic:\ntype 1:位置距离差：\nthe search Nodes is %d\n",Open.size()+Closed.size());
					}else 
				            printf("static:\ntype 2:位置摆放不对号：\nthe search Nodes is %d\n",Open.size()+Closed.size());
					break;
			}	 
	}
}

int main(){
	
	InitData.setStatusSturct(initBoard,2,1);
	endData.setStatusSturct(endBoard,1,1);
 	InitData.setPNotRight(endData);
    InitData.setQLength(endData);
	printf("init data :\n");
    InitData.print();
	printf("end data to:\n");
    endData.print();
	printf("the process is as list:\n");
	
	//三种不同的方法测试
	selecttype=1;//1位置距离差
	A_Star();
    
	
	Open.clear();//2:位置摆放不对号
	Closed.clear();
	selecttype=0;
	A_Star();
	
	Open.clear();//33:深度搜索
	Closed.clear();
    selecttype=2;
    A_Star();

	return 0;
}