algorithm.cpp

绝对原创!用的是A*算法.解决8数码问题.绝对可用.初学者可以看看.

#include "Algorithm.h"

//#define FALSE false
//#define TRUE true

CQNode::CQNode()
{
}

CQNode::~CQNode()
{
}

CQNode::CQNode(int initData[],int targetData[])
{
	memcpy(m_nElemData,initData,sizeof(int)*ORDER*ORDER);
	for(int i=0;i<ORDER;i++)
		for(int j=0;j<ORDER;j++)
		{
			if(m_nElemData[i][j] == 0)
			{
				m_nSpace = i*ORDER + j;
				break;
			}
		}

	m_nFloor = 0;
	Caculate(targetData);	
	parant = NULL;
	next = NULL;
}

void CQNode::Print()
{
	for(int i=0;i<ORDER;i++)
	{
		for(int j=0;j<ORDER;j++)
		{
			printf("%d ",m_nElemData[i][j]);
		}
        printf("\n");
	}
	printf("\n");
}

void CQNode::Caculate(int targetData[])
{
   int count = 0;
   for(int i=0;i<ORDER;i++)
	   for(int j=0;j<ORDER;j++)
	   {
		   int m = i+j;
		   for(int k=0;k<ORDER;k++)
			   for(int t=0;t<ORDER;t++)
			   {
				   int z = k+t;
				   if(m_nElemData[k][t] == targetData[i*ORDER + j])
                            count += abs(m-z);
			   }
	   }
	m_value = count + m_nFloor;
}

BOOL CQNode::IsTarget(int targetData[])
{
	for(int i=0;i<ORDER;i++)
		for(int j=0;j<ORDER;j++)
		{
			if(m_nElemData[i][j] != targetData[i*ORDER+j]) //有一个不等就不是目标状态
				return FALSE;
		}
	return TRUE;
}

BOOL CQNode::GetNewChild(int i,CQNode* pNewNode)
{
	memcpy(pNewNode->m_nElemData,m_nElemData,sizeof(int)*ORDER*ORDER);

	//从最右边开始,沿逆时针生成各个孩子节点
	switch(i)
	{
	case 0://右边
		if(m_nSpace==2 || m_nSpace==5 || m_nSpace==8)//已经在最右边
			return FALSE;//没有孩子生成
		else
		{
			pNewNode->m_nSpace = m_nSpace+1;//空白格往右移一格
		}
		break;
    case 1: //上边
		if(m_nSpace==0 || m_nSpace==1 || m_nSpace==2)//已经在最上边
			return FALSE;//没有孩子生成
		else
		{
			pNewNode->m_nSpace = m_nSpace-3;
		}
		break;
	case 2://左边
		if(m_nSpace==0 || m_nSpace==3 || m_nSpace==6)//已经在最左边
			return FALSE;//没有孩子生成
		else
		{
			pNewNode->m_nSpace = m_nSpace-1;
		}
		break;
	case 3://下边
		if(m_nSpace==6 || m_nSpace==7 || m_nSpace==8)//已经在最下边
			return FALSE;//没有孩子生成
		else
		{
			pNewNode->m_nSpace = m_nSpace+3;
		}
		break;
	default:
		break;
	}
	
	//交换相应的位置
    int temp;
	temp = pNewNode->m_nElemData[m_nSpace/3][m_nSpace%3];
	pNewNode->m_nElemData[m_nSpace/3][m_nSpace%3] = 
		   pNewNode->m_nElemData[pNewNode->m_nSpace/3][pNewNode->m_nSpace%3];
	pNewNode->m_nElemData[pNewNode->m_nSpace/3][pNewNode->m_nSpace%3] = temp;
		
//	//建立父子关系
//	pNewNode->parant = this;
	pNewNode->m_nFloor = m_nFloor+1;//加深了一层
	pNewNode->next = NULL;

	return TRUE;
}

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

CLinkQueue::CLinkQueue()
{
}

CLinkQueue::~CLinkQueue()
{
}

void CLinkQueue::Init(int initData[],int targetData[])
{
	CQNode* pNewNode = new CQNode(initData,targetData);
	CQNode* pRootNode = new CQNode;
	pRootNode->m_nFloor = 0;
	pRootNode->m_value = 0;
	pRootNode->parant = NULL;

	head = pRootNode;
	head->next = pNewNode;
	
	front = head;
	rear = head->next;
	
}

BOOL CLinkQueue::IsEmpty()
{
	if(front == rear && front->next==NULL)
		return TRUE;
	else
		return FALSE;
}

CQNode* CLinkQueue::DeQueue()
{
//	//拷贝相应的值
	CQNode* p;
	p = front->next;
//	currentNode.m_nFloor = p->m_nFloor;
//	currentNode.m_nSpace = p->m_nSpace;
//	currentNode.m_value = p->m_value;
//	currentNode.parant = p->parant;
//	currentNode.next = p->next;
//	memcpy(currentNode.m_nElemData,p->m_nElemData,sizeof(int)*ORDER*ORDER);
    
	//更新队列
	front = front->next;

	return p;
}

