人工智能A星算法及人工智能部分习题答案.docx

人工智能A星算法及人工智能部分习题答案.docx

《人工智能A星算法及人工智能部分习题答案.docx》由会员分享，可在线阅读，更多相关《人工智能A星算法及人工智能部分习题答案.docx（42页珍藏版）》请在冰点文库上搜索。

人工智能A星算法及人工智能部分习题答案

A*算法实验报告

实验目的

1．熟悉和掌握启发式搜索的定义、估价函数和算法过程

2.学会利用A*算法求解N数码难题

3.理解求解流程和搜索顺序

实验原理

A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。

对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。

因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：

从起始节点到节点n的代价以及从节点n到达目标节点的代价。

实验条件

1.WindowNT/xp/7及以上的操作系统

2.内存在512M以上

3.CPU在奔腾II以上

实验内容

1.分别以8数码和15数码为例实际求解A*算法

2.画出A*算法求解框图

3.分析估价函数对搜索算法的影响

4.分析A*算法的特点

实验分析

1.A*算法基本步骤

1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。

2）生成一个列表CLOSED，它的初始值为空。

3）如果OPEN表为空，则失败退出。

4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。

5）如果n是目标节点，顺着G中，从n到n0的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。

6）扩展节点n，生成其后继结点集M，在G中，n的祖先不能在M中。

在G中安置M的成员，使他们成为n的后继。

7）从M的每一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中，也不在CLOSED中）。

把M1的这些成员加到OPEN中。

对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止找到的到达m的最好路径通过n，就把它的指针指向n。

对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。

8）按递增f*值，重排OPEN（相同最小f*值可根据搜索树中的最深节点来解决）。

9）返回第3步。

在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。

已经在CLOSED中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。

实验步骤

算法流程图

程序代码

#include

#include

#include

usingnamespacestd;

constintROW=3;//行数

constintCOL=3;//列数

constintMAXDISTANCE=10000;//最多可以有的表的数目

constintMAXNUM=10000;

typedefstruct_Node{

intdigit[ROW][COL];

intdist;//一个表和目的表的距离

intdep;//t深度

intindex;//节点的位置

}Node;

Nodesrc,dest;//父节表目的表

vectornode_v;//存储节点

boolisEmptyOfOPEN（）//open表是否为空

{

for（inti=0;i

if（node_v[i].dist!

=MAXNUM）

returnfalse;

}

returntrue;

}

boolisEqual（intindex,intdigit[][COL]）//判断这个最优的节点是否和目的节点一样

{

for（inti=0;i

for（intj=0;j

if（node_v[index].digit[i][j]!

=digit[i][j]）

returnfalse;

}

returntrue;

}

ostream&operator<<（ostream&os,Node&node）

{

for（inti=0;i

for（intj=0;j

os<

os<

}

returnos;

}

voidPrintSteps（intindex,vector&rstep_v）//输出每一个遍历的节点深度遍历

{

rstep_v.push_back（node_v[index]）;

index=node_v[index].index;

while（index!

=0）

{

rstep_v.push_back（node_v[index]）;

index=node_v[index].index;

}

for（inti=rstep_v.size（）-1;i>=0;i--）//输出每一步的探索过程

cout<<"Step"<

<

}

voidSwap（int&a,int&b）

{

intt;

t=a;

a=b;

b=t;

}

voidAssign（Node&node,intindex）

{

for（inti=0;i

for（intj=0;j

node.digit[i][j]=node_v[index].digit[i][j];

}

intGetMinNode（）//找到最小的节点的位置即最优节点

{

intdist=MAXNUM;

intloc;//thelocationofminimizenode

for（inti=0;i

{

if（node_v[i].dist==MAXNUM）

continue;

elseif（（node_v[i].dist+node_v[i].dep）

loc=i;

dist=node_v[i].dist+node_v[i].dep;

}

}

returnloc;

}

boolisExpandable（Node&node）

{

for（inti=0;i

if（isEqual（i,node.digit））

returnfalse;

}

returntrue;

}

