searchalg.cpp

人工智能中经典算法-宽度搜索和启发是搜索（A*算法）在VC环境下的实现代码

// SearchAlg.cpp: implementation of the CSearchAlg class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AI.h"
#include "SearchAlg.h"
#include "math.h"
#include "InitDialog.h"
#include "Inputadvdlg.h"


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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CSearchAlg::CSearchAlg()
{

}

CSearchAlg::~CSearchAlg()
{
	if(this->m_NodeList.GetCount() >0) 
		this->m_NodeList.RemoveAll();
}

/////////////////////////////////////////
//    LoadData:载入数据
/////////////////////////////////////////
BOOL CSearchAlg::LoadData(BOOL Adv)
{
	if(Adv == false)
	{
		CInitDialog InitDlg;
		if(InitDlg.DoModal()==IDOK)
		{
			CNodeState *NodeItem;NodeItem = new CNodeState;
			m_CurrentG = 0;
			for(int i=0; i<3; i++)
				for(int j=0; j<3; j++)
				{
					this->m_GoalState[i][j] = InitDlg.GetDescData(i,j);
					this->m_InitialState[i][j] = InitDlg.GetSrcData(i,j);
					NodeItem->LoadData(m_InitialState[i][j],i,j);
				}
				NodeItem->SetNodeType(AlReady);
				NodeItem->SetThisIsAAnswer();
				NodeItem->SetCurrentG(m_CurrentG);
				NodeItem->SetCurrentCount(0);
				m_CurOpItem = NodeItem;
				m_NodeList.AddTail(NodeItem);
				return TRUE;
		}
		else return FALSE;
	}
	else
	{
	 CInputAdvDlg InitDlg;
	 if(InitDlg.DoModal()==IDOK)
	 {
		CNodeState *NodeItem;NodeItem = new CNodeState;
		m_CurrentG = 0;
		for(int i=0; i<3; i++)
		 for(int j=0; j<3; j++)
		 {
			this->m_GoalState[i][j] = InitDlg.GetDescData(i,j);
			this->m_InitialState[i][j] = InitDlg.GetSrcData(i,j);
			NodeItem->LoadData(m_InitialState[i][j],i,j);
		 }
		 NodeItem->SetNodeType(AlReady);
		 NodeItem->SetThisIsAAnswer();
		 NodeItem->SetCurrentG(m_CurrentG);
		 NodeItem->SetCurrentCount(0);
		 m_CurOpItem = NodeItem;
		 m_NodeList.AddTail(NodeItem);
		return TRUE;
	 }
	 else return FALSE;
	}
}

