启
发
式
图
搜
索
过
程
姓名：
学号：
启发式图搜索过程
一、过程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);
⑥ EXPAND(n) {mi} , 计算f(n, mi) = g(n, mi) + h(mi); g(n, mi)是从s通过n到mi的耗散值，f(n, mi)是从s通过n、mi到目标节点耗散值的估计；
·ADD(mj , OPEN), 标记mi到n的指针。
·IF f(n, mk)
·IF f(n, ml)
⑧ GO LOOP。
二、最佳图搜索算法A*：
当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)
在下面解决八数码问题的程序中，采用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
{ for (int j=0;j>node[i][j]; } } cout>node[i][j]; } } cout
for (int i=0;i
{
for (int j=0;j
{
if (node[i][j]==sn.getnode(i,j))
{
n++;
}
}
}
if (n
{
return false;
}
else return true;
}
void operator =(StateNode &sn)
{
for (int i=0;i
{
for (int j=0;j
{
node[i][j]=sn.getnode(i,j);
}
}
this->gs=sn.gs;
this->hs=sn.hs;
this->fs=sn.fs;
this->psn=sn.psn;
}
void printstatenode()
{
for (int i=0;i
{
for (int j=0;j
{
cout
}
cout
}
}
protected:
private: //重载了运算符=，方便后面对节点进行整体赋值 //将每个节点的内容按照一定格式输出
};
void evaluatefunction(StateNode &sn,StateNode &goal) //启发函数，计算某个节点的h(n)值 {
for (int i=0;i
{
for (int j=0;j
{
if (sn.getnode(i,j)!=goal.getnode(i,j) && sn.getnode(i,j)!=0)
{
for (int m=0;m
{
for (int n=0;n
{
if (sn.getnode(i,j)==goal.getnode(m,n))
{
sn.hs+=(abs(i-m)+abs(j-n));
}
}
}
}
}
}
}
bool isgoal(StateNode &sn,StateNode &goal) //判断当前节点是否目标节点 {
return sn==goal;
}
bool uninlist(StateNode &sn,list &lsn)
{
}
//判断当前节点是不是在OPEN表或者CLOSED表中 list::iterator iter; for (iter=lsn.begin();iter!=lsn.end();iter++) { if (*iter==sn) { return false; } } return true;
void addtolist(StateNode &sn,list &lsn,list &lcsn)
{ //根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式 list::iterator iter;
list::iterator iterc;
if (uninlist(sn,lsn) && uninlist(sn,lcsn))
{
for (iter=lsn.begin();iter!=lsn.end() && sn.fs>=iter->fs;iter++){}
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))
{
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++){}
lsn.insert(iter,*lcsn.erase(iterc));
}
}
}
void evaluandadd(StateNode &temsn,StateNode &sn,StateNode &goal,list &lsn,list &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 &lsn,list &lcsn)
{ //扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作 StateNode temsn;
list::iterator iter; for (int i=0;i0) //向左移动 { temsn=sn; temsn.swap(i,j,i-1,j); temsn.psn=&sn; evaluandadd(temsn,sn,goal,lsn,lcsn); }
if (i
temsn=sn;
temsn.swap(i,j,i+1,j);
temsn.psn=&sn;
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
temsn=sn;
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 OPEN; list CLOSED; list::iterator iter; list::iterator iterc; Goal.putgoalnode(); Start.putstartnode(); evaluatefunction(Start,Goal); Start.gs=0; Start.fs=Start.gs+Start.hs; OPEN.push_back(Start); for (iter=OPEN.begin(),i=0;iter!=OPEN.end() && ipsn,j++) { coutprintstatenode(); coutMAXNUM) { cout
启
发
式
图
搜
索
过
程
姓名：
学号：
启发式图搜索过程
一、过程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);
⑥ EXPAND(n) {mi} , 计算f(n, mi) = g(n, mi) + h(mi); g(n, mi)是从s通过n到mi的耗散值，f(n, mi)是从s通过n、mi到目标节点耗散值的估计；
·ADD(mj , OPEN), 标记mi到n的指针。
·IF f(n, mk)
·IF f(n, ml)
⑧ GO LOOP。
二、最佳图搜索算法A*：
当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)
在下面解决八数码问题的程序中，采用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
{ for (int j=0;j>node[i][j]; } } cout>node[i][j]; } } cout
for (int i=0;i
{
for (int j=0;j
{
if (node[i][j]==sn.getnode(i,j))
{
n++;
}
}
}
if (n
{
return false;
}
else return true;
}
void operator =(StateNode &sn)
{
for (int i=0;i
{
for (int j=0;j
{
node[i][j]=sn.getnode(i,j);
}
}
this->gs=sn.gs;
this->hs=sn.hs;
this->fs=sn.fs;
this->psn=sn.psn;
}
void printstatenode()
{
for (int i=0;i
{
for (int j=0;j
{
cout
}
cout
}
}
protected:
private: //重载了运算符=，方便后面对节点进行整体赋值 //将每个节点的内容按照一定格式输出
};
void evaluatefunction(StateNode &sn,StateNode &goal) //启发函数，计算某个节点的h(n)值 {
for (int i=0;i
{
for (int j=0;j
{
if (sn.getnode(i,j)!=goal.getnode(i,j) && sn.getnode(i,j)!=0)
{
for (int m=0;m
{
for (int n=0;n
{
if (sn.getnode(i,j)==goal.getnode(m,n))
{
sn.hs+=(abs(i-m)+abs(j-n));
}
}
}
}
}
}
}
bool isgoal(StateNode &sn,StateNode &goal) //判断当前节点是否目标节点 {
return sn==goal;
}
bool uninlist(StateNode &sn,list &lsn)
{
}
//判断当前节点是不是在OPEN表或者CLOSED表中 list::iterator iter; for (iter=lsn.begin();iter!=lsn.end();iter++) { if (*iter==sn) { return false; } } return true;
void addtolist(StateNode &sn,list &lsn,list &lcsn)
{ //根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式 list::iterator iter;
list::iterator iterc;
if (uninlist(sn,lsn) && uninlist(sn,lcsn))
{
for (iter=lsn.begin();iter!=lsn.end() && sn.fs>=iter->fs;iter++){}
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))
{
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++){}
lsn.insert(iter,*lcsn.erase(iterc));
}
}
}
void evaluandadd(StateNode &temsn,StateNode &sn,StateNode &goal,list &lsn,list &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 &lsn,list &lcsn)
{ //扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作 StateNode temsn;
list::iterator iter; for (int i=0;i0) //向左移动 { temsn=sn; temsn.swap(i,j,i-1,j); temsn.psn=&sn; evaluandadd(temsn,sn,goal,lsn,lcsn); }
if (i
temsn=sn;
temsn.swap(i,j,i+1,j);
temsn.psn=&sn;
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
temsn=sn;
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 OPEN; list CLOSED; list::iterator iter; list::iterator iterc; Goal.putgoalnode(); Start.putstartnode(); evaluatefunction(Start,Goal); Start.gs=0; Start.fs=Start.gs+Start.hs; OPEN.push_back(Start); for (iter=OPEN.begin(),i=0;iter!=OPEN.end() && ipsn,j++) { coutprintstatenode(); coutMAXNUM) { cout