basemethod.cpp

两个人工智能小程序

// BaseMethod.cpp : implementation file
//

#include "stdafx.h"
#include "AIWork2.h"
#include "BaseMethod.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CBaseMethod

CBaseMethod::CBaseMethod()
{
	OpenList=new CList<OPEN,OPEN>;
	ClosedList=new CList<CLOSED,CLOSED>;
	IsSuccess=FALSE;
	CanOutPut=FALSE;
	m_witchone=1;
	m_SearchDepth=10000;
}

CBaseMethod::~CBaseMethod()
{
	OpenList->RemoveAll();
	ClosedList->RemoveAll();
	if(OpenList)
		delete OpenList;
	if(ClosedList)
		delete ClosedList;
}


BEGIN_MESSAGE_MAP(CBaseMethod, CView)
	//{{AFX_MSG_MAP(CBaseMethod)
		// NOTE - the ClassWizard will add and remove mapping macros here.
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBaseMethod message handlers
void CBaseMethod::OnDraw(CDC* pDC)
{
	
	// 输出最后成功后的移动步骤
	CPen *oldPen;
	CString m_strOutHelp;
	CString m_Method;
	m_strOutHelp.Format("%d",m_SearchDepth);
	m_Method.Format("%d",m_witchone);
	pDC->SetTextColor(RGB(10,20,222));
	pDC->TextOut(0,0,"请设定你要解决的8数码问题 方法"+m_Method+ "(状态数限制"+m_strOutHelp+")");
	pDC->SetTextColor(RGB(0,0,0));

	m_tableLU=CPoint(0,40);
	m_tableRD=CPoint(90,130);

	//画出表格，表示各个状态
	CPen newPen(PS_SOLID,1,RGB(255,0,0));
	oldPen=pDC->SelectObject(&newPen);
	pDC->Rectangle(m_tableLU.x,m_tableLU.y,m_tableRD.x,m_tableRD.y);
	pDC->MoveTo(m_tableLU.x+30,m_tableLU.y);
	pDC->LineTo(m_tableLU.x+30,m_tableRD.y);
	pDC->MoveTo(m_tableLU.x+60,m_tableRD.y);
	pDC->LineTo(m_tableLU.x+60,m_tableLU.y);
	pDC->MoveTo(m_tableLU.x,m_tableLU.y+30);
	pDC->LineTo(m_tableRD.x,m_tableLU.y+30);
	pDC->MoveTo(m_tableLU.x,m_tableLU.y+60);
	pDC->LineTo(m_tableRD.x,m_tableLU.y+60);
	m_strOutHelp.Format("%d",basematrix[0][0]);
	pDC->TextOut(m_tableLU.x+10,m_tableLU.y+8,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[0][1]);
	pDC->TextOut(m_tableLU.x+40,m_tableLU.y+8,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[0][2]);
	pDC->TextOut(m_tableLU.x+70,m_tableLU.y+8,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[1][0]);
	pDC->TextOut(m_tableLU.x+10,m_tableLU.y+38,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[1][1]);
	pDC->TextOut(m_tableLU.x+40,m_tableLU.y+38,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[1][2]);
	pDC->TextOut(m_tableLU.x+70,m_tableLU.y+38,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[2][0]);
	pDC->TextOut(m_tableLU.x+10,m_tableLU.y+68,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[2][1]);
	pDC->TextOut(m_tableLU.x+40,m_tableLU.y+68,m_strOutHelp);
	m_strOutHelp.Format("%d",basematrix[2][2]);
	pDC->TextOut(m_tableLU.x+70,m_tableLU.y+68,m_strOutHelp);
	pDC->SelectObject(oldPen);
	if(IsSuccess)
	{
		m_tableLU.x=m_tableLU.x+100;
		m_tableRD.x=m_tableRD.x+100;
		int xZero=m_xIndex;
		int yZero=m_yIndex;
		POSITION pos=OpenList->GetTailPosition();
		OPEN OutPut;
		OpenList->GetPrev(pos);
		int PathCount=0;
		for(;pos;OpenList->GetPrev(pos))
		{
			OutPut=OpenList->GetAt(pos);
			PathCount++;

			memcpy(destmatrix,OutPut.matrix,9);
			pDC->Rectangle(m_tableLU.x,m_tableLU.y,m_tableRD.x,m_tableRD.y);
			pDC->MoveTo(m_tableLU.x+30,m_tableLU.y);
			pDC->LineTo(m_tableLU.x+30,m_tableRD.y);
			pDC->MoveTo(m_tableLU.x+60,m_tableRD.y);
			pDC->LineTo(m_tableLU.x+60,m_tableLU.y);
			pDC->MoveTo(m_tableLU.x,m_tableLU.y+30);
			pDC->LineTo(m_tableRD.x,m_tableLU.y+30);
			pDC->MoveTo(m_tableLU.x,m_tableLU.y+60);
			pDC->LineTo(m_tableRD.x,m_tableLU.y+60);

			pDC->SetTextColor(RGB(0,0,0));
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<3;j++)
				{
					m_strOutHelp.Format("%d",destmatrix[i][j]);
					if(destmatrix[i][j]==0)
					{
						pDC->SetTextColor(RGB(10,10,233));
						pDC->TextOut(m_tableLU.x+10+j*30,m_tableLU.y+8+i*30,m_strOutHelp);
						pDC->SetTextColor(RGB(0,0,0));
					}
					else
						pDC->TextOut(m_tableLU.x+10+j*30,m_tableLU.y+8+i*30,m_strOutHelp);
				}
			}		
			m_tableLU.x=m_tableLU.x+100;
			m_tableRD.x=m_tableRD.x+100;
			if(m_tableLU.x>800)
			{
				m_tableLU.x=0;
				m_tableLU.y=m_tableLU.y+100;
				m_tableRD.x=90;
				m_tableRD.y=m_tableRD.y+100;
			}
		}
		m_strOutHelp.Format("%d",PathCount);
		pDC->TextOut(0,20,"需要"+m_strOutHelp+"步才可以到达目标状态");
	}	
	else
	{
		if(CanOutPut)
			pDC->TextOut(0,20,"这个问题很费时间，在一定时间内我无能为力。");
	}
}
BOOL CBaseMethod::OnResolve()
{
	//放入OPEN
	IsSuccess=FALSE;
	OpenList->RemoveAll();
	ClosedList->RemoveAll();
	OPEN First;
	
	memcpy(First.matrix,basematrix,9);
	First.returnPoint=0;
	First.gValue=0;
	First.hValue=CreateHValue(First.matrix);
	OpenList->AddTail(First);
	int SelfNum=1;
	while(!OpenList->IsEmpty())
	{
		OPEN BestNode=ChooseMinFromOpen();//找最佳Node
		
		CLOSED CloseNode;
		CloseNode.SelfNumber=SelfNum;//放入CloseList
		memcpy(CloseNode.matrix,BestNode.matrix,9);
		CloseNode.returnPoint=BestNode.returnPoint;
		CloseNode.gValue=BestNode.gValue;
		CloseNode.hValue=BestNode.hValue;
		ClosedList->AddTail(CloseNode);

		if(IsGetGoal(BestNode.matrix))//是否达到目标节点
		{
			IsSuccess=TRUE;
			CanOutPut=FALSE;
			CreateOutputList();
			return TRUE;
		}
		if((ClosedList->GetCount()+OpenList->GetCount())>=m_SearchDepth)
		{
			IsSuccess=FALSE;
			CanOutPut=TRUE;
			return FALSE;
		}
		SearchZeroIndex(BestNode.matrix);
		OPEN Successor=BestNode;
		if(m_yIndex<2)//向右走一步看看
		{
			Successor.matrix[m_xIndex][m_yIndex]=Successor.matrix[m_xIndex][m_yIndex+1];
			Successor.matrix[m_xIndex][m_yIndex+1]=0;
			Successor.returnPoint=SelfNum;
			Successor.gValue=BestNode.gValue+1;//深度加1
			Successor.hValue=CreateHValue(Successor.matrix);
			if(!IsInOpenList(Successor))
			{
				if(!IsInClosedList(Successor))
					OpenList->AddTail(Successor);
			}
		}
		Successor=BestNode;
		if(m_xIndex<2)//向下走一步看看
		{
			Successor.matrix[m_xIndex][m_yIndex]=Successor.matrix[m_xIndex+1][m_yIndex];
			Successor.matrix[m_xIndex+1][m_yIndex]=0;
			Successor.returnPoint=SelfNum;
			Successor.gValue=BestNode.gValue+1;//深度加1
			Successor.hValue=CreateHValue(Successor.matrix);
			if(!IsInOpenList(Successor))
			{
				if(!IsInClosedList(Successor))
					OpenList->AddTail(Successor);
			}
		}
		Successor=BestNode;
		if(m_yIndex>0)//向左走一步看看
		{
			Successor.matrix[m_xIndex][m_yIndex]=Successor.matrix[m_xIndex][m_yIndex-1];
			Successor.matrix[m_xIndex][m_yIndex-1]=0;
			Successor.returnPoint=SelfNum;
			Successor.gValue=BestNode.gValue+1;//深度加1
			Successor.hValue=CreateHValue(Successor.matrix);
			if(!IsInOpenList(Successor))
			{
				if(!IsInClosedList(Successor))
					OpenList->AddTail(Successor);
			}
		}
		Successor=BestNode;
		if(m_xIndex>0)//向上走一步看看
		{
			Successor.matrix[m_xIndex][m_yIndex]=Successor.matrix[m_xIndex-1][m_yIndex];
			Successor.matrix[m_xIndex-1][m_yIndex]=0;
			Successor.returnPoint=SelfNum;
			Successor.gValue=BestNode.gValue+1;//深度加1
			Successor.hValue=CreateHValue(Successor.matrix);
			if(!IsInOpenList(Successor))
			{
				if(!IsInClosedList(Successor))
					OpenList->AddTail(Successor);
			}
		}
		SelfNum++;
	}
	return FALSE;
}

