人工智能导论 启发式图搜索Word文档下载推荐.docx
- 文档编号:7712650
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:16
- 大小:134.43KB
人工智能导论 启发式图搜索Word文档下载推荐.docx
《人工智能导论 启发式图搜索Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《人工智能导论 启发式图搜索Word文档下载推荐.docx(16页珍藏版)》请在冰点文库上搜索。
f()THENf():
=f(n,),标记到n的指针;
比较f(n,)和f(),f()是扩展n之前计算的耗散值。
=f(n,),标记到n的指针,ADD(,OPEN);
当f(n,)<
f()时,把重放回OPEN中,不必考虑修改到其子节点的指针。
OPEN中的节点按f值从小到大排列;
GOLOOP。
二、最佳图搜索算法A*:
当在算法A的评价函数中,使用的启发函数h(n)是处在h*(n)的下界范围,即满足h(n)<
=h*(n)时,则把这个算法称为算法A*。
在下面解决八数码问题的程序中,采用h(n)=P(n),P(n)定义为每一个将牌与其目标位置之间的距离的总和。
三、算法实现
(1)数据结构
classStateNode{
public:
intgs,hs,fs;
//分别表示算法中的g(n)、h(n)、f(n)
StateNode*psn;
//一个指向扩展出它的父节点的指针
StateNode();
//构造函数,初始化节点
voidputstartnode();
//输入开始节点
voidputgoalnode();
//输入目标节点
intgetnode(inti,intj);
//读取node[i][j]
voidswap(inti,intj,intm,intn);
//交换数组中指定位置的两个元素的数值
booloperator==(StateNode&
sn);
//重载了运算符==,方便后面进行比较
voidoperator=(StateNode&
//重载了运算符=,方便后面对节点进行整体赋值
voidprintstatenode();
//将每个节点的内容按照一定格式输出
private:
intnode[3][3];
//八数码的每个节点用一个二维数组存储
};
voidevaluatefunction(StateNode&
sn,StateNode&
goal);
//启发函数,计算某个节点的h(n)值
boolisgoal(StateNode&
//判断当前节点是否目标节点
booluninlist(StateNode&
sn,list<
StateNode>
&
lsn);
//判断当前节点是不是在OPEN表或者CLOSED表中
voidaddtolist(StateNode&
lsn,list<
lcsn);
//根据当前扩展到的节点的类型(mj,mk,ml)选择不同的操作方式
voidexpandnode(StateNode&
goal,list<
//扩展节点,计算节点的评价函数值,根据新的节点的类型选择不同的操作
list<
OPEN;
//使用STL中的list类型来存放OPEN表
CLOSED;
//使用STL中的list类型来存放CLOSED表
(2)运行过程演示:
四、程序代码(C++):
#include<
iostream>
list>
math.h>
usingnamespacestd;
#defineMAXNUM1000
classStateNode//这是一个节点类型的类,定义了与节点相关的信息及函数
{
StateNode()
{
gs=0;
hs=0;
fs=gs+hs;
psn=0;
for(inti=0;
i<
3;
i++)
{
for(intj=0;
j<
j++)
{
node[i][j]=0;
}
}
}
voidputstartnode()
cout<
<
"
请输入目标状态!
(空闲的格子用0表示)"
endl;
cin>
>
node[i][j];
voidputgoalnode()
请输入初始状态!
intgetnode(inti,intj)//读取node[i][j]
returnnode[i][j];
voidswap(inti,intj,intm,intn)//交换数组中指定位置的两个元素的数值
inttemp;
temp=node[i][j];
node[i][j]=node[m][n];
node[m][n]=temp;
sn)//重载了运算符==,方便后面进行比较
intn=0;
if(node[i][j]==sn.getnode(i,j))
{
n++;
}
if(n<
9)
returnfalse;
elsereturntrue;
voidoperator=(StateNode&
sn)//重载了运算符=,方便后面对节点进行整体赋值
node[i][j]=sn.getnode(i,j);
this->
gs=sn.gs;
hs=sn.hs;
fs=sn.fs;
psn=sn.psn;
voidprintstatenode()//将每个节点的内容按照一定格式输出
cout<
node[i][j]<
"
;
cout<
\n"
protected:
goal)//启发函数,计算某个节点的h(n)值
for(inti=0;
for(intj=0;
if(sn.getnode(i,j)!
=goal.getnode(i,j)&
&
sn.getnode(i,j)!
=0)
for(intm=0;
m<
m++)
for(intn=0;
n<
n++)
{
if(sn.getnode(i,j)==goal.getnode(m,n))
{
sn.hs+=(abs(i-m)+abs(j-n));
}
}
}
goal)//判断当前节点是否目标节点
returnsn==goal;
lsn)
{//判断当前节点是不是在OPEN表或者CLOSED表中
list<
:
iteratoriter;
for(iter=lsn.begin();
iter!
=lsn.end();
iter++)
if(*iter==sn)
returntrue;
lcsn)
{//根据当前扩展到的节点的类型(mj,mk,ml)选择不同的操作方式
iteratoriterc;
if(uninlist(sn,lsn)&
uninlist(sn,lcsn))
for(iter=lsn.begin();
=lsn.end()&
sn.fs>
=iter->
fs;
iter++){}
lsn.insert(iter,sn);
elseif(!
uninlist(sn,lsn))
if(*iter==sn){break;
if(iter->
fs>
sn.fs){*iter=sn;
elseif(!
uninlist(sn,lcsn))
for(iterc=lcsn.begin();
iterc!
=lcsn.end();
iterc++)
if(*iterc==sn){break;
if(iterc->
sn.fs)
for(iter=lsn.begin();
lsn.insert(iter,*lcsn.erase(iterc));
voidevaluandadd(StateNode&
temsn,StateNode&
lcsn)
temsn.gs=sn.gs+1;
temsn.hs=0;
evaluatefunction(temsn,goal);
temsn.fs=temsn.gs+temsn.hs;
addtolist(temsn,lsn,lcsn);
{//扩展节点,计算节点的评价函数值,根据新的节点的类型选择不同的操作
StateNodetemsn;
if(sn.getnode(i,j)==0)
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.swap(i,j,i+1,j);
if(j>
0)//向上移动
temsn.swap(i,j,i,j-1);
if(j<
2)//向下移动
temsn.swap(i,j,i,j+1);
intmain()
StateNodeStart,SN[MAXNUM],Goal;
inti,j=0;
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;
=OPEN.end()&
i<
MAXNUM;
iter=OPEN.begin(),i++)
if(OPEN.empty()){return0;
SN[i]=OPEN.front();
if(isgoal(SN[i],Goal))
搜索过程如下所示:
for(StateNode*tempsn=&
SN[i];
!
(*tempsn==Start);
tempsn=tempsn->
psn,j++)
第"
步搜索:
tempsn->
printstatenode();
Start.printstatenode();
return1;
OPEN.pop_front();
CLOSED.push_back(SN[i]);
if(CLOSED.size()>
MAXNUM)
该初始节点不可扩展至目标节点!
return0;
expandnode(SN[i],Goal,OPEN,CLOSED);
return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能导论 启发式图搜索 人工智能 导论 启发式 搜索