intDistance（Node&node,intdigit[][COL]）

{

intdistance=0;

boolflag=false;

for（inti=0;i

for（intj=0;j

for（intk=0;k

for（intl=0;l

if（node.digit[i][j]==digit[k][l]）{

distance+=abs（i-k）+abs（j-l）;

flag=true;

break;

}

else

flag=false;

}

if（flag）

break;

}

returndistance;

}

intMinDistance（inta,intb）

{

return（a

a:

b）;

}

voidProcessNode（intindex）

{

intx,y;

boolflag;

for（inti=0;i

for（intj=0;j

if（node_v[index].digit[i][j]==0）

{

x=i;y=j;

flag=true;

break;

}

elseflag=false;

}

if（flag）

break;

}

Nodenode_up;

Assign（node_up,index）;//向上扩展的节点

intdist_up=MAXDISTANCE;

if（x>0）

{

Swap（node_up.digit[x][y],node_up.digit[x-1][y]）;

if（isExpandable（node_up））

{

dist_up=Distance（node_up,dest.digit）;

node_up.index=index;

node_up.dist=dist_up;

node_up.dep=node_v[index].dep+1;

node_v.push_back（node_up）;

}

}

Nodenode_down;

Assign（node_down,index）;//向下扩展的节点

intdist_down=MAXDISTANCE;

if（x<2）

{

Swap（node_down.digit[x][y],node_down.digit[x+1][y]）;

if（isExpandable（node_down））

{

dist_down=Distance（node_down,dest.digit）;

node_down.index=index;

node_down.dist=dist_down;

node_down.dep=node_v[index].dep+1;

node_v.push_back（node_down）;

}

}

Nodenode_left;

Assign（node_left,index）;//向左扩展的节点

intdist_left=MAXDISTANCE;

if（y>0）

{

Swap（node_left.digit[x][y],node_left.digit[x][y-1]）;

if（isExpandable（node_left））

{

dist_left=Distance（node_left,dest.digit）;

node_left.index=index;

node_left.dist=dist_left;

node_left.dep=node_v[index].dep+1;

node_v.push_back（node_left）;

}

}

Nodenode_right;

Assign（node_right,index）;//向右扩展的节点

intdist_right=MAXDISTANCE;

if（y<2）

{

Swap（node_right.digit[x][y],node_right.digit[x][y+1]）;

if（isExpandable（node_right））

{

dist_right=Distance（node_right,dest.digit）;

node_right.index=index;

node_right.dist=dist_right;

node_right.dep=node_v[index].dep+1;

node_v.push_back（node_right）;

}

}

node_v[index].dist=MAXNUM;

}

intmain（）//主函数

{

intnumber;

cout<<"Inputsource:

"<

for（inti=0;i

for（intj=0;j

cin>>number;

src.digit[i][j]=number;

}

src.index=0;

src.dep=1;

cout<<"Inputdestination:

"<

for（intm=0;m

for（intn=0;n

cin>>number;

dest.digit[m][n]=number;

}

node_v.push_back（src）;//在容器的尾部加一个数据

cout<<"Search..."<

clock_tstart=clock（）;

while

（1）

{

if（isEmptyOfOPEN（））

{

cout<<"Cann'tsolvethisstatement!

"<

return-1;

}

else

{

intloc;//thelocationoftheminimizenode最优节点的位置

loc=GetMinNode（）;

if（isEqual（loc,dest.digit））

{

vectorrstep_v;

cout<<"Source:

"<

cout<

PrintSteps（loc,rstep_v）;

cout<<"Successful!

"<

cout<<"Using"<<（clock（）-start）/CLOCKS_PER_SEC

<<"seconds."<

break;

}

else

ProcessNode（loc）;

}

}

return0;

}

程序运行效果图

2

8

3

1

6

4

7

5

（初始状态）

1

2

3

8

0

4

7

6

5

（结束状态）

个人实验小结

A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。

对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。

通过本实验，我熟悉启发式搜索的定义、估价函数和算法过程，并利用A*算法求解了8数码难题，理解了求解流程和搜索顺序。

