jiug.cpp

这是一个关于A*算法的实现8数码的程序源代码

// JiuG.cpp: implementation of the CJiuG class.

#include "stdafx.h"
#include "A8.h"
#include "A8Dlg.h"
#include "JiuG.h"
#include "math.h"//计算估价函数是会用到abs()
#include "stdlib.h"
#include "searchpos.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CJiuG::CJiuG()
{
	//构造函数
}
CJiuG::~CJiuG()
{
   //析构函数
}
//左移,参数pre表示移动前的状态，result表示移动后的状态
BOOL CJiuG::MoveLeft(JGState *pre, JGState *result)
{
	int x, y, tempx, tempy;
	
	//寻找0的位置
	for (x=0; x<3; x++)
	{
		for (y=0; y<3; y++)
		{
			if (pre->state[x][y] == 0)
			{
				tempx = x;
				tempy = y;
			}
		}
	}
    if (tempy == 0)  // 0在左边界则不能左移
	   return FALSE;
	
	// 复制数组
    for (int i=0; i<3; i++)
	{
		for (int j=0; j<3; j++)
		{
			result->state[i][j] = pre->state[i][j];
		}
	}
	
	//互换0和左边的数字位置
	result->state[tempx][tempy] = pre->state[tempx][tempy-1];
	result->state[tempx][tempy-1] = 0;
	
	//结构内容赋值
	result->curdistance = pre->curdistance + 1;  // 到当前节点行进代价
	result->cost = result->curdistance + ComputeFn(result, &StateObj);
	result->prestate = pre;  // 父节点指针
	result->nextstate = NULL;  // 子节点
    return TRUE;
}
// 右移,参数pre表示移动前的状态，result表示移动后的状态
BOOL CJiuG::MoveRight(JGState *pre, JGState *result)
{
	int x, y, tempx, tempy;
	
	for (x=0; x<3; x++)
	{
		for (y=0; y<3; y++)
		{
			if (pre->state[x][y] == 0)
			{
				tempx = x;
				tempy = y;
			}
		}
	}
    
	if (tempy == 2)
	   return FALSE;
    
	for (int i=0; i<3; i++)
	{
		for (int j=0; j<3; j++)
		{
			result->state[i][j] = pre->state[i][j];
		}
	}
    result->state[tempx][tempy] = pre->state[tempx][tempy+1];
	result->state[tempx][tempy+1] = 0;
	result->curdistance = pre->curdistance + 1;
	result->cost = result->curdistance + ComputeFn(result, &StateObj);
	result->prestate = pre;
	result->nextstate = NULL;
    return TRUE;
}
// 上移,参数pre表示移动前的状态，result表示移动后的状态
BOOL CJiuG::MoveUp(JGState *pre,JGState *result)
{
	int x, y, tempx, tempy;
	
	// 寻找空格位置
	for (x=0; x<3; x++)
	{
		for (y=0; y<3; y++)
		{
			if (pre->state[x][y] == 0)
			{
				tempx = x;
				tempy = y;
			}
		}
	}
    
	if (tempx == 0)
		return FALSE;

    for (int i=0; i<3; i++)
	{
		for (int j=0; j<3; j++)
		{
			result->state[i][j] = pre->state[i][j];
		}
	}
	result->state[tempx][tempy] = pre->state[tempx-1][tempy];
	result->state[tempx-1][tempy] = 0;
	result->curdistance = pre->curdistance + 1;  // 深度加一
	result->cost = result->curdistance + ComputeFn(result, &StateObj);
	result->prestate = pre;  // 设置前趋节点
	result->nextstate = NULL;
    return TRUE;
}


