18main.cpp

人工智能中的八数码问题。它由一个3×3的方阵中的八个数码构成

#include <iostream>
#include <stack>
using namespace std;

const int N = 3;
const int x[4] = { -1, 0, 1, 0 };
const int y[4] = { 0, 1, 0, -1 };
int dgoal[N*N] = { 1, 2, 3, 8, 0, 4, 7, 6, 5 };//目标
int position[N*N] = { 4, 0, 1, 2, 5, 8, 7, 6, 3 };//各数码正确位置

class DigitalState
{
	public:
		DigitalState ( void );
		DigitalState ( int cdigit[], int clayer, DigitalState* cpFather );

		int digit[N*N];//8个数码，其中0表示空格
		int spacepos;//空格位置
		int layer;//层数
		int cost;//代价
		DigitalState* pNext;//下一个结点
		DigitalState* pFather;//父结点
};

DigitalState::DigitalState ( void )
{
	layer = -1;
	cost = 0;
	pNext = 0;
	pFather =0;
}

DigitalState::DigitalState ( int cdigit[], int clayer, DigitalState* cpFather )
{
	int i,temp;
	for ( i=0; i<N*N; i++ )
	{
		digit[i] = cdigit[i];
		if ( digit[i] == 0 ) spacepos = i;
	}
	layer = clayer;
	cost = layer;
	pNext =0;
	pFather = cpFather;

	//计算代价
	for ( i=0; i<N*N; i++ )
	{
		temp = i/N - position[ digit[i] ]/N;
		if ( temp<0 ) cost = cost-temp;
		else cost = cost + temp;

		temp = i%N - position[ digit[i] ]%N;
		if ( temp<0 ) cost = cost-temp;
		else cost = cost + temp;
	}
}

	
class Diagram
{
	public:
		Diagram ( int d[] );
		~Diagram ( void );
		void AddOpenState ( DigitalState* pdstate );//增加一个结点到open列表中
		bool CompareState ( DigitalState* pdstate1, DigitalState* pdstate2 );//比较两个结点是否相同
		bool InDiagram ( DigitalState* pdstate );//判断一个结点是否在图中出现过
		DigitalState* Search ( void );//搜索
		void PrintAnswer ( void );//输出结果

	protected:
		DigitalState* closehead;
		DigitalState* closetail;
		DigitalState* openhead;
		DigitalState* opentail;
		DigitalState* goal;
		DigitalState* answer;
};

Diagram::Diagram ( int d[] )
{
	DigitalState* pdstate = new DigitalState();
	closehead = pdstate;
	closetail = pdstate;
	openhead = pdstate;
	opentail  = pdstate;

	pdstate = new DigitalState ( d, 0, 0 );
	AddOpenState ( pdstate );

	openhead = pdstate;

	goal = new DigitalState ( dgoal, 0, 0 );

	answer = 0;
}

Diagram::~Diagram ( void )
{
	if ( !closehead ) return;

	DigitalState* pdelete;
	DigitalState* p;

	pdelete = closehead;
	for ( p = pdelete->pNext; p; p = p->pNext)
	{
		if ( pdelete ) delete pdelete;
		pdelete = p;
	}
	delete pdelete;
}

void Diagram::AddOpenState(DigitalState* pdstate)
{
	DigitalState* p;
	for ( p = openhead; p->pNext; p = p->pNext )
	{
		if ( pdstate->cost < p->pNext->cost )//找到对应的位置则插入
		{
			pdstate->pNext = p->pNext;
			p->pNext = pdstate;
			return;
		}
	}
	opentail->pNext = pdstate;
	opentail = pdstate;
}

bool Diagram::CompareState(DigitalState* pdstate1, DigitalState* pdstate2)
{
	int i;
	for ( i = 0; i < N*N; i++)
	{
		if ( pdstate1->digit[i] != pdstate2->digit[i] ) return false;
	}
	return true;
}

bool Diagram::InDiagram(DigitalState* pdstate)
{
	DigitalState* p;
	for ( p = closehead->pNext; p; p = p->pNext )//closehead指向的是一个空节点
	{
		if ( CompareState ( p, pdstate ) ) return true;
	}
	return false;
}

DigitalState* Diagram::Search ( void )
{
	DigitalState* pdstate;
	DigitalState* pns;
	int i,j;
	int spaceposold,spaceposnew;
	int d[N*N];

	//open队列不为空
	while ( closetail != opentail )
	{
		pdstate = openhead;

		spaceposold = pdstate->spacepos;//空格位置
		for ( i = 0; i<4; i++ )//对于上下左右四种情况
		{
			//计算新空格位置
			spaceposnew = spaceposold+x[i]*3+y[i];
			//如果没有空格位置没有超过范围
			if ( spaceposnew >= 0 && spaceposnew < N*N )
			{
				for ( j=0; j<N*N; j++ )
				{
					d[j] = pdstate->digit[j];
				}

				//交换两个数码
				d[spaceposold] = d[spaceposnew];
				d[spaceposnew] = 0;

				//新建数码状态
				pns = new DigitalState ( d, pdstate->layer+1, pdstate );
				if ( CompareState ( goal, pns ) )//找到目标节点
				{
					answer = pns;
					return pns;
				}
				else if ( InDiagram ( pns ) )//在图中则删除该节点
				{
					delete pns;
				}
				else//不在图中则加入图
				{
					AddOpenState ( pns );
				}
			}
		}
		//将当前节点加入CLOSED列表中
		openhead = openhead->pNext;
		closetail = closetail->pNext;
	}
	return 0;
}

void Diagram::PrintAnswer ( void )
{
	int i,j;
	DigitalState* p = answer;
	stack <DigitalState*> s;
	while ( p )
	{
		s.push ( p );
		p = p->pFather;
	}
	while ( !s.empty() )
	{
		p = s.top ();
		s.pop ();
		for ( i=0; i<N; i++ )
		{
			for ( j=0; j<N; j++ )
			{
				cout<<p->digit[i*N+j]<<' ';
			}
			cout<<endl;
		}
		cout<<endl;
	}
}
void main ( void )
//void main()
{
	int d[N*N] = { 2, 8, 3, 1, 6, 4, 7, 0, 5 };
	//int d[N*N] = { 2, 8, 3, 1, 6, 4, 7, 5, 0 };
	Diagram diagram ( d );
	diagram.Search ();
	diagram.PrintAnswer ();
}