实验过程中巩固了所学的知识，通过实验也提高了自己的编程和思维能力，收获很多。

1.什么是人类智能？

它有哪些特征或特点？

定义：

人类所具有的智力和行为能力。

特点：

主要体现为感知能力、记忆与思维能力、归纳与演绎能力、学习能力以及行为能力。

2.人工智能是何时、何地、怎样诞生的？

解：

人工智能于1956年夏季在美国Dartmouth大学诞生。

此时此地举办的关于用机器模拟人类智能问题的研讨会，第一次使用“人工智能”这一术语，标志着人工智能学科的诞生。

3.什么是人工智能？

它的研究目标是？

定义：

用机器模拟人类智能。

研究目标：

用计算机模仿人脑思维活动，解决复杂问题；从实用的观点来看，以知识为对象，研究知识的获取、知识的表示方法和知识的使用。

4.人工智能的发展经历了哪几个阶段？

解：

第一阶段：

孕育期（1956年以前）；第二阶段：

人工智能基础技术的研究和形成（1956~1970年）；第三阶段：

发展和实用化阶段（1971~1980年）；第四阶段：

知识工程和专家系统（1980年至今）。

5.人工智能研究的基本内容有哪些？

解：

知识的获取、表示和使用。

6.人工智能有哪些主要研究领域？

解：

问题求解、专家系统、机器学习、模式识别、自动定论证明、自动程序设计、自然语言理解、机器人学、人工神经网络和智能检索等。

7.人工智能有哪几个主要学派？

各自的特点是什么？

主要学派：

符号主义和联结主义。

特点：

符号主义认为人类智能的基本单元是符号，认识过程就是符号表示下的符号计算，从而思维就是符号计算；联结主义认为人类智能的基本单元是神经元，认识过程是由神经元构成的网络的信息传递，这种传递是并行分布进行的。

8.人工智能的近期发展趋势有哪些？

解：

专家系统、机器人学、人工神经网络和智能检索。

9.什么是以符号处理为核心的方法？

它有什么特征？

解：

通过符号处理来模拟人类求解问题的心理过程。

特征：

基于数学逻辑对知识进行表示和推理。

11.什么是以网络连接为主的连接机制方法？

它有什么特征？

解：

用硬件模拟人类神经网络，实现人类智能在机器上的模拟。

特征：

研究神经网络。

1.请写出用一阶谓词逻辑表示法表示知识的步骤。

步骤：

（1）定义谓词及个体，确定每个谓词及个体的确切含义；

（2）根据所要表达的事物或概念，为每个谓词中的变元赋予特定的值；（3）根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来，形成谓词公式。

2.设有下列语句，请用相应的谓词公式把它们表示出来：

（1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。

解：

定义谓词如下：

Like（x,y）：

x喜欢y。

Club（x）：

x是梅花。

Human（x）：

x是人。

Mum（x）：

x是菊花。

“有的人喜欢梅花”可表达为：

（x）（Human（x）Like（x,Club（x）））

“有的人喜欢菊花”可表达为：

（x）（Human（x）Like（x,Mum（x）））

“有的人既喜欢梅花又喜欢菊花”可表达为：

（x）（Human（x）Like（x,Club（x））Like（x,Mum（x）））

（1）他每天下午都去玩足球。

解：

定义谓词如下：

PlayFootball（x）：

x玩足球。

Day（x）：

x是某一天。

则语句可表达为：

（x）（D（x）PlayFootball（Ta））

（2）太原市的夏天既干燥又炎热。

解：

定义谓词如下：

Summer（x）：

x的夏天。

Dry（x）：

x是干燥的。

Hot（x）：

x是炎热的。

则语句可表达为：

Dry（Summer（Taiyuan））Hot（Summer（Taiyuan））

（3）所有人都有饭吃。

解：

定义谓词如下：

Human（x）：

x是人。

Eat（x）：

x有饭吃。

则语句可表达为：

（x）（Human（x）Eat（x））

（4）喜欢玩篮球的人必喜欢玩排球。