OPEN CBaseMethod::ChooseMinFromOpen()
{
	POSITION pos=OpenList->GetHeadPosition();
	OPEN MINNODE,tempNode;
	POSITION deletePos;
	tempNode=OpenList->GetAt(pos);
	MINNODE=tempNode;
	deletePos=pos;
	int min=tempNode.gValue+tempNode.hValue;
	OpenList->GetNext(pos);
	for(;pos;OpenList->GetNext(pos))
	{
		tempNode=OpenList->GetAt(pos);
		if((tempNode.gValue+tempNode.hValue)<min)
		{
			min=tempNode.gValue+tempNode.hValue;
			MINNODE=tempNode;
			deletePos=pos;
		}
	}
	OpenList->RemoveAt(deletePos);
	return MINNODE;
}

BOOL CBaseMethod::IsGetGoal(BYTE matrix[][3])
{
	int i,j;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(matrix[i][j]!=destmatrix[i][j])
				return FALSE;
		}
	}
	return TRUE;
}
BOOL CBaseMethod::SearchZeroIndex(BYTE matrix[][3])
{
	int i,j;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(matrix[i][j]==0)
			{
				m_xIndex=i;
				m_yIndex=j;
				return TRUE;
			}
		}
	}
	return FALSE;
}

int CBaseMethod::CreateHValue(BYTE matrix[][3])
{
	if(m_witchone==1)
	{//宽度优先
		return 0;
	}
	if(m_witchone==2)
	{//偏移量函数
		int i,j;
		int HValue=0;
		for(i=0;i<3;i++)
		{
			for(j=0;j<3;j++)
			{
				if(matrix[i][j]!=destmatrix[i][j])
					HValue++;
			}
		}
		return HValue;
	}
	if(m_witchone==3)
	{//距离正确位置的偏移量和
		int i,j,m,n;
		int HValue=0;
		BOOL flag=FALSE;
		for(i=0;i<3;i++)
		{
			for(j=0;j<3;j++)
			{
				flag=FALSE;
				for(m=0;m<3;m++)
				{
					for(n=0;n<3;n++)
					{
						if(matrix[i][j]==destmatrix[m][n])
						{
							HValue+=abs(i-m)+abs(j-n);
							flag=TRUE;
							break;
						}
					}
					if(flag==TRUE)
						break;
				}
			}
		}
		return HValue;
	}
	return 0;
}

