8p.cpp

八数码问题的几种不同解法 八数码问题的几种不同解法

#include "iostream.h"
#include "8p.h"

int absv(int a)
{
	return (a<0)?(-a):a;
}

BoardState::BoardState(char *InitState)
{
	char i,j,x,y;
	for(i = 0 ; i < 3 ; i++)
		for(j = 0 ; j < 3 ; j++)
		{
			m_State[i][j] = InitState[i*3+j];
			if(!InitState[i*3+j])
			{
				x = j;
				y = i;
			}
		}
	for(i = 0 ; i < 3 ; i++)
		m_bUnsearchedMove[i] = 1;
	if(x == 0)
		m_bUnsearchedMove[2] = 0;
	else if(x == 2)
		m_bUnsearchedMove[0] = 0;
	if(y == 0)
		m_bUnsearchedMove[1] = 0;
	else if(y == 2)
		m_bUnsearchedMove[3] = 0;
	m_nDepth = 0;
	m_PrevMove = -1;
	Evaluate();
}

BoardState::BoardState(BoardState &PrevState, char nCommand)
{
	char i,j,x,y;
	for(i = 0 ; i < 3 ; i++)
		for(j = 0 ; j < 3 ; j++)
		{
			m_State[i][j] = PrevState.m_State[i][j];
			if(!PrevState.m_State[i][j])
			{
				x = j;
				y = i;
			}
		}
	switch(nCommand)
	{
	case 0:
		m_State[y][x] = m_State[y][x+1];
		m_State[y][x+1] = 0;
		++x;
		break;
	case 1:
		m_State[y][x] = m_State[y-1][x];
		m_State[y-1][x] = 0;
		--y;
		break;
	case 2:
		m_State[y][x] = m_State[y][x-1];
		m_State[y][x-1] = 0;
		--x;
		break;
	case 3:
		m_State[y][x] = m_State[y+1][x];
		m_State[y+1][x] = 0;
		++y;
		break;
	}
	for(i = 0 ; i < 4 ; i++)
		m_bUnsearchedMove[i] = 1;
	if(nCommand == 0 || nCommand == 2)
		m_bUnsearchedMove[2-nCommand] = 0;
	else m_bUnsearchedMove[4-nCommand] = 0;
	//prevent the repeated move
	if(x == 0)
		m_bUnsearchedMove[2] = 0;
	else if(x == 2)
		m_bUnsearchedMove[0] = 0;
	if(y == 0)
		m_bUnsearchedMove[1] = 0;
	else if(y == 2)
		m_bUnsearchedMove[3] = 0;
	//prevent impossible move
	m_nDepth = PrevState.m_nDepth + 1;
	m_PrevMove = nCommand;
	Evaluate();
}

void BoardState::Evaluate()
{
	int h = 0;
	char i,j,k;
	for(i = 0 ; i < 3 ; i++)
		for(j = 0 ; j < 3 ; j++)
			for(k = 0 ; k < 9 ; k++)
				if(GOAL[i][j] && (GOAL[i][j] == *(*m_State+k)))
				{
					h += absv(i-k/3);
					h += absv(k%3-j);
					break;
				}
	m_Evaluation = h + m_nDepth;
	//h is the "Manhattan distance"
}

SolutionStructure::SolutionStructure(char *InitState)
{
	m_pSolutionSequence = 0;
	m_NodeCount = 0;

	BoardState *pBS = new BoardState(InitState);
	m_pRoot = new BSNode(pBS);
	m_pQueueHead = new BSLink(m_pRoot);
}

void SolutionStructure::Expand()
{
	BSLink *pt = m_pQueueHead;
	char i;
	for(i = 0 ; i < 4 ; i++)
		if(pt->m_pBSN->m_pCurrentBS->m_bUnsearchedMove[i])
		{
			BoardState *pBS = new BoardState(*pt->m_pBSN->m_pCurrentBS, i);
			AddBSN(new BSNode(pBS, pt->m_pBSN));
		}
	m_pQueueHead = m_pQueueHead->m_pNext;
	m_pQueueHead->m_pPrev = 0;
	delete pt;
}

