启发式图搜索过程

EXPAND(n){ } ,计算f(n, ) = g(n, ) + h( ); g(n, )是从s通过n到 的耗散值，f(n, )是从s通过n、 到目标节点耗散值的估计；
·ADD( , OPEN),标记 到n的指针。
·IF f(n, )<f( ) THEN f( ) := f(n, ),标记 到n的指针；比较f(n, )和f( ),f( )是扩展n之前计算的耗散值。
//判断当前节点是否目标节点
bool uninlist(StateNode &sn,list<StateNode> &lsn);
//判断当前节点是不是在OPEN表或者CLOSED表中
void addtolist(StateNode &sn,list<StateNode> &lsn,list<StateNode> &lcsn);
{//根据当前扩展到的节点的类型（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++){}
{
cin>>node[i][j];
}
}
cout<<endl;
}
void putgoalnode()
{
cout<<"请输入初始状态！（空闲的格子用0表示）"<<endl;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
cin>>node[i][j];
}
}
cout<<endl;
{
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));
list<StateNode>::iterator iter;
for (iter=lsn.begin();iter!=lsn.end();iter++)
{
if (*iter==sn)
{
return false;
}
}
return true;
}
void addtolist(StateNode &sn,list<StateNode> &lsn,list<StateNode> &lcsn)
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++)
{
for (iterc=lcsn.begin();iterc!=lcsn.end();iterc++)
{
if (*iterc==sn){break;}
}
if(iterc->fs>sn.fs)
{
for (iter=lsn.begin();iter!=lsn.end() && sn.fs>=iter->fs;iter++){}
{//扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作
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)
{
{
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);
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;
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))
在下面解决八数码问题的程序中，采用h(n)=P(n), P(n)定义为每一个将牌与其目标位置之间的距离的总和。
三、算法实现
（1）数据结构
class StateNode{
public:
int gs,hs,fs;//分别表示算法中的g(n)、h(n)、f(n)
StateNode *psn;//一个指向扩展出它的父节点的指针
list<StateNode> CLOSED;
}
}
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]<<" ";
//根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式
void expandnode(StateNode &sn,StateNode &goal,list<StateNode> &lsn,list<StateNode> &lcsn);
//扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作
启发式图搜索过程
一、过程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);
list<StateNode> OPEN;//使用STL中的list类型来存放OPEN表
list<StateNode> CLOSED;//使用STL中的list类型来存放CLOSED表
（2）运行过程演示：
四、程序代码（C++）：
#include <iostream>
#include <list>
#include <math.h>
using namespace std;
#define MAXNUM 1000
class StateNode//这是一个节点类型的类，定义了与节点相关的信息及函数
{
public:
int gs,hs,fs;
StateNode *psn;
StateNode()
{
gs=0;hs=0;fs=gs+hs;
psn=0;
}
}
}
}
}
}
}
bool isgoal(StateNode &sn,StateNode &goal)//判断当前节点是否目标节点
{
return sn==goal;
}
bool uninlist(StateNode &sn,list<StateNode> &lsn)
{//判断当前节点是不是在OPEN表或者CLOSED表中
}
int getnode(int i,int j)//读取node[i][j]
{
return node[i][j];
}
void swap(int i,int j,int m,int n)//交换数组中指定位置的两个元素的数值
{
int temp;
temp=node[i][j];
node[i][j]=node[m][n];
//交换数组中指定位置的两个元素的数值
bool operator ==(StateNode &sn);
//重载了运算符==，方便后面进行比较
void operator =(StateNode &sn);
//重载了运算符=，方便后面对节点进行整体赋值
void printstatenode();
//将每个节点的内容按照一定格式输出
if (i>0)//向左移动
{
temsn=sn;
temsn.swap(i,j,i-1,j);
temsn.psn=&sn;
evaluandadd(temsn,sn,goal,lsn,lcsn);
}
if (i<2)//向右移动
{
temsn=sn;
temsn.swap(i,j,i+1,j);
temsn.psn=&sn;
StateNode();//构造函数，初始化节点
void putstartnode();//输入开始节点
void putgoalnode();//输入目标节点
int getnode(int i,int j);//读取node[i][j]
void swap(int i,int j,int m,int n);
·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*。
lsn.insert(iter,*lcsn.erase(iterc));
}
}
}
void evaluandadd(StateNode &temsn,StateNode &sn,StateNode &goal,list<StateNode> &lsn,list<StateNode> &lcsn)
{
temsn.gs=sn.gs+1;
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)
}
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++)
lsn.insert(iter,sn);
}
else if(!uninlist(sn,lsn))
{
for (iter=lsn.begin();iter!=lsn.end();iter++)
{
if (*iter==sn){break;}
}
if (iter->fs>sn.fs){*iter=sn;}
}
else if (!uninlist(sn,lcsn))
private:
int node[3][3];//八数码的每个节点用一个二维数组存储
};
void evaluatefunction(StateNode &sn,StateNode &goal);
//启发函数，计算某个节点的h(n)值
bool isgoal(StateNode &sn,StateNode &goal);
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;