chessdoc.cpp

解决八数码问题的经典程序。实现了宽带优先算法

		}
		if(q==NULL) head=head->next;
		else
			q->next=s->next;
		if(!first) first=s;
		else last->next=s;
		last=s;
	}
	*pHead=first;

		
}

int CChessDoc::BFSA1(unsigned char *start, unsigned char *goal)
{
	CPathNode *info,*p,*OpenFirst,*OpenLast,*CloseFirst;
	UINT nextspace;
	int m,n,i,same,flag,Generate,Split;
	
	//初始化第一个节点
	info=new CPathNode(m_N);
	memcpy(info->state,start,m_NUM);
	info->space=strcspn((char*)start,"0");
	info->depth=0;
	info->move='0';
	info->rule=0;
	info->next=info->parent=NULL;

	info->weight=info->depth+Start2GoalW(info->state,goal,m_NUM);

	//初始化队列
	OpenFirst=OpenLast=info;
	CloseFirst=NULL;
	Generate=0;
	Split=0;
	flag=1;
	while(_kbhit()==0)
	{
		if(!OpenFirst || OpenFirst->depth>m_nDepth)
		{
			flag=-1;
			goto Exit_Label;
		}
		//扩展当前队列
		int splitFlag=0;
		for(i=0;i<4;i++)
		{
			if(OpenFirst->depth==m_nDepth) break;
			
			info= new CPathNode(m_N);
			info->depth=OpenFirst->depth +1;
			memcpy(info->state,OpenFirst->state,m_NUM);
			info->space=OpenFirst->space;
			info->rule=i;
			
			nextspace=info->space+(2*info->rule-3)/2*m_N+
			1/(2*info->rule-3);
			if(nextspace<0 || nextspace>m_NUM-1 ||
				(info->space%m_N==0 && info->rule==1) ||
				(info->space%m_N==m_N-1 && info->rule==2))
			{//空格出界
				delete info;
				continue;
			}
			info->move=info->state[info->space]=info->state[nextspace];
			info->state[nextspace]='0';

			info->weight=info->depth+Start2GoalW(info->state,goal,m_NUM);
			
			m=Start2GoalS(info->state,goal,m_N,m_NUM);
			n=m_nDepth-info->depth;

			//当前结点和以前的结点是否有相同
			same=0;
			for(p=OpenFirst;p;p=p->next)
			{
				if(m>n||memcmp(p->state,info->state,m_NUM)==0)
				{
					same=-1;
					delete info;
					break;
				}
			}
			if(same==0)
				for(p=CloseFirst;p;p=p->next)
				{
					if(memcmp(p->state,info->state,m_NUM)==0)
					{
						same=-1;
						delete info;
						break;
					}
				}

			if(same==0)
			{
				//插入队列
				info->space=nextspace;
				info->next=NULL;
				info->parent=OpenFirst;

				OpenLast->next=info;
				OpenLast=info;
				Generate++;
				splitFlag=1;
			}
		}//end for
		Split+=splitFlag;

		//A*1 sort
		SortOpen(&OpenFirst);

		
		//若当前结点和目标状态相同

		if(memcmp(OpenFirst->state,goal,m_NUM)==0)
		{
			m_nResult=(m_nDepth>OpenFirst->depth)? 1: m_nResult+1;
			m_nDepth=OpenFirst->depth;
			//检查m_Resutl
			CResult *res=&m_Result[m_nResult-1];
			if(res->depth!=0)
			{
				delete[] res->moves;
				delete[] res->rules;
			}
			res->moves=new unsigned char[OpenFirst->depth];
			res->rules=new unsigned char[OpenFirst->depth];

			res->generate=Generate;
			res->split=Split;
			res->depth=OpenFirst->depth;

			for(p=OpenFirst,i=1;p->move!='0';p=p->parent,i++)
			{
				res->moves[res->depth-i]=p->move;
				res->rules[res->depth-i]=p->rule;
			}
			flag=0;
		}//end if
		//修改ＯＰＥＮ表和ＣＬＯＳＥ表
		info=OpenFirst;
		OpenFirst=OpenFirst->next;
		info->next=NULL;
		if(CloseFirst==NULL)
		{
			CloseFirst=info;
		}
		else
		{
			info->next=CloseFirst;
			CloseFirst=info;
		}
	}//end while
Exit_Label:
	//册除open表和close表
	p=OpenFirst;
	while(p)
	{
		OpenFirst=OpenFirst->next;
		delete p;
		p=OpenFirst;
	}

	p=CloseFirst;
	while(p)
	{
		CloseFirst=CloseFirst->next;
		delete p;
		p=CloseFirst;
	}

	return flag;
}

