jgwt.h

人工智能中的深度搜索的九宫问题 用VC实现

# ifndef jgwt_h
# define jgwt_h
# include <iostream>
# include <string>
# include "list.h"
class cjgwt
{
public:
	cjgwt(string &,string &);
	void cpjg();
	bool operate();
	void iskuozhan();
	bool isEqualDads(string &);
	void swap(string &,int ,int);
	void isInsertOpen(string &);
	void print();
	void output(cnode *);

private:
	string yuan;
	string mubiao;
	clist  open;
	clist  closed;
};
cjgwt::cjgwt(string &str1,string &str2) :yuan(str1),mubiao(str2) {}
void cjgwt::cpjg()
{
	int flag=0;
	open.insertfront(yuan);//          在OPEN中放致初接点S0；
	flag=operate();
	//cout<<flag<<endl;
	if(flag==1)
		print();
	else cout<<"对不起，在1000步之内做不出"<<endl;
}
bool cjgwt::operate()
{
	int flag=0,i=0;
	while(open.isempty()==0)
	{
		closed.insertback(open.removefront());
		if(closed.lastptr->GetData()==mubiao)//  判断CLOSED表中的LASTPTR是否为目标接点
		{
			flag=1;
			break;
		}
		else 
		{
			/*if(iskuozhan()==0)////////////////////////
				continue;
			else
			{
				zhankai();
			}*/
			iskuozhan();//判断是否能展开，若能则展开，不能则做下一次循环
			i++;
		}
		if(i==1000)
			break;
	}
	//cout<<i<<endl;
	if(flag==1)
		return 1;
	else return 0;
}
void cjgwt::iskuozhan()
{
	int type;
	string temp=closed.lastptr->GetData();
	string str1,str2,str3,str4;
	str1=str2=str3=str4=temp;
	type=temp.find("0")+1;
	switch(type)
	{
	case 1:
		//string str1=temp,str2=temp;
		swap(str1,0,1);
		isInsertOpen(str1);
		swap(str2,0,3);
        isInsertOpen(str2);
		break;
	case 2:
		//string str1=temp,str2=temp,str3=temp;
		swap(str1,1,0);
		isInsertOpen(str1);
		swap(str2,1,2);
		isInsertOpen(str2);
		swap(str3,1,4);
		isInsertOpen(str3);
		break;
	case 3:
		swap(str1,2,1);
		isInsertOpen(str1);
		swap(str2,2,5);
		isInsertOpen(str2);
		break;
	case 4:
		swap(str1,3,0);
		isInsertOpen(str1);
		swap(str2,3,4);
		isInsertOpen(str2);
		swap(str3,3,6);
		isInsertOpen(str3);
		break;
	case 5:
		swap(str1,4,1);
		isInsertOpen(str1);
		swap(str2,4,3);
		isInsertOpen(str2);
		swap(str3,4,5);
		isInsertOpen(str3);
		swap(str4,4,7);
		isInsertOpen(str4);
		break;
	case 6:
		swap(str1,5,2);
		isInsertOpen(str1);
		swap(str2,5,4);
		isInsertOpen(str2);
		swap(str3,5,8);
		isInsertOpen(str3);
		break;
	case 7:
		swap(str1,6,3);
		isInsertOpen(str1);
		swap(str2,6,7);
		isInsertOpen(str2);
		break;
	case 8:
		swap(str1,7,4);
		isInsertOpen(str1);
		swap(str2,7,6);
		isInsertOpen(str2);
		swap(str3,7,8);
		isInsertOpen(str3);
		break;
	case 9:
		swap(str1,8,5);
		isInsertOpen(str1);
		swap(str2,8,7);
		isInsertOpen(str2);
		break;
	default:
		cout<<type<<endl;
		break;
	}
}
void cjgwt::swap(string &str,int m,int n)
{
	char temp;
	temp=str[m];
	str[m]=str[n];
	str[n]=temp;
}
void cjgwt::isInsertOpen(string &str)//  判断是否与祖先接点相同，不同则插入
{
	if(isEqualDads(str)==1)
	{}
	else 
	{
		open.insertfront(str);
		open.firstptr->setDadptr(closed.lastptr);
		//open.lastptr->dadptr=closed.lastptr;
		//value=1;
	}
}
bool cjgwt::isEqualDads(string &str)//是否与祖先接点相同函数
{
/*	cnode *currptr=closed.lastptr;
	string temp=currptr->GetData();
	while(currptr!=NULL && temp!=str)
	{
		currptr=currptr->getDadptr();
	}
	if(currptr==NULL)
		return 0;
	else return 1;*/
	cnode *currptr=closed.lastptr;
	string temp;
	while(currptr!=NULL)
	{
		temp=currptr->GetData();
		if(temp!=str)
		{
			
			currptr=currptr->getDadptr();
		}
		else break;
	}
	if(currptr!=NULL)
		return 1;
	else return 0;
}
void cjgwt::print()
{
	cnode *currptr=closed.lastptr;
	while(currptr!=NULL)
	{
		output(currptr);
		currptr=currptr->getDadptr();
	}
}
void cjgwt::output(cnode *value)
{
	string temp=value->GetData();
	for(int i=0;i<9;i++)
	{
		if(temp[i]=='0')
		{
			cout<<"    ";
			if(i==8 || i==5 || i==2)
				cout<<endl;
		}
		else
		{
			cout<<temp[i]<<"   ";
		    if(i==2 || i==5 ||i==8)
			cout<<endl;
		}
	}
	cout<<"*************************"<<endl;

}
# endif