1.cpp

人工智能运用广度优先算法来解决八数码问题,由初始状态到目标状态按层搜索

#include <iostream.h>
#include <iomanip.h>
#include <stdio.h>

struct open
{
	int fatherbh;
	int data[9];
//	struct open *next;
	bool operator == ( open& da ){ 
		for( int i =0 ; i<9 ; ++i ){
			if( da.data[i] != data[i] ) return false ;
		}//for
		return true ;
	}// operator ==
	
};


struct closed
{
	int pos;
	int data[9];
	int fatherBH;
//	struct closed *next;
	bool operator == ( closed& da ){ 
		for( int i =0 ; i<9 ; ++i ){
			if( da.data[i] != data[i] ) return false ;
		}//for
		return true ;
	}// operator ==
	friend ostream& operator<<( ostream& out , closed da ) ;
}startspace ,aimspace ;

ostream& operator<<( ostream& out , closed da )
{

	for( int i=0 ; i<9 ; ++i ){ 
		out<< da.data[i] << setw( 2 ) ;
		if( (i+1)%3 == 0 ) cout<< endl ;
	}//for

	cout<< endl ;
	return out ;
}

/////////////////////////////////////////////
//定义一个队列的类
template < class T >
class Formation{
	T* Top ;
	T* Bottle ;
	
public:
	Formation( ) ;
	void PushElem( T& data ) ;
	void PopElem ( T& data ) ;
	void PopFromBottle( T& data ) ;
	bool Full(){ return Top == Bottle ? false : true ; }
	bool Find( T& data ) ;
	T GetElem(){ return *( Bottle - 1 ) ; } 
} ;

template < class T >
Formation< T >::Formation()
{
		Top = Bottle = new T[1000 ] ;
}
// 数据的输入
template < class T >
void Formation< T >::PushElem( T& data )
{
	//为了方便没有判断是否越界
	*Bottle = data ;
	Bottle++ ;
}//PushElem()

// 数据的删除
template < class T >
void Formation< T >::PopElem( T& data )
{
	data = *Top ;
	Top++ ;
}//PopElem()

template < class T >
void Formation< T >::PopFromBottle( T& data )
{
	data = *( --Bottle ) ;
}

// 查找数据
template < class T >
bool Formation< T >::Find( T& data )
{
	T* pd ;
	for( pd = Top ; pd != Bottle ; ++pd ){
		if( data == *pd ) return true ;
	}//for
	return false ;
}//Find()
/////////////////////////////////////////////////////
//定义一个栈
template < class T >
class Stack{
	T* Top ;
	T* Bottle ;
public:
	Stack() ;
	~Stack(){ delete[] Top ; delete[] Bottle ; }
	void PushElem( T& data ) ;
	void PopElem ( T& data ) ;
	bool Empty(){ return Top == Bottle ? true : false ; }
	bool Find( T& data ) ;
	T GetElem(){ return *( Top-1 ) ; }
	
} ;
template < class T >
Stack< T >::Stack()
{
	Top = Bottle = nem T[1000] ; 
}//Stack()
template < class T >
void Stack< T >::PushElem( T& data )
{
	*Top = data ;
	++Top ;
}
template < class T >
void Stack< T >::PopElem( T& data )
{
	data = *( --Top ) ;
}
template < class T >
bool Stack< T >::Find( T& data )
{
	T* pd ;
	for( pd = Top-1 ; pd != Bottle ; --pd ){
		if( data == *pd ) return true ;
	}//for
	return false ;
}



//有9个格就要有9个可能(虽然有的可能是有重复的..不过为了设计的方便..最好要定义9个)

struct Move
{
	int UP;
	int DOWN;
	int LEFT;
	int RIGHT;
//////////////////////////////////////////////////////////////////////////////////////////
//存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/
}move[9]={{0,1,0,1},{0,1,1,1},
{0,1,1,0},{1,1,0,1},
{1,1,1,1},{1,1,1,0},
{1,0,0,1},{1,0,1,1},{1,0,1,0}};
/////////////////////////////////////////////////////



bool IsTarget( closed& q );
int getpos( closed& q );
void Print(  Formation < closed >& ClosedList ) ;

bool moveup( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList ) ;
bool movedown( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList ) ;
bool moveleft( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList ) ;
bool moveright( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList ) ;

