}
}
}
}
}
}
}
bool isgoal(StateNode &sn,StateNode &goal)//判断当前节点是否目标节点
{
return sn==goal;
}
bool uninlist(StateNode &sn,list<StateNode> &lsn)
{//判断当前节点是不是在OPEN表或者CLOSED表中
//根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式
void expandnode(StateNode &sn,StateNode &goal,list<StateNode> &lsn,list<StateNode> &lcsn);
//扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作
}
cout<<"\n";
}
}
protected:
private:
int node[3][3];
};
void evaluatefunction(StateNode &sn,StateNode &goal)//启发函数，计算某个节点的h(n)值
{
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
//判断当前节点是否目标节点
bool uninlist(StateNode &sn,list<StateNode> &lsn);
//判断当前节点是不是在OPEN表或者CLOSED表中
void addtolist(StateNode &sn,list<StateNode> &lsn,list<StateNode> &lcsn);
}
}
this->gs=sn.gs;
this->hs=sn.hs;
this->fs=sn.fs;
this->psn=sn.psn;
}
void printstatenode()//将每个节点的内容按照一定格式输出
{
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
cout<<node[i][j]<<" ";
private:
int node[3][3];//八数码的每个节点用一个二维数组存储
};
void evaluatefunction(StateNode &sn,StateNode &goal);
//启发函数，计算某个节点的h(n)值
bool isgoal(StateNode &sn,StateNode &goal);
{//扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作
StateNode temsn;
list<StateNode>::iterator iter;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
if (sn.getnode(i,j)==0)
{
//交换数组中指定位置的两个元素的数值
bool operator ==(StateNode &sn);
//重载了运算符==，方便后面进行比较
void operator =(StateNode &sn);
//重载了运算符=，方便后面对节点进行整体赋值
void printstatenode();
//将每个节点的内容按照一定格式输出
启发式图搜索过程
一、过程A描述：
OPEN := (s), f(s) := g(s) + h(s);
LOOP : IF OPEN=() THEN EXIT(FAIL);
n := FIRST(OPEN);
IF GOAL(n) THEN EXIT(SUCCESS);
REMOVE(n, OPEN) , ADD(n, CLOSED);
temsn.hs=0;
evaluatefunction(temsn,goal);
temsn.fs=temsn.gs+temsn.hs;
addtolist(temsn,lsn,lcsn);
}
void expandnode(StateNode &sn,StateNode &goal,list<StateNode> &lsn,list<StateNode> &lcsn)
lsn.insert(iter,*lcsn.erase(uandadd(StateNode &temsn,StateNode &sn,StateNode &goal,list<StateNode> &lsn,list<StateNode> &lcsn)
{
temsn.gs=sn.gs+1;
{//根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式
list<StateNode>::iterator iter;
list<StateNode>::iterator iterc;
if (uninlist(sn,lsn) && uninlist(sn,lcsn))
{
for (iter=lsn.begin();iter!=lsn.end() && sn.fs>=iter->fs;iter++){}
{
n++;
}
}
}
if (n<9)
{
return false;
}
else return true;
}
void operator =(StateNode &sn)//重载了运算符=，方便后面对节点进行整体赋值
{
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
node[i][j]=sn.getnode(i,j);
·IF f(n, )<f( ) THEN f( ) := f(n, ),标记 到n的指针，ADD( ,OPEN);当f(n, )<f( )时，把 重放回OPEN中，不必考虑修改到其子节点的指针。
OPEN中的节点按f值从小到大排列；
GO LOOP。
二、最佳图搜索算法A*：
当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)<=h*(n)时，则把这个算法称为算法A*。
evaluandadd(temsn,sn,goal,lsn,lcsn);
}
if (j>0)//向上移动
{
temsn=sn;
temsn.swap(i,j,i,j-1);
temsn.psn=&sn;
evaluandadd(temsn,sn,goal,lsn,lcsn);
}
if (j<2)//向下移动
{
temsn=sn;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
node[i][j]=0;
}
}
}
void putstartnode()
{
cout<<"请输入目标状态！（空闲的格子用0表示）"<<endl;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
node[m][n]=temp;
}
bool operator ==(StateNode &sn)//重载了运算符==，方便后面进行比较
{
int n=0;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
if (node[i][j]==sn.getnode(i,j))
{
if (sn.getnode(i,j)!=goal.getnode(i,j) && sn.getnode(i,j)!=0)
{
for (int m=0;m<3;m++)
{
for (int n=0;n<3;n++)
{
if (sn.getnode(i,j)==goal.getnode(m,n))
{
sn.hs+=(abs(i-m)+abs(j-n));
temsn.swap(i,j,i,j+1);
temsn.psn=&sn;
evaluandadd(temsn,sn,goal,lsn,lcsn);
}
}
}
}
}
int main()
{
StateNode Start,SN[MAXNUM],Goal;
int i,j=0;
list<StateNode> OPEN;