BOOL CBaseMethod::IsInOpenList(OPEN opElem)
{
	POSITION pos=OpenList->GetHeadPosition();
	for(;pos;OpenList->GetNext(pos))
	{
		if(IsTheSame(opElem.matrix,OpenList->GetAt(pos).matrix))
		{
			if((opElem.gValue+opElem.hValue)<(OpenList->GetAt(pos).gValue+OpenList->GetAt(pos).hValue))
			{
				OpenList->GetAt(pos).returnPoint=opElem.returnPoint;
				OpenList->GetAt(pos).gValue=opElem.gValue;
				OpenList->GetAt(pos).hValue=opElem.hValue;
				return TRUE;
			}
		}
	}
	return FALSE;	
}

BOOL CBaseMethod::IsInClosedList(OPEN clElem)
{
	POSITION pos=ClosedList->GetHeadPosition();
	for(;pos;ClosedList->GetNext(pos))
	{
		if(IsTheSame(clElem.matrix,ClosedList->GetAt(pos).matrix))
		{
			if((clElem.gValue+clElem.hValue)<(ClosedList->GetAt(pos).gValue+ClosedList->GetAt(pos).hValue))
			{
				ClosedList->GetAt(pos).returnPoint=clElem.returnPoint;
				ClosedList->GetAt(pos).gValue=clElem.gValue;
				ClosedList->GetAt(pos).hValue=clElem.hValue;
			}
			return TRUE;
		}
	}
	return FALSE;	
}
BOOL CBaseMethod::IsTheSame(BYTE matrix1[][3], BYTE matrix2[][3])
{
	int i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
		{
			if(matrix1[i][j]!=matrix2[i][j])
				return FALSE;
		}
	return TRUE;
}

void CBaseMethod::CreateOutputList()
{
	OpenList->RemoveAll();
	POSITION pos=ClosedList->GetTailPosition();
	int returnPoint;
	OPEN Output;
	CLOSED closMem;
	closMem=ClosedList->GetAt(pos);
	memcpy(Output.matrix,closMem.matrix,9);
	OpenList->AddTail(Output);
	for(;pos;ClosedList->GetPrev(pos))
	{
		returnPoint=closMem.returnPoint;
		for(;pos;ClosedList->GetPrev(pos))
		{
			closMem=ClosedList->GetAt(pos);
			if(returnPoint==closMem.SelfNumber)
			{
				returnPoint=closMem.returnPoint;
				memcpy(Output.matrix,closMem.matrix,9);
				OpenList->AddTail(Output);
				break;
			}
		}
		if(pos)
			ClosedList->GetNext(pos);
		else
			break;
	}
}

void CBaseMethod::SetDepth(int m_Depth)
{
	m_SearchDepth=m_Depth;
}

void CBaseMethod::SetWitchOne(int witch)
{
	m_witchone=witch;
}