void SolutionStructure::AddBSN(BSNode *pBSN)
{
	int Evaluation = pBSN->m_pCurrentBS->m_Evaluation;
	BSLink *pBSL, *ptBSL;
	for(pBSL = m_pQueueHead, ptBSL = 0 ; pBSL ; pBSL = pBSL->m_pNext)
	{
		if(Evaluation < pBSL->m_pBSN->m_pCurrentBS->m_Evaluation)
			break;
		ptBSL = pBSL;
	}
	BSLink *pNewBSL = new BSLink(pBSN, ptBSL, pBSL);
	if(ptBSL)
		ptBSL->m_pNext = pNewBSL;
	if(pBSL)
		pBSL->m_pPrev = pNewBSL;
	++m_NodeCount;
}

void SolutionStructure::Clear()
{
	BSLink *pBSL, *ptBSL;
	for(pBSL = m_pQueueHead ; pBSL ; )
	{
		ptBSL = pBSL->m_pNext;
		delete pBSL->m_pBSN->m_pCurrentBS;
		delete pBSL->m_pBSN;
		delete pBSL;
		pBSL = ptBSL;
	}
}

int SolutionStructure::Solve()
{
	double s = 0;
	int MaxDepth = 0;
	while(!m_pQueueHead->m_pBSN->m_pCurrentBS->GoalState())
	{
		if(m_pQueueHead->m_pBSN->m_pCurrentBS->m_nDepth > MaxDepth)
		{
			++MaxDepth;
			s = s * 1.4 + 1.4;
			//s keeps the value of the number of nodes expanded when b*=1.5
		}
		if(m_NodeCount>s && MaxDepth>10)
		{
			Clear();
			return MaxDepth;
		}
		Expand();
	}
	char i = m_pQueueHead->m_pBSN->m_pCurrentBS->m_nDepth;
	m_pSolutionSequence = new char[i+1];
	m_pSolutionSequence[i] = 0;
	BSNode *pBSN = m_pQueueHead->m_pBSN;
	for(--i ; i >= 0 ; i--)
	{
		m_pSolutionSequence[i] = pBSN->m_pCurrentBS->m_PrevMove+1;
		pBSN = pBSN->m_pFatherBSN;
	}
	Clear();
	return 0;
}

double order(double a, int b)
{
	double t = 1;
	for( ; b > 0 ; b--)
		t *= a;
	return t;
}

double AverageBreath(int Steps, int NodesExpanded)
{	
	double a = 1.0;
	double b = 3.0;
	double e;
	do
	{
		e = (order((a+b)/2, Steps+1)-(a+b)/2)/((a+b)/2-1) - NodesExpanded;
		if(e > 0.2)
			b = (a+b)/2;
		else if(e < -0.2)
			a = (a+b)/2;
		else break;
	}
	while(1);
	return (a+b)/2;
}

void main()
{
	char State[9];
	int i,t,s = 0;
	cout<<"Input the initial state here('0' for space):"<<endl;
	for(i = 0 ; i < 9 ; i++)
	{
		cin>>t;
		s += t*t;
		State[i] = t;
	}
	if(s != 204)
		cout<<"Illegal board state."<<endl;
	else
	{
		SolutionStructure ss(State);
		if(!(t = ss.Solve()))
		{
			for(i = 0 ; *(ss.Solution()+i) ; i++)
				cout<<int(*(ss.Solution()+i))<<endl;
			cout<<"Total steps:"<<i<<endl;
			cout<<"Total nodes expanded:"<<ss.GetNodeCount()<<endl;
			if(i)
				cout<<"Average breath = "<<AverageBreath(i, ss.GetNodeCount())<<endl;
		}
		else
		{
			cout<<"No solution available!"<<endl;
			cout<<"Deepest node expanded:"<<t<<endl;
			cout<<"Total nodes expanded:"<<ss.GetNodeCount()<<endl;
			cout<<"Average breath = "<<AverageBreath(t, ss.GetNodeCount())<<endl;
		}
	}
}