int CChessDoc::BFSA2(unsigned char *start, unsigned char *goal)
{

	CPathNode *info,*p,*OpenFirst,*OpenLast,*CloseFirst;
	UINT nextspace;
	int m,n,i,same,flag,Generate,Split;
	
	//初始化第一个节点
	info=new CPathNode(m_N);
	memcpy(info->state,start,m_NUM);
	info->space=strcspn((char*)start,"0");
	info->depth=0;
	info->move='0';
	info->rule=0;
	info->next=info->parent=NULL;

	info->weight=info->depth+Start2GoalS(info->state,goal,m_N,m_NUM);

	//初始化队列
	OpenFirst=OpenLast=info;
	CloseFirst=NULL;
	Generate=0;
	Split=0;
	flag=1;
	while(_kbhit()==0)
	{
		if(!OpenFirst || OpenFirst->depth>m_nDepth)
		{
			flag=-1;
			goto Exit_Label;
		}
		//扩展当前队列
		int splitFlag=0;
		for(i=0;i<4;i++)
		{
			if(OpenFirst->depth==m_nDepth) break;
			
			info= new CPathNode(m_N);
			info->depth=OpenFirst->depth +1;
			memcpy(info->state,OpenFirst->state,m_NUM);
			info->space=OpenFirst->space;
			info->rule=i;
			
			nextspace=info->space+(2*info->rule-3)/2*m_N+
			1/(2*info->rule-3);
			if(nextspace<0 || nextspace>m_NUM-1 ||
				(info->space%m_N==0 && info->rule==1) ||
				(info->space%m_N==m_N-1 && info->rule==2))
			{//空格出界
				delete info;
				continue;
			}
			info->move=info->state[info->space]=info->state[nextspace];
			info->state[nextspace]='0';

			info->weight=info->depth+Start2GoalS(info->state,goal,m_N,m_NUM);
			
			m=Start2GoalS(info->state,goal,m_N,m_NUM);
			n=m_nDepth-info->depth;

			//当前结点和以前的结点是否有相同
			same=0;
			for(p=OpenFirst;p;p=p->next)
			{
				if(m>n||memcmp(p->state,info->state,m_NUM)==0)
				{
					same=-1;
					delete info;
					break;
				}
			}
			if(same==0)
				for(p=CloseFirst;p;p=p->next)
				{
					if(memcmp(p->state,info->state,m_NUM)==0)
					{
						same=-1;
						delete info;
						break;
					}
				}

			if(same==0)
			{
				//插入队列
				info->space=nextspace;
				info->next=NULL;
				info->parent=OpenFirst;

				OpenLast->next=info;
				OpenLast=info;
				Generate++;
				splitFlag=1;
			}
		}//end for
		Split+=splitFlag;

		//A*1 sort
		SortOpen(&OpenFirst);

		
		//若当前结点和目标状态相同

		if(memcmp(OpenFirst->state,goal,m_NUM)==0)
		{
			m_nResult=(m_nDepth>OpenFirst->depth)? 1: m_nResult+1;
			m_nDepth=OpenFirst->depth;
			//检查m_Resutl
			CResult *res=&m_Result[m_nResult-1];
			if(res->depth!=0)
			{
				delete[] res->moves;
				delete[] res->rules;
			}
			res->moves=new unsigned char[OpenFirst->depth];
			res->rules=new unsigned char[OpenFirst->depth];

			res->generate=Generate;
			res->split=Split;
			res->depth=OpenFirst->depth;

			for(p=OpenFirst,i=1;p->move!='0';p=p->parent,i++)
			{
				res->moves[res->depth-i]=p->move;
				res->rules[res->depth-i]=p->rule;
			}
			flag=0;
		}//end if
		//修改ＯＰＥＮ表和ＣＬＯＳＥ表
		info=OpenFirst;
		OpenFirst=OpenFirst->next;
		info->next=NULL;
		if(CloseFirst==NULL)
		{
			CloseFirst=info;
		}
		else
		{
			info->next=CloseFirst;
			CloseFirst=info;
		}
	}//end while
Exit_Label:
	//册除open表和close表
	p=OpenFirst;
	while(p)
	{
		OpenFirst=OpenFirst->next;
		delete p;
		p=OpenFirst;
	}

	p=CloseFirst;
	while(p)
	{
		CloseFirst=CloseFirst->next;
		delete p;
		p=CloseFirst;
	}

	return flag;
}

