bfsalg.cpp

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

// BfsAlg.cpp: implementation of the CBfsAlg class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AI.h"
#include "BfsAlg.h"
#include "initdialog.h"
#include "inputadvdlg.h"
#include "nodestate.h"

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

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

//!!!!!

CBfsAlg::CBfsAlg()
{
	m_MoveFlagCount=1;
	m_GsNodes=1;
}

CBfsAlg::~CBfsAlg()
{
}


//////////////////////
BOOL CBfsAlg::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);
				m_OpenList.AddTail(NodeItem);
				//!!!
				depth=InitDlg.m_Depth;
				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;
	}
}

////////////////////////////////////
// GenerateMoveFlag : 穷举空白位的移动方式
// m_MoveFlagCount :  同时记录共几种移动方式
///////////////////////////////////
void CBfsAlg::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 CBfsAlg::GenerateChild()
{
	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);
		m_NodeList.AddTail(Tmp);
		m_GsNodes++;
		if(Tmp->IsEqual(m_GoalState))
			return 0;
	}
	return 1;
}






List * CBfsAlg::GetResultListPoint()
{
	int Isok=1;
	for(int i=0;i<depth;i++)
	{
		if( m_NodeList.GetCount() >= MaxNodeNo)
		{
			AfxMessageBox("达到最大搜索节点数，广度优先搜索失败！");
			return &m_NodeList;		
		}
		m_CurrentG++;
		POSITION pos = m_NodeList.GetHeadPosition();
		while (pos) 
		{
			CNodeState *Item = (CNodeState *)m_NodeList.GetNext(pos);
			if(Item->GetCurrentG()==i)
			{
				m_CurOpItem= Item;
				GenerateMoveFlag();
				Isok=GenerateChild();
				if(Isok==0)return &m_NodeList;
			}
		}
	}
	return &m_NodeList;
}