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 *);
    int  opeOnDn(string &,string &);
	int  jiedianshu;
private:
	string yuan;
	string mubiao;
	clist  open;
	clist  closed;
};
cjgwt::cjgwt(string &str1,string &str2) :yuan(str1),mubiao(str2),jiedianshu(0) {}
void cjgwt::cpjg()
{
	int flag=0;
	open.insertfront(yuan);//          在OPEN中放致初接点S0；
	open.firstptr->setFn(this->opeOnDn(yuan,mubiao));
	flag=operate();
	cout<<"扩展的节点数：      ";
	cout<<jiedianshu<<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;
			closed.lastptr->setSg(1);
			break;
		}
		else 
		{
			iskuozhan();//判断是否能展开，若能则展开，不能则做下一次循环
			open.sort();
			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.insertback(str);
		open.lastptr->setDadptr(closed.lastptr);
		open.lastptr->setDn(this->opeOnDn(str,mubiao));
		open.lastptr->setHn(closed.lastptr->getHn()+1);
		open.lastptr->setFn(open.lastptr->getDn()+open.lastptr->getHn());
		jiedianshu++;
	}
}
bool cjgwt::isEqualDads(string &str)//是否与祖先接点相同函数
{
	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;

}
int cjgwt::opeOnDn(string &str1,string &str2)//   得出不同的张数
{
	int d=0;
	for(int i=0;i<str1.size();i++)
		if(str1[i]!=str2[i])
			d++;
	return d;
}
# endif