dfs.cpp

深度优先搜索算法解决八码难题

#include<iostream>
#include<stdio.h>
#define N 3   //九宫二维数组大小
#define M 100000   //closed表的大小，可进行设置
#define D 15    //深度限制，根据需要进行设置

using namespace std;


class jgnode{
public:
	int value[N][N];                 //记录九宫各位置的值
	int num[2];                      //记录0的位置
	int depth;
	jgnode *pre;                  //指向父辈节点的指针
	jgnode *next;
	jgnode():pre(NULL)            //默认构造函数
	{}

	jgnode(const int v[N][N],jgnode *p=NULL){//构造函数初始化
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				value[i][j]=v[i][j];
		pre=p;
	}
	jgnode(const int v[N][N],jgnode *p=NULL,int n[2]=0){
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				value[i][j]=v[i][j];
		pre=p;
		num[0]=n[0];
		num[1]=n[1];
		depth=0;
		next=NULL;
	}
	void print(){                     //输出九宫
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++)
				cout<<value[i][j]<<"  ";
			cout<<endl;}
		cout<<endl;
	}
	int isequal(int v[N][N]){
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				if(value[i][j]!=v[i][j])
					return -1;
		return 0;
	}

};

void findzero(int tv[N][N],int tn[2]);
int expand(jgnode *h,jgnode *t,jgnode *g);
int isgnode(jgnode *t,jgnode *g,int tv[N][N]);
int printnode(jgnode *g);
void evalue(jgnode *t,int tv[N][N]);
int expnode(jgnode *h,jgnode *t,int tv[N][N],int tn[2]);

int main(){
	int vs[N][N]={1,2,3,4,0,5,6,7,8},vg[N][N]={0,1,2,3,4,5,6,7,8},vt[N][N],tnum[2]={0,0};
	int ecount=0,ocount=0,ccount=0,j=0,temp=0,counter=0,dep=15;  
	char cho='n';
do{
	//ecount记录open表末端，ocount记录open表始端，ccount记录closed表末端
	jgnode *head=NULL,*closed[M]={NULL},*tt;
	jgnode *snode=NULL,*gnode=NULL,*tnode=NULL;
	//snode为开时节点，gnode为目标节点，tnode为寄存节点
	
	cout<<"出入搜索的深度界限（默认为15）："<<endl;
	cin>>dep;
	cout<<"输入开始节点（如1,2,3,4,0,5,6,7,8）："<<endl;
	for(int m=0;m<N;m++)
		for(int n=0;n<N;n++)
			cin>>vs[m][n];//scanf("%d",&vs[m][n]);
/*	cout<<"输入目标节点（如0,1,2,3,4,5,6,7,8）："<<endl;
	for(m=0;m<N;m++)
		for(int n=0;n<N;n++)
			cin>>vg[m][n];//scanf("%d",&vg[m][n]);*/
	findzero(vs,tnum);
	snode=new jgnode(vs,NULL,tnum);
	gnode=new jgnode(vg,NULL,tnum);
	cout<<"开始节点："<<endl;
	snode->print();
	cout<<"目标节点："<<endl;
	gnode->print();
	head=snode;tt=head;
	cout<<"start:"<<endl;
	if(snode->isequal(vg)==0){
		cout<<"find with th snode."<<endl;
		return 0;
	}
	closed[ccount++]=snode;
	ecount=expand(head,snode,gnode);
	if(ecount==-1)
		return 0;
	while(j++<M){
		if(head->next==NULL){
			cout<<"open 表已空!"<<endl;
			break;
		}
		tnode=head->next;
		head->next=tnode->next;
		evalue(tnode,vt);
		while(closed[counter]!=NULL){
			if(closed[counter++]->isequal(vt)==0){
				temp=1;break;}
		}
		if(tnode->depth>dep){
			head=tnode;
			continue;
		}
		if(temp==0){
		closed[ccount++]=tnode;
		ecount=expand(head,tnode,gnode);
		if(ecount==-1)
			break;
		}
		temp=0;counter=0;
	}
	cout<<"扩展次数为:  "<<j<<endl;
		j=0;
	cout<<"是否继续下一次搜索（y or n）:"<<endl;
	cin>>cho;
	}while((cho=='y')||(cho=='Y'));
	return 0;
}

int printnode(jgnode *g,int c){
	int cc=c;
	if((g->pre)!=NULL)
		cc=printnode(g->pre,c+1);
	g->print();
	return cc;
}
int isgnode(jgnode *t,jgnode *g,int tv[N][N]){
	int count=0;
	if(g->isequal(tv)==0){
		g->pre=t;
		cout<<"find the goal node!!"<<endl;
		cout<<"搜索路径如下："<<endl;
		count=printnode(g,count);
		cout<<"路径长度："<<count<<endl;
		return -1;
	}
	return 0;
}
int expnode(jgnode *h,jgnode *t,int tv[N][N],int tn[2]){
	jgnode *temp;
	if((t->pre)!=NULL){
		if(((t->pre)->isequal(tv))!=0){
			temp=new jgnode(tv,t,tn);
			temp->pre=t;temp->depth=t->depth+1;
			temp->next=h->next;
			h->next=temp;
			temp=NULL;
			return 1;
		}
		else return 0;
	}
	else{
		temp=new jgnode(tv,t,tn);
		temp->pre=t;temp->depth=t->depth+1;
		temp->next=h->next;
		h->next=temp;
		temp=NULL;
		return 1;
	}
}
//扩展当前节点，并判断是否为目标
int expand(jgnode *h,jgnode *t,jgnode *g){
	int td=0,ti,tj,tv[N][N],tn[2],ct=0,flag=0;
	ti=t->num[0];tj=t->num[1];
    if((ti-1)>=0){
		evalue(t,tv);
		tn[0]=ti-1;tn[1]=tj;
		td=tv[ti-1][tj];tv[ti-1][tj]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn);
	}
    if((tj+1)<=2){
		evalue(t,tv);
		tn[0]=ti;tn[1]=tj+1;
		td=tv[ti][tj+1];tv[ti][tj+1]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn);
	}
    if((ti+1)<=2){
		evalue(t,tv);
		tn[0]=ti+1;tn[1]=tj;
		td=tv[ti+1][tj];tv[ti+1][tj]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn);
	}
    if((tj-1)>=0){
		evalue(t,tv);
		tn[0]=ti;tn[1]=tj-1;
		td=tv[ti][tj-1];tv[ti][tj-1]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn);
	}
	return 0;
}
void evalue(jgnode *t,int tv[N][N]){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			tv[i][j]=t->value[i][j];
}

void findzero(int tv[N][N],int tn[2]){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			if(tv[i][j]==0){tn[0]=i;tn[1]=j;}
		}
}