void main()
{   
	
	//定义两个队列open 和closed
	Formation < open > OpenList ;
	Formation < closed > ClosedList ;
    //初始化OpenList
	open start ;
	cout<<"\n\n\n八数码难题求解过程\n广度优先穷举解决\t\t\n";
	cout<< "请输入初始矩阵数码:" ;
	for( int k=0 ; k<9 ; ++k ) cin>> startspace.data[k] ;
	cout<< "请输入目标矩阵数码:" ;
	for( k=0 ; k<9 ; ++k ) cin>> aimspace.data[k] ;
	for( int i=0 ; i<9 ; ++i ) start.data[i] = startspace.data[i] ;
	start.fatherbh = -1 ;
	OpenList.PushElem( start ) ;
	//广度优先
	open otemp ;
	closed ctemp ;
	int ppos = 0 ;
	int number = 0 ;
	while( OpenList.Full() ){
		OpenList.PopElem( otemp ) ;
		ctemp.fatherBH = otemp.fatherbh  ;
		ctemp.pos      = ppos            ;
		for( int i=0 ; i<9 ; ++i ) ctemp.data[i] = otemp.data[i] ;
        ClosedList.PushElem( ctemp )  ;
		if( IsTarget( ClosedList.GetElem() ) ) break ; 

		if( move[ getpos( ctemp ) ].UP ){ 
			if( moveup( ctemp, OpenList, ClosedList ) ){
				otemp.fatherbh = ppos ;
				for( int i=0 ; i<9 ; ++i ) otemp.data[i] = ctemp.data[i] ;
				OpenList.PushElem( otemp ) ;
				
			}//if
		}//if
		ctemp = ClosedList.GetElem() ;

		if( move[ getpos( ctemp ) ].DOWN ){ 
			if( movedown( ctemp, OpenList, ClosedList ) ){
				otemp.fatherbh = ppos ;
				for( int i=0 ; i<9 ; ++i ) otemp.data[i] = ctemp.data[i] ;
				OpenList.PushElem( otemp ) ;
				
			}//if
		}//if
		ctemp = ClosedList.GetElem() ;

		if( move[ getpos( ctemp ) ].LEFT ){ 
			if( moveleft( ctemp, OpenList, ClosedList ) ){
				otemp.fatherbh = ppos ;
				for( int i=0 ; i<9 ; ++i ) otemp.data[i] = ctemp.data[i] ;
				OpenList.PushElem( otemp ) ;
				
			}//if
		}//if
		ctemp = ClosedList.GetElem() ;
        
		if( move[ getpos( ctemp ) ].RIGHT ){ 
			if( moveright( ctemp, OpenList, ClosedList ) ){
				otemp.fatherbh = ppos ;
				for( int i=0 ; i<9 ; ++i ) otemp.data[i] = ctemp.data[i] ;
				OpenList.PushElem( otemp ) ;
				
			}//if
		}//if
        ctemp = ClosedList.GetElem() ;
		++ppos ;
		number++ ;
		if( number>500 ) break ;
	}//while
	if(  number>500 ) cout<< "ERROR!" << endl ;
	else
	Print( ClosedList ) ;
	
    
}


//一个判断的函数要判断得越快越好..就是优先判断可能性大的..
bool IsTarget( closed& q )
{
	for( int i=0 ; i<9 ; ++i ){
		if( q.data[i] != aimspace.data[i] ) return false ;
	}//for
	return true ;
}// IsTarget()
/////////////////////////////////////////////////////////////////



int getpos( closed& q )
{
	for( int i=0; i<9; i++ )
	{
		if( q.data[i]!=0 )
			continue ;
		else
			break ;
	}
	return i ;
}//getpos()


//////////////////////////////////////////////////////////////////////////////////////////
//数组中的矩阵的空格上移
bool moveup( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList )
{
	int k ;
	int pos = getpos( q ) ;
	k = q.data[pos] ;
	q.data[pos] = q.data[pos-3] ;
	q.data[pos-3] = k ;

    open oq ;
	for( int i=0 ; i<9 ; ++i )oq.data[i] = q.data[i] ;
	oq.fatherbh = q.fatherBH ;

	if( OpenList.Find( oq ) || ClosedList.Find( q ) ) return false ;
    return true ;
}
//////////////////////////////////////////////////////////////////////////////////////////
//数组中的矩阵的空格下移
bool movedown( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList )
{
	int k ;
	int pos = getpos( q ) ;
	k = q.data[pos] ;
	q.data[pos] = q.data[pos+3] ;
	q.data[pos+3] = k ;

    open oq ;
	for( int i=0 ; i<9 ; ++i )oq.data[i] = q.data[i] ;
	oq.fatherbh = q.fatherBH ;

	if( OpenList.Find( oq ) || ClosedList.Find( q ) ) return false ;
    return true ;
}
//////////////////////////////////////////////////////////////////////////////////////////
//数组中的矩阵的空格左移
bool moveleft( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList )
{
	int k ;
	int pos = getpos( q ) ;
	k = q.data[pos] ;
	q.data[pos] = q.data[pos-1] ;
	q.data[pos-1] = k ;

	open oq ;
	for( int i=0 ; i<9 ; ++i )oq.data[i] = q.data[i] ;
	oq.fatherbh = q.fatherBH ;

	if( OpenList.Find( oq ) || ClosedList.Find( q ) ) return false ;
    return true ;
}
//////////////////////////////////////////////////////////////////////////////////////////
//数组中的矩阵的空格右移
bool moveright( closed& q, Formation < open >& OpenList, Formation < closed >& ClosedList )
{
	int k ;
	int pos = getpos( q ) ;
	k = q.data[pos] ;
	q.data[pos] = q.data[pos+1] ;
	q.data[pos+1] = k ;

    open oq ;
	for( int i=0 ; i<9 ; ++i )oq.data[i] = q.data[i] ;
	oq.fatherbh = q.fatherBH ;

	if( OpenList.Find( oq ) || ClosedList.Find( q ) ) return false ;
    return true ;
}
//////////////////////////////////////////////////////////

void Print(  Formation < closed >& ClosedList )
{
	closed ctemp , temp[30] ;
	int cn = 0 ; 
    ClosedList.PopFromBottle( temp[0] ) ;

	while( ClosedList.Full() ){
		
		ClosedList.PopFromBottle( ctemp ) ;
		if( ctemp.pos == temp[cn].fatherBH ){
			++cn ;
			temp[cn].fatherBH = ctemp.fatherBH ;
			temp[cn].pos      = ctemp.pos      ;
			for( int i=0 ; i<9 ; ++i ) 
				temp[cn].data[i] = ctemp.data[i] ;
			
		}//if
	}//while

	for( int i=cn ; i>=0 ; --i ) cout<< temp[i] ;

}