8digits.cpp

用A*算法求解八数码问题。A*算法又叫做最佳图搜索算法

/************************************************************************/
/*                                                                      */
/*				Solving Eight Digits Problem by A* algorithms			*/
/*																		*/
/*				LUO Pengkui (SS31:2003010655)  2006-1-5					*/
/*																		*/
/************************************************************************/

#include "8Digits.h"

//////////////////////////////////////////////////////////////////////////
///		CHECK WHETHER OR NOT THE TWO NODES ARE OF THE SAME
///
bool isEqual( StateList *st1, StateList *st2)
{
	int i,j;
	for (i=0;i<3;i++)
		for (j=0;j<3;j++)
			if ( st1->a[i][j] != st2->a[i][j]) return false;
	return true;
};

//////////////////////////////////////////////////////////////////////////
///		CHENCK WHETHER OR NOT THE NEW NODE IS EXPANDED REPEATELY
///
bool isLastState(StateList *st1,StateList *lt)
{
	if(lt==NULL) return false;
	if(lt->last==NULL) return false;
	return isEqual(st1,lt->last);
};

//////////////////////////////////////////////////////////////////////////
///		CHECK WHETHER OR NOT THE NODE IS IN THE LIST
///
StateList *inList(StateList *state, StateList *list)
{
	if (list == NULL) return NULL;
	if (isEqual(state, list)) return list;
	return inList(state, list->next);
};

//////////////////////////////////////////////////////////////////////////
///		DELETE A NODE FROM THE LINK LIST
///
StateList *del(StateList *state, StateList *list)
{
	if (list == NULL) return list;
	if (isEqual(state, list)) return list->next;
	list->next = del(state, list->next);
	return list;
};

//////////////////////////////////////////////////////////////////////////
///		INSERT THE NODE INTO THE OPEN TABLE
///
StateList *intoOpen(StateList *state, StateList *open)
{
	if(open==NULL)
	{
		state->next=NULL;
		return state;
	}
	else if (open->f > state->f)
	{
		state->next = open;
		return state;
	}
	else
	{
		open->next = intoOpen(state,open->next);	// recursively
		return open;
	}
};

//////////////////////////////////////////////////////////////////////////
///		INSERT THE NODE INTO THE CLOSED TABLE
///
StateList *intoClosed(StateList *state , StateList *closed)
{
	state->next = closed;
	return state;
};

//////////////////////////////////////////////////////////////////////////
///		CALCULATE THE VALUE OF H FUNCTION
///
int getHValue(StateList *state)
{
	int i,j;
	int p=0,q=0;
	for ( i=0;i<3;i++) for( j=0;j<3;j++)
		// compare with the destination so as to calculate the value of p()
		if (state->a[i][j] != desState.a[i][j]) 
		{
			q++;
			switch(state->a[i][j]) {
				case 1:	p += i+j; break;
				case 2:	p += i+abs(1-j); break;
				case 3: p += i+abs(2-j); break;
				case 4: p += abs(1-i)+abs(2-j); break;
				case 5: p += abs(2-i)+abs(2-j); break;
				case 6: p += abs(2-i)+abs(1-j); break;
				case 7: p += abs(2-i)+j; break;
				case 8: p += abs(1-i)+j;
			}
		}
	if (1==inn) return q;
	else if (2==inn) return p;
	else exit(0);
};

//////////////////////////////////////////////////////////////////////////
///		EXAMINE THE STATUS AFTER MOVING A DIGIT
///
StateList *move(StateList *state , int i, int j )
{
	int tmpRow,tmpCol;
	StateList *tmp=NULL;
	tmp = new StateList();
	for (int k=0;k<3;k++)
		for (int l=0;l<3;l++)
			tmp->a[k][l] = state->a[k][l];
	tmp->or=state->or;
	tmp->ol=state->ol;
	tmpRow=tmp->or;
	tmpCol=tmp->ol;
	tmp->a[tmpRow][tmpCol]=tmp->a[i][j];	// Move a(i,j) to the blank grid
	tmp->a[i][j]=0;
	tmp->or=i;							// new position of new blank grid
	tmp->ol=j;
//	genCount ++;
	return tmp;
};