void CSearchAlg::GenerateMoveFlag()
{
	Position BlankPosition = m_CurOpItem->GetBlankPosition();
	m_MoveFlagCount = 0;
	if(BlankPosition == Position(0,0))
	{//空白位在(0,0)
	 m_MoveFlag[Up] = FALSE;m_MoveFlag[Right] = TRUE;
	 m_MoveFlag[Down] = TRUE;m_MoveFlag[Left] = FALSE;
	 m_MoveFlagCount = 2;
	}
	else if(BlankPosition == Position(0,3-1))
	{//空白位在(0,3-1)
	 m_MoveFlag[Up] = FALSE;m_MoveFlag[Right] = FALSE;
	 m_MoveFlag[Down] = TRUE;m_MoveFlag[Left] = TRUE;
	 m_MoveFlagCount = 2;
	}
	else if(BlankPosition == Position(3-1,0))
	{//空白位在(3-1,0)
	 m_MoveFlag[Up] = TRUE;m_MoveFlag[Right] = TRUE;
	 m_MoveFlag[Down] = FALSE;m_MoveFlag[Left] = FALSE;
	 m_MoveFlagCount = 2;
	}
	else if(BlankPosition == Position(3-1,3-1))
	{//空白位在(3-1,3-1)
	 m_MoveFlag[Up] = TRUE;m_MoveFlag[Right] = FALSE;
	 m_MoveFlag[Down] = FALSE;m_MoveFlag[Left] = TRUE;
	 m_MoveFlagCount = 2;
	}
	else if(BlankPosition.x>0 && BlankPosition.x<3-1 && BlankPosition.y==0)
	{//空白位在第一列除(0,0)与(3-1,0)
	 m_MoveFlag[Up] = TRUE;m_MoveFlag[Right] = TRUE;
	 m_MoveFlag[Down] = TRUE;m_MoveFlag[Left] = FALSE;
	 m_MoveFlagCount = 3;
	}
	else if(BlankPosition.x>0 && BlankPosition.x<3-1 && BlankPosition.y==3-1)
	{//空白位在第3列除(0,3-1)与(3-1,3-1)
	 m_MoveFlag[Up] = TRUE;m_MoveFlag[Right] = FALSE;
	 m_MoveFlag[Down] = TRUE;m_MoveFlag[Left] = TRUE;
	 m_MoveFlagCount = 3;
	}
	else if(BlankPosition.y>0 && BlankPosition.y<3-1 && BlankPosition.x==0)
	{//空白位在第一行除(0,0)与(0,3-1)
	 m_MoveFlag[Up] = FALSE;m_MoveFlag[Right] = TRUE;
	 m_MoveFlag[Down] = TRUE;m_MoveFlag[Left] = TRUE;
	 m_MoveFlagCount = 3;
	}
	else if(BlankPosition.y>0 && BlankPosition.y<3-1 && BlankPosition.x==3-1)
	{//空白位在第3行 除(3-1,0)与(3-1,3-1)
	 m_MoveFlag[Up] = TRUE;m_MoveFlag[Right] = TRUE;
	 m_MoveFlag[Down] = FALSE;m_MoveFlag[Left] = TRUE;
	 m_MoveFlagCount = 3;
	}
	else
	{
	 m_MoveFlag[Up] = TRUE;m_MoveFlag[Right] = TRUE;
	 m_MoveFlag[Down] = TRUE;m_MoveFlag[Left] = TRUE;
	 m_MoveFlagCount = 4;
	}
}

//////////////////////////////////
//GenerateChild: 生成子节点
//////////////////////////////////
UINT CSearchAlg::GenerateChild()
{
	List ChildList;
	int m=0;
	for(int k=0; k<4; k++)
	{
		if(m_MoveFlag[k] == false) continue;
		CNodeState *Tmp;Tmp = new CNodeState;
		for(int i=0; i<3; i++)
			for(int j=0; j<3; j++)
				Tmp->LoadData(m_CurOpItem);
		Tmp->SetCurrentG(m_CurrentG);
		Tmp->SetCurrentCount(m++);
		Tmp->SetNodeType(NotYet);
		Tmp->MoveBlank(k);
		ChildList.AddTail(Tmp);
	}
	return FindBestMoveFlag(&ChildList);
}

///////////////////////////////////////////
// FindBestMoveFlag:寻找最佳移动方式 并移动之
//////////////////////////////////////////
UINT CSearchAlg::FindBestMoveFlag(List *pList)
{
	IsExisted(pList);
	POSITION Pos = pList->GetHeadPosition();
	int H[4]={65535,65535,65535,65535},i=0,Min = 65535;
	POSITION MinPos;
	while(Pos)
	{
	 POSITION CurPos = Pos;
	 CNodeState *Item = (CNodeState *)pList->GetNext(Pos);
	 if(Item->GetNodeType() == AlReady) {i++;continue;}
	 H[i] = ComputeH(Item);
	 if(Min>H[i]) {Min=H[i];MinPos = CurPos;}
	 i++;
	}
	
	if(Min == 65535)
	{
		return ErrorCode;//没有未扩展的结点了 本题无解
	}	

	//标记最佳解
	Pos = pList->GetHeadPosition();
	while(Pos)
	{
	 POSITION CurPos = Pos;
	 CNodeState *Item = (CNodeState *)m_NodeList.GetNext(Pos);
	 if(CurPos == MinPos) 
	 {
	  Item->SetThisIsAAnswer();//是解
	  Item->SetNodeType(AlReady);//被扩展
	  m_CurOpItem = Item;
	 }
	 m_NodeList.AddTail(Item);
	}
	return NoError;
}