解：

定义谓词如下：

Like（x,y）：

x喜欢y。

Human（x）：

x是人。

则语句可表达为：

（x）（（Human（x）Like（x,basketball））Like（x,volleyball））

（5）要想出国留学，必须通过外语考试。

解：

定义谓词如下：

Abroad（x）：

x出国留学。

Pass（x）：

x通过外语考试。

则语句可表达为：

Abroad（x）Pass（x）

、

猴子问题：

2.7解：

根据谓词知识表示的步骤求解问题如下：

解法一：

（1）本问题涉及的常量定义为：

猴子：

Monkey，箱子：

Box，香蕉：

Banana，位置：

a，b，c

（2）定义谓词如下：

SITE（x，y）：

表示x在y处；

HANG（x，y）：

表示x悬挂在y处；

ON（x，y）：

表示x站在y上；

HOLDS（y，w）：

表示y手里拿着w。

（3）根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下：

问题的初始状态表示：

SITE（Monkey，a）∧HANG（Banana，b）∧SITE（Box，c）∧~ON（Monkey，Box）∧~HOLDS（Monkey，Banana）

问题的目标状态表示：

SITE（Monkey，b）∧~HANG（Banana，b）∧SITE（Box，b）

∧ON（Monkey，Box）∧HOLDS（Monkey，Banana）

解法二：

本问题涉及的常量定义为：

猴子：

Monkey，箱子：

Box，香蕉：

Banana，位置：

a，b，c

定义谓词如下：

SITE（x，y）：

表示x在y处；

ONBOX（x）：

表示x站在箱子顶上；

HOLDS（x）：

表示x摘到了香蕉。

（3）根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下：

问题的初始状态表示：

SITE（Monkey，a）∧SITE（Box，c）∧~ONBOX（Monkey）∧~HOLDS（Monkey）

问题的目标状态表示：

SITE（Box，b）∧SITE（Monkey，b）∧ONBOX（Monkey）∧HOLDS（Monkey）

从上述两种解法可以看出，只要谓词定义不同，问题的初始状态和目标状态就不同。

所以，对于同样的知识，不同的人的表示结果可能不同。

2.8解：

本问题的关键就是制定一组操作，将初始状态转换为目标状态。

为了用谓词公式表示操作，可将操作分为条件（为完成相应操作所必须具备的条件）和动作两部分。

条件易于用谓词公式表示，而动作则可通过执行该动作前后的状态变化表示出来，即由于动作的执行，当前状态中删去了某些谓词公式而又增加一些谓词公式从而得到了新的状态，通过这种不同状态中谓词公式的增、减来描述动作。

定义四个操作的谓词如下，操作的条件和动作可用谓词公式的增、删表示：

（1）goto

从x处走到y处。

条件：

SITE（Monkey，x）

动作：

删除SITE（Monkey，x）；增加SITE（Monkey，y）

（2）pushbox（x，y）：

将箱子从x处推到y处。

条件：

SITE（Monkey，x）∧SITE（Box，x）∧~ONBOX（Monkey）

动作：

删除SITE（Monkey，x），SITE（Box，x）；增加SITE（Monkey，y），SITE（Box，y）

（3）climbbox：

爬到箱子顶上。

条件：

~ONBOX（Monkey）

动作：

删除~ONBOX（Monkey）；增加ONBOX（Monkey）

（4）grasp：

摘下香蕉。

条件：

~HOLDS（Monkey）∧ONBOX（Monkey）∧SITE（Monkey，b）

动作：

删除~HOLDS（Monkey）；增加HOLDS（Monkey）

在执行某一操作前，先检查当前状态是否满足其前提条件。

若满足，则执行该操作。

否则，检查另一操作的条件是否被满足。

检查的方法就是当前的状态中是否蕴含了操作所要求的条件。

在定义了操作谓词后，就可以给出从初始状态到目标状态的求解过

程。

在求解过程中，当进行条件检查时，要进行适当的变量代换。

SITE（Monkey，a）

SITE（Box，c）

~ONBOX（Mon