源代码：基于A*算法的八数码问题的实现（类的定义与实现）

转载请注明出处：http://hi.baidu.com/lvchengbin405/blog/item/e354fd1faaeb09c0a7866921.html

 

 

// 类的定义头文件EDCPP.h
#include <stdio.h>
#include <stdlib.h>
#ifndef _EDCPP_H
#define _EDCPP_H
struct State{
char value[3][3];
int blankx;     // blank position x
int blanky;     // blank position y
};
class EDCNode{
private:
int m_index;    // ID
State* m_state; // state
int m_g;        // g value
int m_h;        // h value
int m_x;        // x coordinate(for drawing)
int m_y;        // y coordinate(for drawing)
int m_parent;

public:
// 构造与析构函数
EDCNode();
EDCNode(EDCNode& node);
~EDCNode();
// 初始化Node
void InitEDCNode(int index, State* s);
void InitEDCNode(int index, State* s, int x, int y);
void InitEDCNode(int index, State* s, int g, int h, int x, int y);
// Set函数
void SetIndex(const int index);
void SetState(State* s);
void SetG(const int g);
void SetH(const int h);
void SetX(const int x);
void SetY(const int y);
void SetParent(int parentindex);

// Get函数
int GetIndex();
State* GetState();
int GetG();
int GetH();
int GetF();
int GetX();
int GetY();
int GetParent();
// 静态函数，由类调用
static bool MoveLeft(State* s);             // 左移，返回值false表示不可移
static bool MoveRight(State* s);            // 右移，返回值false表示不可移
static bool MoveUp(State* s);               // 上移，返回值false表示不可移
static bool MoveDown(State* s);             // 下移，返回值false表示不可移
static bool Compare(State* s1, State* s2); // 比较两种状态是否一样，返回值false表示不一样
};
#define MAXNUM 100
#define EDC_L 1
#define EDC_R 2
#define EDC_U 3
#define EDC_D 4
class EDC
{
private:
static int m_index;// 
EDCNode* m_start; // 起始节点
EDCNode* m_end;    // 目标节点
EDCNode m_openList[MAXNUM]; // Open表
EDCNode m_closeList[MAXNUM]; // Close表
int m_openNum;    // Open表节点个数
int m_closeNum;   // Close表节点个数
int m_gParas;    // 值为1时选择g(suc)=g(bes)+h(suc,bes)，为0时选择g(child)=g(parent)+1
int m_hParasDn; // h(scr,des)=aDn+bPn+cSn,Dn方法的系数a
int m_hParasPn; // h(scr,des)=aDn+bPn+cSn,Pn方法的系数b
int m_hParasSn; // h(scr,des)=aDn+bPn+cSn,Sn方法的系数c
public:
// 构造函数
EDC();                                    
// 构造函数2，具备起始节点和目标节点和代价树参数
EDC(EDCNode* start, EDCNode* end, int g, int hd, int hp, int hs); 
// 析构函数
~EDC();                                   

EDCNode* GetStart();
EDCNode* GetEnd();
int GetOpenNum();
int GetCloseNum();
EDCNode* GetNodeFromOpenList(int index);
EDCNode* GetNodeFromCloseList(int index);
void GetParas(int& gParas, int& hParasDn, int& hParasPn, int& hParasSn);
void InsertToOpenList(EDCNode* node); // 插入一个节点到Open表中，并构建堆
EDCNode* PopNodeFromOpenList();        // 取Open表首元素，并调整堆
int IsInOpenList(EDCNode* node);       // 判断该节点是否在Open表中
void UpdateOpenList(int index);        // 更新堆，使第一元素为最小元素
void InsertToCloseList(EDCNode* node); // 插入一个节点到Close表中,按照G值从小到大排序
int IsInCloseList(EDCNode* node);      // 判断该节点是否在Close表中
int GetNodeParentFromCloseList(int index); // 获取Close中下标为index的父节点在Close的位置。
EDCNode* ExpandNode(EDCNode* node, int direct);   // 扩展子节点
void SetParas(int g, int hd, int hp, int hs);     // 设置代价树参数
int CalculateG(EDCNode* node1, EDCNode* node2);   // 计算节点的G值,由m_gParas决定计算方式
int CalculateH(EDCNode* node1, EDCNode* node2);   // 计算节点1到节点2的H值，h(scr,des)=aDn+bPn+cSn
static int DnMethod(EDCNode* node1, EDCNode* node2);     // D(n)表示节点node1的格局与node2目标节点格局的不同牌数，包括空格
static int PnMethod(EDCNode* node1, EDCNode* node2);     // P(n)是指node1格局各将牌离“家”（node2）的最短路径之和，包括空格
static int SnMethod(EDCNode* node1, EDCNode* node2);     /* S(n)计算方法：依照顺时针方向来检查非中心位置的每个奖牌，
                                                      若其后紧跟的将牌与目标格局一致，该将牌得0分，否则得2分；
                                                      中间方格有将牌得1分，否则得0分。所有将牌得分之和即为S(n)。*/
void StartEDC();         // 启动EDC，为单步遍历做好准备
int EDCOnce();           // 遍历搜索树一次，返回值-1表示失败，0表示继续，1表示成功
bool EDCAll();           // 遍历直到结果出来，返回值ture表示成功，false表示失败
};