int CChessDoc::BFSA3(unsigned char *start, unsigned char *goal)
{

	CPathNode *info,*p,*OpenFirst,*OpenLast,*CloseFirst;
	UINT nextspace;
	int m,n,i,same,flag,Generate,Split;
	
	//初始化第一个节点
	info=new CPathNode(m_N);
	memcpy(info->state,start,m_NUM);
	info->space=strcspn((char*)start,"0");
	info->depth=0;
	info->move='0';
	info->rule=0;
	info->next=info->parent=NULL;

	info->weight=info->depth+3*Start2GoalPS(info->state,goal,m_N,m_NUM);

	//初始化队列
	OpenFirst=OpenLast=info;
	CloseFirst=NULL;
	Generate=0;
	Split=0;
	flag=1;
	while(_kbhit()==0)
	{
		if(!OpenFirst || OpenFirst->depth>m_nDepth)
		{
			flag=-1;
			goto Exit_Label;
		}
		//扩展当前队列
		int splitFlag=0;
		for(i=0;i<4;i++)
		{
			if(OpenFirst->depth==m_nDepth) break;
			
			info= new CPathNode(m_N);
			info->depth=OpenFirst->depth +1;
			memcpy(info->state,OpenFirst->state,m_NUM);
			info->space=OpenFirst->space;
			info->rule=i;
			
			nextspace=info->space+(2*info->rule-3)/2*m_N+
			1/(2*info->rule-3);
			if(nextspace<0 || nextspace>m_NUM-1 ||
				(info->space%m_N==0 && info->rule==1) ||
				(info->space%m_N==m_N-1 && info->rule==2))
			{//空格出界
				delete info;
				continue;
			}
			info->move=info->state[info->space]=info->state[nextspace];
			info->state[nextspace]='0';

			info->weight=info->depth+3*Start2GoalPS(info->state,goal,m_N,m_NUM);
			
			m=Start2GoalS(info->state,goal,m_N,m_NUM);
			n=m_nDepth-info->depth;

			//当前结点和以前的结点是否有相同
			same=0;
			for(p=OpenFirst;p;p=p->next)
			{
				if(m>n||memcmp(p->state,info->state,m_NUM)==0)
				{
					same=-1;
					delete info;
					break;
				}
			}
			if(same==0)
				for(p=CloseFirst;p;p=p->next)
				{
					if(memcmp(p->state,info->state,m_NUM)==0)
					{
						same=-1;
						delete info;
						break;
					}
				}

			if(same==0)
			{
				//插入队列
				info->space=nextspace;
				info->next=NULL;
				info->parent=OpenFirst;

				OpenLast->next=info;
				OpenLast=info;
				Generate++;
				splitFlag=1;
			}
		}//end for
		Split+=splitFlag;

		//A*1 sort
		SortOpen(&OpenFirst);

		
		//若当前结点和目标状态相同

		if(memcmp(OpenFirst->state,goal,m_NUM)==0)
		{
			m_nResult=(m_nDepth>OpenFirst->depth)? 1: m_nResult+1;
			m_nDepth=OpenFirst->depth;
			//检查m_Resutl
			CResult *res=&m_Result[m_nResult-1];
			if(res->depth!=0)
			{
				delete[] res->moves;
				delete[] res->rules;
			}
			res->moves=new unsigned char[OpenFirst->depth];
			res->rules=new unsigned char[OpenFirst->depth];

			res->generate=Generate;
			res->split=Split;
			res->depth=OpenFirst->depth;

			for(p=OpenFirst,i=1;p->move!='0';p=p->parent,i++)
			{
				res->moves[res->depth-i]=p->move;
				res->rules[res->depth-i]=p->rule;
			}
			flag=0;
		}//end if
		//修改ＯＰＥＮ表和ＣＬＯＳＥ表
		info=OpenFirst;
		OpenFirst=OpenFirst->next;
		info->next=NULL;
		if(CloseFirst==NULL)
		{
			CloseFirst=info;
		}
		else
		{
			info->next=CloseFirst;
			CloseFirst=info;
		}
	}//end while
Exit_Label:
	//册除open表和close表
	p=OpenFirst;
	while(p)
	{
		OpenFirst=OpenFirst->next;
		delete p;
		p=OpenFirst;
	}

	p=CloseFirst;
	while(p)
	{
		CloseFirst=CloseFirst->next;
		delete p;
		p=CloseFirst;
	}

	return flag;
}

void CChessDoc::OnFileOpen() 
{
	// TODO: Add your command handler code here
	
	char  szFilter[]= "Data Files (*.dat)|*.dat|Text Files (*.txt)|*.txt|All Files (*.*)|*.*||";
	FILE *fp;
	UINT i;
	CFileDialog filedlg(TRUE,NULL,NULL,NULL,szFilter);
	
	int	ret=filedlg.DoModal();

	
	if(ret==IDOK)
	{
		CString pathName=filedlg.GetPathName();
		
		if((fp=fopen(pathName,"r"))==NULL)
		{
			AfxMessageBox("数据文件打开出错!");
			return;
		}
		fscanf(fp,"%d\n",&m_N);
		m_NUM=m_N*m_N;
		for(i=0;i<m_N;i++)
			if(m_N==3)
				fscanf(fp,"%c %c %c\n",&m_strStart[i*m_N],&m_strStart[i*m_N+1],&m_strStart[i*m_N+2]);
			else
				fscanf(fp,"%c %c %c %c\n",&m_strStart[i*m_N],&m_strStart[i*m_N+1],&m_strStart[i*m_N+2],&m_strStart[i*m_N+3]);
		fscanf(fp,"\n");
		for(i=0;i<m_N;i++)
			if(m_N==3)
				fscanf(fp,"%c %c %c\n",&m_strEnd[i*m_N],&m_strEnd[i*m_N+1],&m_strEnd[i*m_N+2]);
			else
				fscanf(fp,"%c %c %c %c\n",&m_strEnd[i*m_N],&m_strEnd[i*m_N+1],&m_strEnd[i*m_N+2],&m_strEnd[i*m_N+3]);

		fclose(fp);
	}
	m_bFileOpen=TRUE;
	UpdateAllViews(NULL);
	m_bFileOpen=FALSE;
}