// 下移,参数pre表示移动前的状态，result表示移动后的状态
BOOL CJiuG::MoveDown(JGState *pre, JGState *result)
{
	int x, y, tempx, tempy;
	
	for (x=0; x<3; x++)
	{
		for (y=0; y<3; y++)
		{
			if (pre->state[x][y] == 0)
			{
				tempx = x;
				tempy = y;
			}
		}
	}
    
	if(tempx == 2)
		return FALSE;
    
	for (int i=0; i<3; i++)
	{
		for (int j=0; j<3; j++)
		{
			result->state[i][j] = pre->state[i][j];
		}
	}
    result->state[tempx][tempy] = result->state[tempx+1][tempy];
	result->state[tempx+1][tempy] = 0;
	result->curdistance = pre->curdistance + 1;
	result->cost = result->curdistance + ComputeFn(result, &StateObj);
	result->prestate = pre;
	result->nextstate = NULL;
    return TRUE;
}
// 比较两个状态是否相等，输入的是指针(这个函数很简单)
BOOL CJiuG::Compare(JGState *src1, JGState *src2)
{
	for (int i=0; i<=2; i++)
	{
		for (int j=0; j<=2; j++)
		{
			if (src1->state[i][j] != src2->state[i][j])
				return FALSE;
		}
	}

    return TRUE;
}
// 计算估价函数，采用了错位数来计算
int CJiuG::ComputeFn(JGState *cur, JGState *dest)
{
	int xcur[9], ycur[9], xdest[9], ydest[9];//保存9个坐标
	int i, j;
	int result = 0;
	for (i=0; i<3; i++)
	{
		for (j=0; j<3; j++)
		{
			xcur[cur->state[i][j]] = i;
			ycur[cur->state[i][j]] = j;
			xdest[dest->state[i][j]] = i;
			ydest[dest->state[i][j]] = j;
		}
	}
	for (i=1; i<9; i++)
	{
		result = result + abs(xcur[i]-xdest[i]) + abs(ycur[i]-ydest[i]);
	}

	return result;
}
 // 执行搜索
BOOL CJiuG::Search(Csearchpos *plg)
{   
	OpenList.clear();      // 清空OPEN表
	CloseList.clear();     // 清空CLOSE表
	ResultList.clear();    // 清空结果状态表
	int i = 0;               // 循环要用到的循环变量
	int fun_return = 0;      // 中间函数返回值
	
	JGState *tempstate = new JGState;
	CopyJG(&StateInit, tempstate);  // 此时复制只复制了数组,其它的项需另赋值.
	tempstate->curdistance = 0;
	tempstate->cost = ComputeFn(tempstate, &StateObj);
	tempstate->prestate = NULL;
	tempstate->nextstate = NULL;
	pstart = tempstate;
    
	// 如果初始状态和末态相同，搜索成功退出
	if (Compare(&StateInit, &StateObj))
	{
		ResultList.push_back(*pstart);
		return TRUE;
	}
	
	// 将起始结点加入Open表中
	OpenList.push_front(pstart);
	JGState *MinCostNode = new JGState;
	
	// 搜索//OPEN表非空 

	while (!OpenList.empty())  // Open表为空,失败退出
	{   
		JGState *nowstate = new JGState;
		int nmin = 10000;  // 设置的最大估价值
			
		// 搜索Open表中估计值最小的节点
		list<JGState*>::iterator ite;
		 MinCostNode = *OpenList.begin();
		
		 // 找出代价最小的点
		for (ite=OpenList.begin(); ite!=OpenList.end(); ++ite)
		{
			  if (((*ite)->cost < MinCostNode->cost)
				 && ((*ite)->curdistance >= MinCostNode->curdistance))
			 MinCostNode = *ite;
		}
		
		// 将估价函数最小的节点从Open表删除，加入到Close表中
		for (ite=OpenList.begin(); ite!=OpenList.end(); ++ite)
		{   
			if(Compare(*ite, MinCostNode))
			{
				nowstate = *ite;
			    OpenList.erase(ite);  // 从Open表移除
			    break;
			}
		}
		CloseList.push_back(nowstate);  // 加入到Close表中

        // 左移
		JGState *leftstate = new JGState;
		if (MoveLeft(nowstate, leftstate))
		{
           fun_return = YesNoObjOpenClose(leftstate);
		   
		   if(fun_return == 1)
		   {
			   return TRUE;
		   }
		   else
		   {
			   if (fun_return == -1)
			   {
			     delete leftstate;
			   }
		   }
		}
		else 
		{
			delete leftstate;
		}
        
		// 右移
		JGState *rightstate = new JGState;
		if (MoveRight(nowstate, rightstate))
		{
		  fun_return = YesNoObjOpenClose(rightstate);
		   
		  if(fun_return == 1)
		   {
			   return TRUE;
		   }
		   else
		   {
			   if (fun_return == -1)
			   {
			     delete rightstate;
			   }
		   }

		}
		else 
		{
			delete rightstate;
		}
        
		// 上移
		JGState *upstate = new JGState;
		if (MoveUp(nowstate, upstate) == TRUE)
		{
		  fun_return = YesNoObjOpenClose(upstate);
		  
		  if(fun_return == 1)
		   {
			   return TRUE;
		   }
		   else
		   {
			   if (fun_return == -1)
			   {
			     delete upstate;
			   }
		   }

		}
		else 
		{
			delete upstate;
		}
		
		// 下移
		JGState *downstate = new JGState;
	    if (MoveDown(nowstate, downstate) == TRUE)
		{
		   fun_return = YesNoObjOpenClose(downstate);
		   
		   if (fun_return == 1)
		   {
			   return TRUE;
		   }
		   else
		   {
			   if (fun_return == -1)
			   {
			     delete downstate;
			   }
		   }

		}
		else 
		{
			delete downstate;
		}

        // 设置最大的搜索节点个数(计算限制)
		int maxnode = CloseList.size() + OpenList.size();
		
		// 搜索超过设置的最大节点数要中止搜索，返回FALSE
		if (maxnode > 1000)
		   return FALSE;
		
		int CloseListNodeSum = CloseList.size();
		int OpenListNodeSum = OpenList.size();
		
		// 进度条显示
		plg->ComputePos(maxnode, CloseListNodeSum, OpenListNodeSum);

	} // return while
   
	return FALSE;
} // END SEARCH

