aiwork1view.cpp

两个人工智能小程序

void CAIWork1View::OnConfig() 
{
	// TODO: Add your command handler code here
	CConfigDlg dlg;
	if(dlg.DoModal()==IDOK)
	{
		m_iDepth=dlg.m_iDataLength;
		m_strBeginInfo.Format("输入你要解决的问题。(步数限制%d步)",m_iDepth);
		m_dataList.Init();
		m_strPathCount=_T("");
		Invalidate();
		//初始化8数码数组
		matrix[0][0]=m_store[0][0];
		matrix[0][1]=m_store[0][1];
		matrix[0][2]=m_store[0][2];
		matrix[1][0]=m_store[1][0];
		matrix[1][1]=m_store[1][1];///要移动的点
		matrix[1][2]=m_store[1][2];
		matrix[2][0]=m_store[2][0];
		matrix[2][1]=m_store[2][1];
		matrix[2][2]=m_store[2][2];
		m_hitAgain=FALSE;
	}
}

void CAIWork1View::OnEight() 
{
	// TODO: Add your command handler code here
	//输入你要解决的8数码问题
	CEightSetDlg dlg;
	if(dlg.DoModal()==IDOK)
	{
		if(m_bIsEight==FALSE)
		{
			m_bIsEight=TRUE;
			m_bIsFifteen=FALSE;
			m_iLMatrix=3;
		}
		//初始化8数码数组
		m_store[0][0]=matrix[0][0]=dlg.m_edit1;
		m_store[0][1]=matrix[0][1]=dlg.m_edit2;
		m_store[0][2]=matrix[0][2]=dlg.m_edit3;
		m_store[1][0]=matrix[1][0]=dlg.m_edit4;
		m_store[1][1]=matrix[1][1]=dlg.m_edit5;///要移动的点
		m_store[1][2]=matrix[1][2]=dlg.m_edit6;
		m_store[2][0]=matrix[2][0]=dlg.m_edit7;
		m_store[2][1]=matrix[2][1]=dlg.m_edit8;
		m_store[2][2]=matrix[2][2]=dlg.m_edit9;
		m_hitAgain=FALSE;
		for(int i=0;i<m_iLMatrix;i++)
			for(int j=0;j<m_iLMatrix;j++)
				if(m_store[i][j]==0)
				{
					//记录0的位置
					m_xZero=i;
					m_yZero=j;
					break;
				}
		m_dataList.Init();
		m_strPathCount=_T("");
		Invalidate();

	}
}

void CAIWork1View::OnUpdateEight(CCmdUI* pCmdUI) 
{
	// TODO: Add your command update UI handler code here
	pCmdUI->SetCheck(m_bIsEight);
}

