⑦OPEN中的节点按f值从小到大排列；
⑧GO LOOP。
二、最佳图搜索算法A*：
当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)<=h*(n)时，则把这个算法称为算法A*。
在下面解决八数码问题的程序中，采用h(n)=P(n), P(n)定义为每一个将牌与其目标位置之间的距离的总和。
三、算法实现
（1）数据结构
class StateNode{
public:
int gs,hs,fs; //分别表示算法中的g(n)、h(n)、f(n)
StateNode *psn; //一个指向扩展出它的父节点的指针
StateNode(); //构造函数，初始化节点
void putstartnode(); //输入开始节点
void putgoalnode(); //输入目标节点
int getnode(int i,int j); //读取node[i][j]
void swap(int i,int j,int m,int n);
//交换数组中指定位置的两个元素的数值bool operator ==(StateNode &sn);
//重载了运算符==，方便后面进行比较void operator =(StateNode &sn);
//重载了运算符=，方便后面对节点进行整体赋值void printstatenode();
//将每个节点的内容按照一定格式输出private:
int node[3][3]; //八数码的每个节点用一个二维数组存储};
void evaluatefunction(StateNode &sn,StateNode &goal);
//启发函数，计算某个节点的h(n)值
bool isgoal(StateNode &sn,StateNode &goal);
//判断当前节点是否目标节点
bool uninlist(StateNode &sn,list &lsn);
//判断当前节点是不是在OPEN表或者CLOSED表中void addtolist(StateNode &sn,list &lsn,list &lcsn);
//根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式void expandnode(StateNode &sn,StateNode &goal,list &lsn,list &lcsn);
//扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作list OPEN; //使用STL中的list类型来存放OPEN表list CLOSED; //使用STL中的list类型来存放CLOSED表
（2）运行过程演示：
四、程序代码（C++）：
#include
#include
#include
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;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
node[i][j]=0;
}
}
}
void putstartnode()
{
cout<<"请输入目标状态！（空闲的格子用0表示）"<for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
cin>>node[i][j];
}
}
cout<}
void putgoalnode()
{
cout<<"请输入初始状态！（空闲的格子用0表示）"<for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
cin>>node[i][j];
}
}
cout<}
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];
node[m][n]=temp;
}
bool operator ==(StateNode &sn) //重载了运算符==，方便后面进行比较{