// 复制两种状态(包括内含数组的复制,以及其它的结构复制)
void CJiuG::CopyJG(JGState *src, JGState *dest)
{
	for (int i=0; i < 3; i++)
	{
		for (int j=0; j < 3; j++)
		{
			dest->state[i][j] = src->state[i][j];
		}
	}
	dest->curdistance = src->curdistance;
	dest->cost = src->cost;
	dest->prestate = src->prestate;
	dest->nextstate = src->nextstate;
}


// 计算逆序奇偶性，以判断有无解，基于我对九宫问题解是否可达的证明
// 返回0为偶，返回1为奇
int CJiuG::ComputeJO(JGState *jo)
{
	int result = 0;
	int i, j;
	int k = 0;
	int temp[8];
	
	// 除去0，将其余8个数依次加入到数组中
	for (i=0; i<3; i++)
	{
		for (j=0; j<3; j++)
		{
			if (jo->state[i][j] != 0)
			{
				temp[k] = jo->state[i][j];
				k++;
			}
		}
	}
	
	// 判断奇偶性
	for (i=0; i<7; i++)
	{
		for (j=i+1; j<8; j++)
		{
			if (temp[i] > temp[j])
				result++;
		}
	}
    result = result%2;
	return result;
}
/******************************************************************
*函数名:YesNoObjOpenClose()
*详细描述：判断给定点是否是目标点，不是则看是否在open表，在则退出；
*再看是否在close表，在则退出。openclose表均不在则加入open表。
*如果是目标点，则不断回溯路径将这些点加入路径链表。
*输入参数：当前节点curstate
*返回值：0：不在openclose表加入open表，1：是目标点,-1:在openclose表
*******************************************************************/
int CJiuG::YesNoObjOpenClose(JGState *curstate)
{
	if (Compare(curstate, &StateObj) == FALSE)
	{
	    // 不是目标节点，则看是否可以加入到Open表中
		int  i = 0;		
		bool inopen = false;
		bool inclose = false;
		
		// 检查是否在Open表中
		i = OpenList.size();
		if (i != 0)
		{
			list<JGState*>::iterator ite;
			for (ite=OpenList.begin(); ite!=OpenList.end(); ++ite)
			{
			   if (Compare(curstate,*ite) == TRUE)
				{
				 inopen = true;  // 在open表中则直接退出
				 break;
				}
			}  //end for
		}  //end if
		
		// 检查是否在Close表中
		i = CloseList.size();
		if(i != 0)
		{
			list<JGState*>::iterator ite;
			for (ite=CloseList.begin(); ite!=CloseList.end(); ++ite)
			{
			   if (Compare(curstate,*ite) == TRUE)
				{
				  inclose = true;  // 在close表中则直接退出
			      break;
			   }
			}  // end for
		}  // end else
		
		if ((inopen==false) && (inclose==false))  // open and close no lie all
		{
			OpenList.push_front(curstate);  // push into open list
		    return 0;
		}
		else 
		{
			return -1;
		}
	}  // end if compare( )
	else
	{
		// 找到目标结点
		ResultList.push_front(*curstate);
		
		//回溯，得到ResultList
		while (curstate != pstart)
		{
			ResultList.push_front( *curstate);
			curstate = curstate->prestate;
		}
		ResultList.push_front(*pstart);  // 再将起始点加入
		
		return 1;  // 成功返回
	}//end else

}