人工智能-宽度搜索.cpp

来自「八数码宽度优先搜索算法,可以找到最优解,但会消耗更多的资源.」· C++ 代码 · 共 212 行

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

char t[10]="012345678";

int strdif(char s[]);
int strindex(char s[]);
inline void change(char &a,char &b);

class node
{
private:
	char s[10];
	char op;
	int  dif,index;
	node *pre;
	node *next;
	node *openroot;
	node *closeroot;
	node *openlast;
public:
	node():op('\0'),dif(10),index(10),next(NULL),pre(NULL),openroot(NULL),closeroot(NULL),openlast(NULL) 
	{
		strcpy(s,"\0");
	}
	void init(char s[])
	{
		node *temp;
		int i=0;
		openroot=new node;
		closeroot=new node;
		temp=new node;
		openroot->next=temp;
		strcpy(temp->s,s);
		i=strdif(s);
		temp->dif=i;
		i=strindex(s);
		temp->index=i;
		openlast=temp;
	}
	void deal();
	void develop(node *temp);
	void prin(node *temp);
	void move(node *temp,int s,int t,char op);
	void destorynode()
	{
		node *temp;
		while(openroot!=NULL)
		{
			temp=openroot->next;
			delete openroot;
			openroot=temp;
		}
		while(closeroot!=NULL)
		{
			temp=closeroot->next;
			delete closeroot;
			closeroot=temp;
		}
		cout<<"DESTORIED!"<<endl;
	}
};

void node::deal()
{
	node *temp,*cursor;
	if(openroot->next==NULL)
	{
		cout<<"ERROR!"<<endl;
		exit(1);
	}
	temp=openroot->next;
	openroot->next=temp->next;
	temp->next=closeroot->next;
	closeroot->next=temp;
	if(temp->dif==0)
	{
		prin(closeroot->next);
		return;
	}
	for(openlast=openroot;openlast->next!=NULL;openlast=openlast->next);
	cout<<"1"<<endl;
	cout<<(void *)temp<<endl;
	cout<<"2"<<endl;
	switch(temp->index)
	{ 
			case 0:	 move(temp,0,1,'R');
				     move(temp,0,3,'D');
					 break;

			case 1:  move(temp,1,0,'L');
					 move(temp,1,2,'R');
					 move(temp,1,4,'D');
					 break;

			case 2:  move(temp,2,5,'D');
					 move(temp,2,1,'L');
					 break;

			case 3:  move(temp,3,0,'U');
					 move(temp,3,4,'R');
					 move(temp,3,6,'D');
					 break;

			case 4:  move(temp,4,1,'U');
					 move(temp,4,5,'R');
					 move(temp,4,3,'L');
					 move(temp,4,7,'D');
					 break;

			case 5:  move(temp,5,2,'U');
					 move(temp,5,4,'L');
					 move(temp,5,8,'D');
					 break;

			case 6:  move(temp,6,3,'U');
					 move(temp,6,7,'R');
					 break;

			case 7:  move(temp,7,4,'U');
					 move(temp,7,8,'R');
					 move(temp,7,6,'L');
					 break;

			case 8:  move(temp,8,5,'U');
					 move(temp,8,7,'L');
					 break;
	}   
	deal();
}

void node::move(node *temp,int s,int t,char op)
{
	cout<<"3"<<endl;
	node *cursor,*p,*q;
	char m[10];
	strcpy(m,temp->s);
	change(m[s],m[t]);
	cout<<"bijiaoM"<<endl;//
	for(p=openroot->next,q=closeroot->next;p!=NULL||q!=NULL;)
	{
		if(p!=NULL)
		{
			if(strcmp(m,p->s)==0)
				return;
			p=p->next;
		}
		if(q!=NULL)
		{
			if(strcmp(m,q->s)==0)
				return;
			q=q->next;
		}
	}
	cout<<"bijiaoM-1"<<endl;//
	cursor=new node;
	strcpy(cursor->s,m);
	cursor->op=op;
	cursor->index=t;
	cursor->dif=strdif(cursor->s);
	cursor->pre=temp;
	cursor->next=openlast->next;
	openlast->next=cursor;
	cout<<cursor->s<<endl;//
}

void node::prin(node *temp)
{
	while(temp!=NULL)
	{
		cout<<temp->s<<"  "<<temp->op<<endl;
		temp=temp->pre;
	}
}

void main()
{
	node op;
	char s[10];
	cout<<"目标状态："<<t<<endl;
	cout<<"请输入你的初始状态：";
	cin>>s;
	s[9]='\0';
	op.init(s);
	op.deal();
	op.destorynode();
}

int strdif(char s[])
{
	int i,j;
	i=j=0;
	for(;s[i]&&i<9;i++)
		if(s[i]!=t[i]&&t[i]!='0')
			j++;
	return j;
}
int strindex(char s[])
{
	int i=0;
	for(;s[i]&&i<9;i++)
		if(s[i]=='0')
			break;
	return i;
}

inline void change(char &a,char &b)
{
	char c;
	c=a;a=b;b=c;
}