//////////////////////////////////////
// IsReadyExist: 是否已经存在
//////////////////////////////////////
void CSearchAlg::IsExisted(List *pList)
{
	POSITION PosInit = pList->GetHeadPosition();
	while(PosInit)
	{
	 POSITION CurPos = PosInit;
	 CNodeState *ItemInit = (CNodeState *)pList->GetNext(PosInit);
	 POSITION PosGoal = m_NodeList.GetHeadPosition();
	 while(PosGoal)
	 {
	  CNodeState *ItemGoal = (CNodeState *)m_NodeList.GetNext(PosGoal);
	  if(ItemInit->IsEqual(ItemGoal))
	  {//已经存在于第i个结果上
	   ItemInit->SetNodeType(Cannot);
	   m_NodeList.AddTail(ItemInit);
	   pList->RemoveAt(CurPos);
	   break;
	  }
	 }
	}
}

////////////////////////////////////
// ComputeH:计算当前H值
////////////////////////////////////
int CSearchAlg::ComputeH(CNodeState *Item)
{
	int Src[3][3];
	for(int i=0; i<3; i++)
	 for(int j=0; j<3; j++)
	  Src[i][j] = Item->GetNodeData(i,j);
	int Hop = 0;
	for(i=0; i<3; i++)
	 for(int j=0; j<3; j++)
	 {
		if(Src[i][j] == m_GoalState[i][j]) continue;
		if(Src[i][j] == 0 ) continue;
		else
		{
			int Hhop = Scan(Src[i][j], Position(i,j));
			if(Hhop == 65535) return 65535;
			Hop += Hhop;
		}
	 }
return Hop;
}

//////////////////////////////////////////////
// Scan: 扫描 计算H值的辅助函数
//////////////////////////////////////////////
int CSearchAlg::Scan(int Desc,Position Srcpos)
{
	Position Descpos;
	for(int i=0;i<3;i++)
	 for(int j=0;j<3;j++)
	 {
		 if(this->m_GoalState[i][j] == Desc) 
		 {
			Descpos = Position(i,j);
			return (int)fabs(Descpos.x - Srcpos.x)
				+(int)fabs(Descpos.y-Srcpos.y);
		 }
	 }
	 return 65535;
}

///////////////////////////////////////
// FindOtherNote: 用于回溯 寻找另一个节点 
BOOL CSearchAlg::FindOtherNode(int CurrentG)
{
	POSITION pos = m_NodeList.GetTailPosition();
	while(pos)
	{
		CNodeState *Item = (CNodeState *)m_NodeList.GetPrev(pos);
		if(Item->GetCurrentG() != CurrentG) continue;//没有到当前层
		if(Item->GetNodeType() != NotYet) continue;//当前结点不是没有被扩展的结点
		m_CurOpItem = Item;
		return TRUE;
	}
	return FALSE;
}

///////////////////////////////////////////
// GetResultListPoint: 得到搜索树树根的指针
// ////////////////////////////////////////
List * CSearchAlg::GetResultListPoint()
{
	while(1)
	{
		if(m_NodeList.GetCount() >= MaxNodeNo) 
		{
			AfxMessageBox("达到最大搜索节点数，启发式搜索失败！");
			return &m_NodeList;
		}
		if(ComputeH(m_CurOpItem) == 0) 
		{
			AfxMessageBox("搜索成功！");
			return &m_NodeList;
		}
		GenerateMoveFlag();
		m_CurrentG++;
		if(GenerateChild() == NoError) continue;
		else
		{
		HWND hWnd = ::AfxGetApp()->GetMainWnd()->GetSafeHwnd();
		PostMessage(hWnd,WM_ERROR,0,ErrorCode);
		break;
		}
	}
	AfxMessageBox("搜索节点过多，未能完成启发式搜索，请重来！");
	return &m_NodeList;
}