void CAIWork1View::OnResolve() 
{
	// TODO: Add your command handler code here
	m_strBeginInfo.Format("输入你要解决的问题。(步数限制%d步)",m_iDepth);
	if(m_hitAgain)
		MessageBox("下面已经显示计算结果，请重新出题","警告");
	else
	{
		m_strBeginInfo+=" 开始解题，请耐心等待...........";
		CClientDC dc(this);
		dc.TextOut(300,0,"开始解题，请耐心等待...........");
		Invalidate();
		m_dataList.Init();
		if(m_bIsEight)
		{
			int timecount=GetTickCount();//取初始时间
			//开始递归
			m_iDirection=RIGHT;
			for(int i=0;i<m_iLMatrix;i++)
				for(int j=0;j<m_iLMatrix;j++)
					m_sData.datakey[i][j]=matrix[i][j];
			m_sData.direction=m_iDirection;
			m_dataList.Push(m_sData);
			if(BACKTRACK(m_xZero,m_yZero))
			{	
				//成功找到策略
				IsFinish=TRUE;
				m_strPathCount.Format("需要 %d 步才能到达目标状态。",m_dataList.Length()-1);
				m_strTime.Format("花费时间: %d ms",GetTickCount()-timecount);
				m_strPathCount+=m_strTime;
			}
			else
			{
				//解题失败
				m_strPathCount="我无能为力，在限制步数内无法达到目标状态。";
				m_strTime.Format("花费时间: %d ms",GetTickCount()-timecount);
				m_strPathCount+=m_strTime;
				Invalidate(NULL);
			}
			m_strBeginInfo.Format("输入你要解决的问题。(步数限制%d步)",m_iDepth);
		}
		m_hitAgain=TRUE;
	}
}
//按照右，下，左，上的顺序依次搜索
BOOL CAIWork1View::BACKTRACK(int xZero,int yZero)
{
	if(IsLegal())
		return TRUE;
	if(IsInList())
	{	//恢复一下
		TurnBack(xZero,yZero);
		return FALSE;
	}
	if(m_dataList.Length()>m_iDepth)
	{//强制变相
		TurnBack(xZero,yZero);
		return FALSE;
	}
	if(yZero!=m_iLMatrix-1)//Right
	{
		matrix[xZero][yZero]=matrix[xZero][yZero+1];
		matrix[xZero][yZero+1]=0;
	
		m_iDirection=RIGHT;
		for(int i=0;i<m_iLMatrix;i++)
		{
			for(int j=0;j<m_iLMatrix;j++)
			{
				m_sData.datakey[i][j]=matrix[i][j];
			}
		}
		m_sData.direction=m_iDirection;
		m_dataList.Push(m_sData);
		if(BACKTRACK(xZero,yZero+1))
			return TRUE;
	}	
	if(xZero!=m_iLMatrix-1)//Down
	{
		matrix[xZero][yZero]=matrix[xZero+1][yZero];
		matrix[xZero+1][yZero]=0;
		m_iDirection=DOWN;
		for(int i=0;i<m_iLMatrix;i++)
		{
			for(int j=0;j<m_iLMatrix;j++)
			{
				m_sData.datakey[i][j]=matrix[i][j];
			}
		}
		m_sData.direction=m_iDirection;
		m_dataList.Push(m_sData);
		if(BACKTRACK(xZero+1,yZero))
			return TRUE;
	}
	if(yZero!=0)//Left
	{
		matrix[xZero][yZero]=matrix[xZero][yZero-1];
		matrix[xZero][yZero-1]=0;
		m_iDirection=LEFT;
		for(int i=0;i<m_iLMatrix;i++)
		{
			for(int j=0;j<m_iLMatrix;j++)
			{
				m_sData.datakey[i][j]=matrix[i][j];
			}
		}
		m_sData.direction=m_iDirection;
		m_dataList.Push(m_sData);
		if(BACKTRACK(xZero,yZero-1))
			return TRUE;
	}
	if(xZero!=0)	//UP
	{
		matrix[xZero][yZero]=matrix[xZero-1][yZero];
		matrix[xZero-1][yZero]=0;
		m_iDirection=UP;
		for(int i=0;i<m_iLMatrix;i++)
		{
			for(int j=0;j<m_iLMatrix;j++)
			{
				m_sData.datakey[i][j]=matrix[i][j];
			}
		}
		m_sData.direction=m_iDirection;
		m_dataList.Push(m_sData);
		if(BACKTRACK(xZero-1,yZero))
			return TRUE;
	}
	TurnBack(xZero,yZero);
	return FALSE;
}
//判断Datalist中是否存在，如果有，则回溯
BOOL CAIWork1View::IsInList()
{
	datastruct receive;
	for(int k=0;k<m_dataList.Length()-1;k++)
	{
		int CountFlag=0;
		receive=m_dataList.IndexValue(k);
		for(int i=0;i<m_iLMatrix;i++)
		{
			for(int j=0;j<m_iLMatrix;j++)
			{
				if(receive.datakey[i][j]==matrix[i][j])
					CountFlag++;
			}
		}
		if(CountFlag==(m_iLMatrix*m_iLMatrix))
			return TRUE;
	}
	return FALSE;
}
//判断是否到达最后正确的结果
BOOL CAIWork1View::IsLegal()
{
	int count=1;
	for(int i=0;i<m_iLMatrix;i++)
	{
		for(int j=0;j<m_iLMatrix;j++)
		{
			if(matrix[m_iLMatrix-1][m_iLMatrix-1]!=0)
				return FALSE;
			if((i==m_iLMatrix-1)&&j==m_iLMatrix-1)
			{                         //最后一位为0
				if(matrix[i][j]==0)
					return TRUE;
			}
			if(matrix[i][j]!=count)
				return FALSE;
			count++;
		}
	}
	return TRUE;
}
//当回溯的时候,恢复到上步的状态
void CAIWork1View::TurnBack(int &xZero,int &yZero)
{
	Direction recForce=(Direction)m_dataList.PopDirection();//恢复一下
	switch(recForce)
	{
	case RIGHT:
		matrix[xZero][yZero]=matrix[xZero][yZero-1];	
		matrix[xZero][yZero-1]=0;
		break;
	case DOWN:
		matrix[xZero][yZero]=matrix[xZero-1][yZero];
		matrix[xZero-1][yZero]=0;
		break;
	case LEFT:
		matrix[xZero][yZero]=matrix[xZero][yZero+1];
		matrix[xZero][yZero+1]=0;
		break;
	case UP:
		matrix[xZero][yZero]=matrix[xZero+1][yZero];
		matrix[xZero+1][yZero]=0;
		break;
	}
}

void CAIWork1View::OnInitialUpdate() 
{
	CScrollView::OnInitialUpdate();
	
	// TODO: Add your specialized code here and/or call the base class

	CSize sizeTotal;
	sizeTotal.cx=1000;
	sizeTotal.cy=5000;
	SetScrollSizes(MM_TEXT,sizeTotal);
}