#endif;
*********************************************************************************************************************
// 类的实现EDCPP.cpp 文件
#include "EDCPP.h"
//-------------------------------------------------------------------------
//      EDCNode class
//------------------------------------------------------------------------- 
EDCNode::EDCNode()
{
m_index = -1;
m_state = new State();
m_g = 0;
m_h = 0;
m_x = 0;
m_y = 0;
m_parent = -1;
}
EDCNode::EDCNode(EDCNode &node)
{
m_index = node.m_index;
m_state = new State(*(node.m_state));
m_g = node.m_g;
m_h = node.m_h;
m_x = node.m_x;
m_y = node.m_y;
m_parent = node.m_parent;
}
EDCNode::~EDCNode()
{
m_index = -1;
if (!m_state)
   delete m_state;
m_state = NULL;
m_g = 0;
m_h = 0;
m_x = 0;
m_y = 0;
}
void EDCNode::InitEDCNode(int index, State* s)
{
m_index = index;
*m_state = *s;
}
void EDCNode::InitEDCNode(int index, State* s, int x, int y)
{
m_index = index;
*m_state = *s;
m_x = x;
m_y = y;
}
void EDCNode::InitEDCNode(int index, State* s, int g, int h, int x, int y)
{
m_index = index;
*m_state = *s;
m_g = g;
m_h = h;
m_x = x;
m_y = y;
}
void EDCNode::SetIndex(const int index)
{
m_index = index;
}
void EDCNode::SetState(State* s)
{
m_state = s;
}
void EDCNode::SetG(const int g)
{
m_g = g;
}
void EDCNode::SetH(const int h)
{
m_h = h;
}
void EDCNode::SetX(const int x)
{
m_x = x;
}
void EDCNode::SetY(const int y)
{
m_y = y;
}
void EDCNode::SetParent(int parentindex)
{
m_parent = parentindex;
}
int EDCNode::GetIndex()
{
return m_index;
}
State* EDCNode::GetState()
{
return m_state;
}
int EDCNode::GetG()
{
return m_g;
}
int EDCNode::GetH()
{
return m_h;
}
int EDCNode::GetF()
{
return m_g + m_h;
}
int EDCNode::GetX()
{
return m_x;
}
int EDCNode::GetY()
{
return m_y;
}
int EDCNode::GetParent()
{
return m_parent;
}
bool EDCNode::MoveLeft(State* s)
{
if (s->blanky==0) 
   return false;
s->value[s->blankx][s->blanky] = s->value[s->blankx][s->blanky-1];
s->blanky--;
s->value[s->blankx][s->blanky] = '0';
return true;
}
bool EDCNode::MoveRight(State* s)
{
if (s->blanky==2) 
   return false;
s->value[s->blankx][s->blanky] = s->value[s->blankx][s->blanky+1];
s->blanky++;
s->value[s->blankx][s->blanky] = '0';
return true;
}
bool EDCNode::MoveUp(State* s)
{
if (s->blankx==0) 
   return false;
s->value[s->blankx][s->blanky] = s->value[s->blankx-1][s->blanky];
s->blankx--;
s->value[s->blankx][s->blanky] = '0';
return true;
}
bool EDCNode::MoveDown(State* s)
{
if (s->blankx==2) 
   return false;
s->value[s->blankx][s->blanky] = s->value[s->blankx+1][s->blanky];
s->blankx++;
s->value[s->blankx][s->blanky] = '0';
return true;
}
bool EDCNode::Compare(State* s1, State* s2)
{
for (int i=0; i<3; i++)
   for (int j=0; j<3; j++)
   {
    if (s1->value[i][j] != s2->value[i][j])
     return false;
   }
return true;
}
//-------------------------------------------------------------------------
//      EDC class
//------------------------------------------------------------------------- 
int EDC::m_index = 0;
EDC::EDC()
{
m_start = new EDCNode();
m_end = new EDCNode();
m_openNum = 0;
m_closeNum = 0;
m_gParas = 0;
m_hParasDn = 1;
m_hParasPn = 0;
m_hParasSn = 0;
}
EDC::EDC(EDCNode* start, EDCNode* end, int g=0, int hd=1, int hp=0, int hs=0)
{
m_start = new EDCNode(*start);
m_end = new EDCNode(*end);
m_openNum = 0;
m_closeNum = 0;
m_gParas = g;
m_hParasDn = hd;
m_hParasPn = hp;
m_hParasSn = hs;
}
EDC::~EDC()
{
if (m_start)
   delete m_start;
if (m_end)
   delete m_end;
m_start = NULL;
m_end = NULL;
m_openNum = 0;
m_closeNum = 0;
m_gParas = 0;
m_hParasDn = 1;
m_hParasPn = 0;
m_hParasSn = 0;
}
EDCNode* EDC::GetStart()
{
return m_start;
}
EDCNode* EDC::GetEnd()
{
return m_end;
}
int EDC::GetOpenNum()
{
return m_openNum;
}
int EDC::GetCloseNum()
{
return m_closeNum;
}
EDCNode* EDC::GetNodeFromOpenList(int index)
{
if (index<1 || index>m_openNum)
   return NULL;
return &m_openList[index];
}
EDCNode* EDC::GetNodeFromCloseList(int index)
{
if (index<1 || index>m_closeNum)
   return NULL;
return &m_closeList[index];
}
void EDC::GetParas(int &gParas, int &hParasDn, int &hParasPn, int &hParasSn)
{
gParas = m_gParas;
hParasDn = m_hParasDn;
hParasPn = m_hParasPn;
hParasSn = m_hParasSn;
}
void EDC::InsertToOpenList(EDCNode* node)
{
m_openList[++m_openNum] = *node;
UpdateOpenList(m_openNum);
}
EDCNode* EDC::PopNodeFromOpenList()
{
if (m_openNum<1)
   return NULL;
// 获取首元素
EDCNode* node = new EDCNode(m_openList[1]);
// 调整堆
m_openList[1] = m_openList[m_openNum--];
int u,v=1;
EDCNode temp;
do
{
   u = v;
   if (u*2+1<=m_openNum)
   {
    if (m_openList[u].GetF()>=m_openList[u*2].GetF())
     v = u*2;
    if (m_openList[v].GetF()>=m_openList[u*2+1].GetF())
     v = u*2+1;
   }
   else if (u*2<=m_openNum)
   {
    if (m_openList[u].GetF()>=m_openList[u*2].GetF())
     v = u*2;
   }
   if (u==v)
    break;
   else
   {
    temp = m_openList[u];
    m_openList[u] = m_openList[v];
    m_openList[v] = temp;
   }
}while (true);
return node;
}
int EDC::IsInOpenList(EDCNode* node)
{
for (int i=0; i<m_openNum; i++)
{
   if (EDCNode::Compare(node->GetState(), m_openList[i].GetState()))
    return i;
}
return -1;
}
void EDC::UpdateOpenList(int index)
{
if (index<1 || index>m_openNum)
   return;
EDCNode temp;
int i = index;
while (i!=1)
{
   if (m_openList[i].GetF() <= m_openList[i/2].GetF())
   {
    temp = m_openList[i/2];
    m_openList[i/2] = m_openList[i];
    m_openList[i] = temp;
    i = i/2;
   }
   else
    break;
}
}
void EDC::InsertToCloseList(EDCNode* node)
{
//m_closeList[++m_closeNum] = *node;
int i;
for (i=m_closeNum; i>0; i--)
{
   if (m_closeList[i].GetG() > node->GetG())
   {
    m_closeList[i+1] = m_closeList[i];
   }
   else
   {
    break;
   }
}
m_closeList[i+1] = *node;
m_closeNum++;
}
int EDC::IsInCloseList(EDCNode* node)
{
for (int i=0; i<m_closeNum; i++)
{
   if (EDCNode::Compare(node->GetState(), m_closeList[i].GetState()))
    return i;
}
return -1;
}
int EDC::GetNodeParentFromCloseList(int index)
{
if (index>m_closeNum)
   return -1;
for (int i=0; i<index; i++)
{
   if (m_closeList[index].GetParent() == m_closeList[i].GetIndex())
    return i;
}
return -1;
}
EDCNode* EDC::ExpandNode(EDCNode* node, int direct)
{
EDCNode* child = new EDCNode(*node);
bool result = false;
switch (direct)
{
case EDC_L:
   if (EDCNode::MoveLeft(child->GetState()))
    result = true;
   break;
case EDC_R:
   if (EDCNode::MoveRight(child->GetState()))
    result = true;
   break;
case EDC_U:
   if (EDCNode::MoveUp(child->GetState()))
    result = true;
   break;
case EDC_D:
   if (EDCNode::MoveDown(child->GetState()))
    result = true;
   break;
default:
   result = false;
}
if (result)
{
   child->SetIndex(++EDC::m_index);
   return child;
}
delete child;
return NULL;
}
void EDC::SetParas(int g, int hd, int hp, int hs)
{
m_gParas = g;
m_hParasDn = hd;
m_hParasPn = hp;
m_hParasSn = hs;
}
int EDC::CalculateG(EDCNode* node1, EDCNode* node2)
{
int res;
if (m_gParas==1)
   res = node1->GetG() + CalculateH(node1, node2);
else if (m_gParas==0)
   res = node1->GetG() + 1;
else
   res = 0;
return res;
}
int EDC::CalculateH(EDCNode* node1, EDCNode* node2)
{
int res = 0;
if (m_hParasDn != 0)
   res += m_hParasDn*DnMethod(node1, node2);
if (m_hParasPn != 0)
   res += m_hParasPn*PnMethod(node1, node2);
if (m_hParasSn != 0)
   res += m_hParasSn*SnMethod(node1, node2);
return res;
}
int EDC::DnMethod(EDCNode *node1, EDCNode *node2)
{
State *s1 = node1->GetState();
State *s2 = node2->GetState();
int i,j, Dn=0;
for (i=0; i<3; i++)
{
   for (j=0; j<3; j++)
   {
    if (s1->value[i][j] != s2->value[i][j])
     Dn++;
   }
}
return Dn;
}
int EDC::PnMethod(EDCNode *node1, EDCNode *node2)
{
State *s1 = node1->GetState();
State *s2 = node2->GetState();
int xcur[9], ycur[9], xdes[9], ydes[9];
int i,j, Pn=0;
for (i=0; i<3; i++)
{
   for (j=0; j<3; j++)
   {
    xcur[s1->value[i][j] - '0'] = i;
    ycur[s1->value[i][j] - '0'] = j;
    xdes[s2->value[i][j] - '0'] = i;
    ydes[s2->value[i][j] - '0'] = j;
   }
}
for (i=0; i<9; i++)
{
   Pn += abs(xdes[i]-xcur[i]) + abs(ydes[i]-ycur[i]);
}
return Pn;
}
int EDC::SnMethod(EDCNode *node1, EDCNode *node2)
{
State *s1 = node1->GetState();
State *s2 = node2->GetState();
int i, k, Sn=0;
int dirX[9];
int dirY[9];
if (s2->blankx==0)
{
   if (s2->blanky==0)
   {
    dirX[0]=0;dirX[1]=0;dirX[2]=1;dirX[3]=2; dirX[4]=2;dirX[5]=2;dirX[6]=1;dirX[7]=1;dirX[8]=0;
    dirY[0]=1;dirY[1]=2;dirY[2]=2;dirY[3]=2; dirY[4]=1;dirY[5]=0;dirY[6]=0;dirY[7]=1;dirY[8]=1;
   }
   else if (s2->blanky==1)
   {
    dirX[0]=0;dirX[1]=1;dirX[2]=2;dirX[3]=2; dirX[4]=2;dirX[5]=1;dirX[6]=0;dirX[7]=1;dirX[8]=0;
    dirY[0]=2;dirY[1]=2;dirY[2]=2;dirY[3]=1; dirY[4]=0;dirY[5]=0;dirY[6]=0;dirY[7]=1;dirY[8]=2;
   }
   else // blanky=2
   {
    dirX[0]=1;dirX[1]=2;dirX[2]=2;dirX[3]=2; dirX[4]=1;dirX[5]=0;dirX[6]=0;dirX[7]=1;dirX[8]=1;
    dirY[0]=2;dirY[1]=2;dirY[2]=1;dirY[3]=0; dirY[4]=0;dirY[5]=0;dirY[6]=1;dirY[7]=1;dirY[8]=2;
   }
}
else if (s2->blankx==1)
{
   if (s2->blanky==0)
   {
    dirX[0]=0;dirX[1]=0;dirX[2]=0;dirX[3]=1; dirX[4]=2;dirX[5]=2;dirX[6]=2;dirX[7]=1;dirX[8]=0;
    dirY[0]=0;dirY[1]=1;dirY[2]=2;dirY[3]=2; dirY[4]=2;dirY[5]=1;dirY[6]=0;dirY[7]=1;dirY[8]=0;
   }
   else if (s2->blanky==1)
   {
    dirX[0]=0;dirX[1]=0;dirX[2]=0;dirX[3]=1; dirX[4]=2;dirX[5]=2;dirX[6]=2;dirX[7]=1;dirX[8]=0;
    dirY[0]=0;dirY[1]=1;dirY[2]=2;dirY[3]=2; dirY[4]=2;dirY[5]=1;dirY[6]=0;dirY[7]=0;dirY[8]=0;
   }
   else // blanky=2
   {
    dirX[0]=2;dirX[1]=2;dirX[2]=2;dirX[3]=1; dirX[4]=0;dirX[5]=0;dirX[6]=0;dirX[7]=1;dirX[8]=2;
    dirY[0]=2;dirY[1]=1;dirY[2]=0;dirY[3]=0; dirY[4]=0;dirY[5]=1;dirY[6]=2;dirY[7]=1;dirY[8]=2;
   }
}
else // blankx=2
{
   if (s2->blanky==0)
   {
    dirX[0]=1;dirX[1]=0;dirX[2]=0;dirX[3]=0; dirX[4]=1;dirX[5]=2;dirX[6]=2;dirX[7]=1;dirX[8]=1;
    dirY[0]=0;dirY[1]=0;dirY[2]=1;dirY[3]=2; dirY[4]=2;dirY[5]=2;dirY[6]=1;dirY[7]=1;dirY[8]=0;
   }
   else if (s2->blanky==1)
   {
    dirX[0]=2;dirX[1]=1;dirX[2]=0;dirX[3]=0; dirX[4]=0;dirX[5]=1;dirX[6]=2;dirX[7]=1;dirX[8]=2;
    dirY[0]=0;dirY[1]=0;dirY[2]=0;dirY[3]=1; dirY[4]=2;dirY[5]=2;dirY[6]=2;dirY[7]=1;dirY[8]=0;
   }
   else // blanky=2
   {
    dirX[0]=2;dirX[1]=2;dirX[2]=1;dirX[3]=0; dirX[4]=0;dirX[5]=0;dirX[6]=1;dirX[7]=1;dirX[8]=2;
    dirY[0]=1;dirY[1]=0;dirY[2]=0;dirY[3]=0; dirY[4]=1;dirY[5]=2;dirY[6]=2;dirY[7]=1;dirY[8]=1;
   }
}
for (k=0; k<8; k++)
{
   for (i=0; i<8; i++)
   {
    if (s1->value[dirX[k]][dirY[k]] == s2->value[dirX[i]][dirY[i]])    
    {
     if (s1->value[dirX[k+1]][dirY[k+1]] != s2->value[dirX[i+1]][dirY[i+1]])
     {
      Sn += 2;
      break;
     }
     break;
    }
   }
}
if (s1->blankx!=s2->blankx || s1->blanky!=s2->blanky)
   Sn += 1;
return Sn;
}
int EDC::EDCOnce()
{
// 选取open表中未设置过的具有最小f值的节点bestnode
EDCNode* bestnode = PopNodeFromOpenList();
if (!bestnode)
   return -1;    // open表为空，返回-1，失败
// 放入close表
InsertToCloseList(bestnode);
// 判断bestnode是否是目标节点,如果是返回1,成功
if (EDCNode::Compare(bestnode->GetState(), m_end->GetState()))
   return 1;
// 扩展bestnode,从4个移动方向产生其后续节点successor
int i=EDC_L;
int old = -1;
EDCNode* successor;
while(i<=EDC_D)
{
   successor = ExpandNode(bestnode, i);
   i++;
   if (!successor)
    continue;
   // 建立从successor返回bestnode的指针
   successor->SetParent(bestnode->GetIndex());
   /*// 计算个g(suc)=g(bes)+h(bes,suc)
   successor->SetG(CalculateG(bestnode, successor));*/
   // 计算个g(suc)=g(bes)+1,深度加1
   successor->SetG(CalculateG(bestnode, successor));
   // suc是否在openlist中,如果在则返回位置
   old = IsInOpenList(successor);
   if (old!=-1)
   {
    // 判断g(suc)<g(old)
    if (successor->GetG()<m_openList[old].GetG())
    {
     // 重新确定old的父辈节点为bestnode,并修正父辈节点的g值
     m_openList[old].SetParent(bestnode->GetIndex());
     m_openList[old].SetG(successor->GetG());
    }
   }
   else    // 不在openlist中
   {
    // 如果不在closelist表中
    if (IsInCloseList(successor)==-1)
    {
     // 计算H值
     successor->SetH(CalculateH(successor, m_end));
     InsertToOpenList(successor); // 放入openlist中
    }
   }
   delete successor;
}
delete bestnode;
return 0;   // 继续
}
bool EDC::EDCAll()
{
InsertToOpenList(m_start);
int result=0;
while (result==0)
{
   result = EDCOnce();
}
if (result==-1)
   return false;
return true;
}
void EDC::StartEDC()
{
m_openNum = 0;
m_closeNum = 0;
m_index = 0;
InsertToOpenList(m_start);
}