//////////////////////////////////////////////////////////////////////////
///		INSERT ALL THE NODES EXPANDED BY THE CURRENT NODE INTO THE LINK LIST
///
StateList *expand(StateList *state)
{
	int i1,j1;
	int i2,j2;
	StateList *expandedState=NULL;
	StateList *newState=NULL;			// new state generated
	for (i1=-1;i1<2;i1++)
		for (j1=-1;j1<2;j1++)
		{
			if (i1==0 && j1==0) continue;
			if (i1!=0 && j1!=0) continue;
			i2=state->or+i1;
			j2=state->ol+j1;
			if (i2<0 || j2<0 || i2>2 || j2>2) continue;
			newState=move(state,i2,j2);		// call move() to generate new node
			if (isLastState(newState,state))
			{
				free(newState);
				continue;
			}
			newState->last=state;
			newState->g=state->g+1;	
			newState->f=newState->g+getHValue(newState); // f=g+h
			newState->next=expandedState;
			expandedState=newState;
		}
//	expandCount ++;
	return expandedState;
};

//////////////////////////////////////////////////////////////////////////
///		THE ESSENTIAL PROCEDURE OF THE A* ALGORITHMS
///
StateList *A(StateList *firstState)
{
	StateList *expandedState=NULL;
	StateList *first=NULL;
	StateList *temp=NULL;
	StateList *state=NULL;
	open=firstState;								// put initial state into the Open Table
	closed=NULL;
	while(open!=NULL)
	{
		first = open;								// the first element of the Open Table
		if (isEqual(first,&desState))				// If target, win. 
			return first;							// Otherwise put first into the Closed Table
		open = open->next;	
		closed = intoClosed(first, closed);
		expandedState = expand(first);				// Expand the FIRST node to get all its sub-nodes
		while (expandedState!=NULL)
		{
			temp = expandedState;
			expandedState = expandedState->next;
			if (state = inList(temp, open))
			{				
				if (temp->f < state->f)	
				{
					open = intoOpen(temp, del(state, open));
					free(state);
				}
				else free(temp);					//Discard the temp
			}
			else if (state = inList(temp, closed))
			{
				if (temp->f < state->f)	
				{
					closed = del(state, closed);
					open = intoOpen(temp, open);	// reinsert to the Open Table
//					expandCount --;
					free(state);
				}
				else free(temp);
			}
			else open = intoOpen(temp, open);		// default: put into OPEN directly
		}
	}
	return NULL;
};

//////////////////////////////////////////////////////////////////////////
///		PRINT THE RESULT PATH
///
void print(StateList *state)
{
	if (state == NULL) return;
	print(state->last); // print reversely & recursively
	int i, j;
	for (i = 0; i < 3; i++)
	{
		cout<<"| ";
		for (j = 0; j < 3; j++)	cout<<state->a[i][j]<<" ";
		cout<<"| "<<endl;
	}
	cout << "[g,f]=[" << state->g << "," << state->f << "]\n" << endl;
};

//////////////////////////////////////////////////////////////////////////
///		INITIALIZATION
///
StateList* init()
{
	expandCount = 0;
	genCount = 0;
	StateList *fs = new StateList();
	fs->a[0][0] = 2; fs->a[0][1] = 1; fs->a[0][2] = 6;
	fs->a[1][0] = 4; fs->a[1][1] = 0; fs->a[1][2] = 8;
	fs->a[2][0] = 7; fs->a[2][1] = 5; fs->a[2][2] = 3;			
	fs->or=1; fs->ol=1;
	fs->g=0; fs->f=getHValue(fs);
	fs->last=NULL; fs->next=NULL;
	return fs;
}

//////////////////////////////////////////////////////////////////////////
///		THE ENTRY OF THE PROGRAM
///
int main()
{
L1:	cout << "\n请选择一个H函数：\n 1.不在位的将牌数；\n"; 
	cout << " 2.每一个将牌与其目标位置距离的总和。\n>>" ;
	try{
		scanf("%d",&inn);
		if (1!=inn&&2!=inn) {
			getchar();
			goto L1;
		}
	}
	catch(exception e) {
		getchar();
		goto L1;
	}	

	StateList *firstState = init();
	
	// Start searching
	firstState=A(firstState);

	// print the result
	if(firstState!=NULL) print(firstState);
	else cout<<"No result"<<endl;
	inn = 0;
	cout << "Again(Y/N)?  >>";
	char ch; cin >> ch;
	if ('y'==ch||'Y'==ch) goto L1;
	
	return 0;
}

//////////////////////////////////////////////////////////////////////////