void CLinkQueue::EnQueue(CQNode* pNewNode)
{
   //本质上是插入到Open表部分
	CQNode* p;
	p = front;

	if(IsEmpty()) //如果为空表
	{
        p->next = pNewNode;
		rear = pNewNode;
	}

    //如果在Open表首部
    if(p->next->m_value >= pNewNode->m_value) 
	{
          pNewNode->next = p->next;
		  p->next = pNewNode;
		  return;
	}
	else
	{
          p = p->next;
	}

	//在Open表中间
	while(p != rear) 
	{
	   if((p->next->m_value >= pNewNode->m_value) && (p->m_value < pNewNode->m_value)) //
	   {
          pNewNode->next = p->next;
		  p->next = pNewNode;
		  return;
	   }
	   else
	   {
          p = p->next;
	   }
	}
	
	//到了队列末尾,就插到末尾
	if(p == rear) 
	{
		if(p->m_value < pNewNode->m_value)
		{
			p->next = pNewNode;
			rear = pNewNode;
		}
	}

}

BOOL CLinkQueue::IsInClose(CQNode* pNode)
{
	CQNode* p;
	int i,j;
	p = head->next;
   while(p != front->next) 
	{
		for(i=0;i<ORDER;i++)
		{
			for(j=0;j<ORDER;j++)
			{
				if(p->m_nElemData[i][j] != pNode->m_nElemData[i][j])
					  break;
			}
			if(j<ORDER)break;
		}

		if(i==ORDER && j==ORDER)
			 return TRUE;

		p = p->next;
	}

	return FALSE;
}

BOOL CLinkQueue::IsInOpen(CQNode* pNode)
{
	CQNode* p;
	int i,j;
	p = front->next;
	while(p != rear->next)
	{
		for(i=0;i<ORDER;i++)
		{
			for(j=0;j<ORDER;j++)
			{
				if(p->m_nElemData[i][j] != pNode->m_nElemData[i][j])
					  break;
			}
			if(j<ORDER)break;
		}

		if(i==ORDER && j==ORDER)
			 return TRUE;

		p = p->next;
	}

	return FALSE;
}

void CLinkQueue::UpdateOpen(CQNode* pNewNode)
{
	CQNode* p;
	int i,j;
	p = front->next;
	while(p != rear->next)
	{
		for(i=0;i<ORDER;i++)
		{
			for(j=0;j<ORDER;j++)
			{
				if(p->m_nElemData[i][j] != pNewNode->m_nElemData[i][j])
					  break;
			}
			if(j<ORDER)break;
		}

		if(i==ORDER && j==ORDER)
			 break;
        else
		   p = p->next;
	}

	if(pNewNode->m_value < p->m_value)
	{
		p->m_value = pNewNode->m_value;
		p->parant = pNewNode->parant;
		p->m_nFloor = pNewNode->m_nFloor;
	}
    
}

void CLinkQueue::UpdateClose(CQNode* pNewNode)
{
	CQNode* p;
	CQNode* q;
	int i,j;
	p = head->next;
	q = head->next;
   while(p != front->next)
	{
		for(i=0;i<ORDER;i++)
		{
			for(j=0;j<ORDER;j++)
			{
				if(p->m_nElemData[i][j] != pNewNode->m_nElemData[i][j])
					  break;
			}
			if(j<ORDER)break;
		}

		if(i==ORDER && j==ORDER)
			 break;
        else
		{
	    	q = p;
		    p = p->next;
		}	
	}
   
	if(pNewNode->m_value < p->m_value)
	{
		//删除p
		q->next = p->next;
		delete p;
		EnQueue(pNewNode);//把pNewNode放回Open表
	}

}

CQNode* CLinkQueue::Output(CQNode* targetNode)
{
	CQNode* p;
	CQNode* q;

// 	targetNode->Print();
	
	p = targetNode->parant;
	q = targetNode;
	q->nextResult = NULL;
//	p->next = targetNode;
	while(p!=NULL) 
	{
		//p->Print();
		p->nextResult = q;
		q = p;
		p = p->parant;	
	}
 
	return q;

}

void CLinkQueue::Destroy()
{
	CQNode* p;
	CQNode* q;
	if(head != NULL)
	{
		p = head;
		while(p != rear)
		{
           q = p;
		   p = p->next;
		   if(q!=NULL)
		   {
			   delete q;  
		   }
		}
	}
}

BOOL ASearch(int initData[],int targetData[],CQNode** pResult,CLinkQueue& Q)
{
	Q.Init(initData,targetData);//初始化链表

	CQNode* pCurrentNode;

	while(!Q.IsEmpty()) //如果Q非空
	{
       pCurrentNode = Q.DeQueue();//出队,取出一个节点
       
	   if(pCurrentNode->IsTarget(targetData)) //如果是目标节点
	   {
		   if(pCurrentNode->parant != NULL)
		     *pResult = Q.Output(pCurrentNode); //输出结果
		   return TRUE;
	   }
	   else //如果不是
	   {
          for(int i=0;i<4;i++) //在棋格中,最多有4个孩子
		  {
               CQNode* pNewNode = new CQNode;
			   if(pCurrentNode->GetNewChild(i,pNewNode))//得到当前节点的第i个孩子
			   {
				  pNewNode->parant = pCurrentNode;//设置父子关系
				  pNewNode->Caculate(targetData);//计算估价值

			      if((!Q.IsInOpen(pNewNode)) && (!Q.IsInClose(pNewNode)))//如果队列中没有这个节点
				  {
				     Q.EnQueue(pNewNode);//则插入节点,返回
				  }
			      else if(Q.IsInOpen(pNewNode)) //如果在Open表中
				  {
                     Q.UpdateOpen(pNewNode); //更新Open表
				  }
			      else //如果在Close表中
				  {
				     Q.UpdateClose(pNewNode);//更新Close表
				  }
			   }
		  }
	   }
	}

	return FALSE;
}