2013春人工智能复习题带答案 2

一、 是非判断题

1、消解时主要通过推导空子句来实现反证的。 （√） 2、 L、?L 为互解文字，L∧?L=》[]。 （√）

3、(P(x) ∧Q(y))∨(P(x) ∧R(y))为合取范式。（×） 4、若P 为时真时假，则P 仍为永真式。（×）

5、\?x(p(x)?R（x))中的P（X）不在\的辖域中。（×）

6、极小极大分析法中采用逆向推算来计算节点得分的。（√） 7、解树一定是代价最小。（×）

8、本原问题即直接可解的简单问题。（√）

9、与或图搜索也可分为盲目搜索和启发式搜索。（√）

10、对α-β剪枝技术中，对与节点来说，α是倒推值的下确界，β是倒推 值的上确界。（×）

11、语义网络是一种有向图，它有5 个级别，7 种类型。（√） 12、方位关系不在语义网络表示的范围内。（×） 13、对象与类是实例关系。（√）

14、基于语义网络的推理主要有网络匹配、网络继承和网络演绎三种 方式。（√）

15、对“与”、“或”、“蕴含”关系，在语义网络表示时主要加上 “与”、“或”、“蕴含”结点。（√）

16、框架之间也有从属关系、实例关系等。（√） 17、专家系统是由数名专家组成的咨询系统。（×）

18、用普通的程序设计语言开发专家系统的开发周期最长，效率最 低，但限制最小。（×）

19、网络环境下的专家系统结构可以分为客户机/服务器或浏览器/ 服务器结构。（√）

20、黑板模型中的黑板就是一个全局数据库。（√） 21、智能机器人的智能已经达到人类智能的水平。（×） 22、人也可以作为Agent。（√）

二、填空题

1、 人工智能程序与传统的计算机程序相比，有如下特点：

①AI以符号表示的只是为研究对象，而不是以数值数据为研究对象 ②AI 采用启发式推理方法、而不是常规的算法 ③AI中控制结构与领域只是分离 ④AI中允许出现不正确的解答

2、 产生式系统包括知识库和推理机。知识库有（规则库）和数据库组成，因此知识库中存放

（产生式规则）和事实。推理机是一个程序，推理方式有（正向）推里、（反向）推理和（混合）推理。

3、 状态空间搜索中宽度优先属于（盲目搜索），A*算法属于（启发式搜索） 4、 归结方法是一种机械化的（反）向推理方法

5、 在归结原理中，空字句不含有文字，它（不能）被任何解释满足，所以空字句是（永假的）。

归结过程出现空字句，说明出现了互补的文字对，说明字句集是（不可满足的）

6、 归结推理过程中的删除策略是指：对字句集S使用归结推理过程中，当归结式Cj是（重言式），或者Cj被S中字句或归结式Ci（i?j）所（包含）时，可以删除Cj。

7、 简单遗传算法的主要操作有（选择）、（交叉）、（变异），个体的选择一般采用（轮盘赌）产生各个体的再生数目。

8、在状态空间搜索的一般过程中，常常需要（ OPEN表 ）、（ CLOSED表 ）两个数据结构，它们的作用分别是（OPEN表：已经生成但是还未扩展的节点）、（CLOSED表：将要扩展或已经扩展并生成了其子女的节点）

9、在语义网络中，为了表示节点间属性的继承推理，规定了两个约定俗成的链，命名为 （ISA）和（AKO），用来表明类和子类、类和个体之间的关系。

10、人工智能是1956年、在美国的达特茅斯大学诞生的。大会由麦卡锡.MaCarthy）教授正式提出“人工智能”这一术语。

11、人工智能主要有机器学习、专家系统和自然语言处理研究领域

12、在人工智能中，通常知识有基于逻辑谓词逻辑表示法、产生式系统表示法、语义网络表示法、框架表示法、过程表示法等表示的方法

13、开发专家系统需要解决知识获取、知识表示和知识推理三个基本问题。

14、语义网络是用有向图方法表示的【节点1，有向弧，节点2】三元式连接而成的。其中节点表示事物、概念、事件或情况等；弧表示节点间的语义关系。

15、评价一个搜索策略的好坏，主要是两个方面：找到解的速度，找到解的质量

*

16、搜索策略主要包括：盲目搜索，启发式搜索，A索策略集中策略。 17、推理的形式主要有正向推理，反向推理，双向推理的三种方式。

三、选择题

1、基于“有限合理性原理”和“物理符号系统假设”的人工智能学派一般指的是（a） a.符号主义 b.联结主义 c.行为主义

2、为了证明A1?A2?...?An?B，可以采用归结反演的方法，通常认为A1、A2、.....、An之间是（ b ）的，这时如果A1?A2?...?An??B通过归结，可以得出空字句，说明?B和A1、A2、.....、An之间是（ a ）的，也就是说明B和A1、A2、.....、An之间是（ b ）的

a.有矛盾 b.无矛盾 c.无法确定

3、每次归结时，首先从字句集S中选取一个称为顶字句C0开始做归结；其次将归结过程中所

得到的归结式Ci立即同另外一个字句Bi进行归结，刀刀归结式Ci+1，而Bi是原始字句集S中的一个字句或者是已经归结出的某个归结式Cj（j

a. 支持集策略 b.输入策略 c.线性归结策略

4、XOR问题一般可以用下面那种模型来解决（ c ）

a. 神经元 b.单层感知器 c.多层感知器

5、标准逻辑（谓词逻辑）中，重言式是 a

a．永真 B. 永假 C.为非永真

四、 计算题

1、用谓词表示法求解机器人摞积木问题。设机器人有一只机械手，要处理的世界有一张桌子，桌上可堆放若干相同的方积木块。机械手有4个操作积木的典型动作：从桌上拣起一块积木；将手中的积木放到桌之上；在积木上再摞上一块积木；从积木上面拣起一块积木。积木世界的布局如下图所示。

A

B A

B C

四、 图 机器人摞积木问题

解：(1) 先定义描述状态的谓词 CLEAR(x)：积木x上面是空的。 ON(x, y)：积木x在积木y的上面。 ONTABLE(x)：积木x在桌子上。 HOLDING(x)：机械手抓住x。 HANDEMPTY：机械手是空的。

其中，x和y的个体域都是{A, B, C}。 问题的初始状态是： ONTABLE(A) ONTABLE(B) ON(C, A) CLEAR(B) CLEAR(C)

HANDEMPTY

问题的目标状态是： ONTABLE(C) ON(B, C) ON(A, B) CLEAR(A) HANDEMPTY

(2) 再定义描述操作的谓词

在本问题中，机械手的操作需要定义以下4个谓词： Pickup(x)：从桌面上拣起一块积木x。 Putdown(x)：将手中的积木放到桌面上。

Stack(x, y)：在积木x上面再摞上一块积木y。 Upstack(x, y)：从积木x上面拣起一块积木y。

其中，每一个操作都可分为条件和动作两部分，具体描述如下： Pickup(x)

条件：ONTABLE(x)，HANDEMPTY，CLEAR(x) 动作：删除表：ONTABLE(x)，HANDEMPTY 添加表：HANDEMPTY(x) Putdown(x)

条件：HANDEMPTY(x)

动作：删除表：HANDEMPTY(x)

添加表：ONTABLE(x)，CLEAR(x) ，HANDEMPTY Stack(x, y)

条件：HANDEMPTY(x)，CLEAR(y)

动作：删除表：HANDEMPTY(x)，CLEAR(y)

添加表：HANDEMPTY，ON(x, y) ，CLEAR(x) Upstack(x, y)

条件：HANDEMPTY，CLEAR(y) ，ON(y,x) 动作：删除表：HANDEMPTY，ON(y, x) 添加表：HOLDING(y)，CLEAR(x) (3) 问题求解过程

利用上述谓词和操作，其求解过程为： ONTABLE(A) ONTABLE(A) ONTABLE(A) ONTABLE(B) ONTABLE(B) ONTABLE(B) Upstack(A,C) Putdown(C) ONTABLE(C) Pickup(B) ON(C, A) HOLDING(C) CLEAR(A) CLEAR(B) CLEAR(A) CLEAR(B) CLEAR(C) CLEAR(B) CLEAR(C) HANDEMPTY CLEAR(C) HANDEMPTY ONTABLE(A) ONTABLE(A) 五、 ONTABLE(CONTABLE(CONTABLE(C) 六、 Stack(C,B) ONTABLE(C) Pickup(A) ) ) Stack(B,A) HOLDING(B) ON(B,C) 七、 ON(B,C) ON(B,C) CLEAR(A) CLEAR(A) 八、 ON(A,B) CLEAR(A) CLEAR(B) CLEAR(B) CLEAR(A) CLEAR(B) CLEAR(C) HANDEMPT HANDEMPT HOLDING(AY

2、 用语义网络和框架方法表示下属知识

（1）John gives a book to Mary

Giving-Events Object G1 ISA Human ISA

（2）高老师从3月到7月给计算机系学生讲《计算机网络》课。 解： 7月 8月

End Start

ISA 老师 高老师 Action 讲课 Subjec讲课事件 Object Caurse 计算机网络 计算机系学生 Recipient Mary ISA Book1 ISA Book Giver John （3）创新公司在科海大街56号，刘洋是该公司的经理，他32岁、硕士学位。 解：

56号 32岁 硕士

Number Degree Age

科海大刘洋 经理 创新公司 HeadshiLocated-at Work-for

3、 什么是???过程，基本思想树什么？

答：在极大极小过程中，总是先生成一颗博弈树，而且会生成规定深度内的所有节点，然后在进行估值的倒退计算，这样使得生成博弈树和估计值的倒退计算两个过程分离，因此搜索效率较低。如果能边生成博弈树，边进行估值的计算，则可能不必生成对顶深度内的所有节点，以减少搜索的次数，这就是???过程。

???过程的基本思想：首先使搜索树的某一部分达到最大深度，这时计算出某些MAX

节点的?值，或者是某些MIN节点的?值。随着搜索的继续，不断修改个别节点的?或者?。对任意节点，当其某一后继结点的最终值给定时，就可以确定该节点的?或者?。当该节点的其他后继节点的最终值给定时，就可以对该节点的?或者?进行修正。

若任何MIN节点的?值小于或者任何他的先辈MAX节点的?值，则可停止该MIN节点以下的搜索，然后这个MIN节点的最终倒退至结尾它已经得到的?，该值与真正的极大极小的搜索结果的倒退值可能不一样，但是对开始节点而言，倒退至是相同的。当满足该规则时，可以进行?剪枝。

若任何MAX节点的?值大于或者等于它的MIN先辈节点的?值，则可以停止该MAX节点以下的搜索，然后这个MAX节点处的倒退值解为它的?值。当满足该规则时，可以进行?剪枝。

4、 假设N个传教士和N个野人，传每次最多可供K个人乘渡，这里N?5,K?3。

假设在某一时刻，在河的左岸有M个传教士，C个野人。B?1表示船在左岸，

现在已它们的组合作为启发式函数的基本分量。给定下面两B?0表示船在右岸。

种不同的启发式函数：

（1）h1(n)?M?C （2）h2(n)?M?C?2B

试说明h1(n)不满足h1(n)?h(n)，而h2(n)?h(n)

答：（1）要说明h1(n)不满足h1(n)?h(n)，只要给出一个反例。如状态

（M,C,B）=（1,1,1）时，h1(n)?M?C=1+1=2，而实际上只要摆渡一次就可以达到目标。所以h1(n)不满足h1(n)?h(n)

（2）要证明h2(n)?h(n)，从两种情况说明。

A、船在左岸的情况

如果不考虑限制条件，那么摆渡的次数肯定比有限制的摆渡的次数少。另外每船载三人的摆渡次数肯定比每船载2人的次数少。所以先考虑没有限制的条件下，每次船上可以在人数为3人

*****时的摆渡次数为次。其中分子中的“-3”表示剩下最后3个留待者最后一次运过去。除以2是因为一个来回可以运过去2个人，需要??M?c?3?个来回，乘以2是因为一个来回相当于两?2??次摆渡，而最后的加1，则表示将剩下的3个人运过去，需要一次摆渡。化简为

M?C?3?M?c?3?*2?1?*2?1?M?C?2 ??22??B、考虑船在右岸的情况

同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此对于状态(M,C,0)来说，七所需要的最少摆渡数，相当于船在左岸时状态(M?1,C,1)或者(M,C?1,1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡次数为：

(M?C?1)?2?1?M?C，其中M?C?1中的+1表示送船回到左岸的那个人，最后边+1

表示送船到左岸时的一次摆渡。化简得到

(M?C?1)?2?1?M?C

综上分析，所需要的最少摆渡次数可以为M?C?2B

由于该摆渡次数是在不考虑限制的条件选推出的最少所需要的摆渡次数。因此，当有限制条件的时候，最优的摆渡次数只能大于或等于该摆渡次数。所以启发式函数h2(n)满足

h2(n)?h*(n)

5、考虑下面的博弈树，静态值（在叶节点的圆括号中）都是从第一个博弈者的角度得的。假设第一个博弈者为MAX，如图所示。 （1）第一个博弈者将选择什么移动？

（2）假如采用???算法。那些节点无须检验（假设节点按从左到右的顺序检验） L 2 M 3 A B C D E A F A G H I J K N 8 O 5 P 7 Q 6 R 0 S 1 T 5 U 2 V 8 W 4 X 10 Y 2 (1) D

(2) O、Q、I（因此T和U）Y。

6、 简述用归结法证明定理的过程（消解反演求解过程）。

给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下： （1）否定L，得到~L； （2）把~L添加到S中去；

（3）把新产生的集合{~L，S}化成子句集F；

（4）（以前）应用消解原理，力图推导出一个表示矛盾的空子句

（现在ppt）反复归结子句集F中的子句，若出现了空子句，则停止归结，此时就证明了L永真

7、计算下述各字句对的归结式 （1）C1:P?R，C2:?P?Q （2）C1:?P?Q，C2:P

（3）C1:?P?Q?R，C2:?Q??R （4）C1:?P?Q，C2:?P?R （5）C1:Q,C2:?Q

解：（1）两个字句的归结式为：C12:R?Q （2）两个字句的归结式为：C12:Q

（3）两个字句的归结式为存在两个归给式：C12:?P?R??R或者C12:?P?Q??Q。该字句中，只能在Q上或R上归结，不能两者同时归结。所以?P不是归结式

（4）C1中的任何文字都不能与C2中的文字构成互补对，所以C1和C2不存在归结式

（5）

Q和?Q是文字互补对。所以C12:（空字句）

8、将合式公式化为字句形

?x[?P(x)?[?y[?P(y)?P(f(x,y))]???y[?Q(x,y)?P(y)]]]

解：

?x[?P(x)?[?y[?P(y)?P(f(x,y))]???y[?Q(x,y)?P(y)]]]

= ?x[?P(x)?[?y[?P(y)?P(f(x,y))]??y[Q(x,y)??P(y)]]] = ?x[?P(x)?[?y[?P(y)?P(f(x,y))]??w[Q(x,w)??P(w)]]] = ?x[?P(x)?[?y[?P(y)?P(f(x,y))]?[Q(x,g(x))??P(g(x))]]] =?x?y[?P(x)?[[?P(y)?P(f(x,y))]?[Q(x,g(x))??P(g(x))]]]

= ?x?y[[?P(x)?[?P(y)?P(f(x,y))]]?[?P(x)?Q(x,g(x))]?[?P(x)??P(g(x))]] 最后消去全称量词和连接词? ①[?P(x)??P(y)?P(f(x,y))] ②[?P(x)?Q(x,g(x))] ③[?P(x)??P(g(x))]

更改变量名称，于是有

?P(x1)??P(y)?P(f(x1,y)) ?P(x2)?Q(x2,g(x2)) ?P(x3)??P(g(x3))

9、设已知：

(1) 如果x是y的父亲，y是z的父亲，则x是z的祖父； (2) 每个人都有一个父亲。

使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。 解：先定义谓词

F(x,y)：x是y的父亲 GF(x,z)：x是z的祖父 P(x)：x是一个人

再用谓词把问题描述出来：

已知F1：(?x) (?y) (?z)( F(x,y)∧F(y,z))→GF(x,z)) F2：(?y)(P(x)→F(x,y))

求证结论G：(?u) (?v)( P(u)→GF(v,u)) 然后再将F1，F2和?G化成子句集： ① ?F(x,y)∨?F(y,z)∨GF(x,z)

② ?P(r)∨F(s,r)

③ P(u)

④ ?GF(v,u))

对上述扩充的子句集，其归结推理过程如下：

?F(x,y)∨?F(y,z)∨GF(x,z) ?GF(v,u)

{x/v,z/u}

?F(x,y)∨?F(y,z) ?P(r)∨F(s,r)

{x/s,y/r} ?F(y,z)∨?P(y) ?P(r)∨F(s,r)

{y/s,z/r} ?P(y)∨?P(z

{y/z} P(u) ?P(y)

{y/u} NIL

10、计算及简答

1、 已知产生式系统中具有下面的规则

R1：IF (X 身上有毛) Then （X 是哺乳动物） R2：IF （X喂奶）Then （X 是哺乳动物）

R3：IF （X 会飞）and （X 产卵）Then （X是鸟类） R4：IF （X有翅膀） and（X 不是企鹅）Then （X会飞）

R5：IF （X 是哺乳动物）and （X吃肉）Then （X 是食肉动物）

R6: IF （X 是哺乳动物）and （X有尖锐的牙齿）and （X有锋利的爪子）

Then（X 是食肉动物）

R7：IF（X 是哺乳动物）and （X 有蹄子）Then （X是有蹄动物）

R8：IF（X 是食肉动物）and （X的身体是黄褐色）and （X有黑色条纹）

Then （X是老虎）

R9：IF（X 是食肉动物）and （X的身体是黄褐色）and （X有黑色斑点）

Then （X是猎豹） 事实集合为： D1：（阿郎身上有毛） D2：（阿郎有尖锐的牙齿） D3：（阿郎有锋利的爪子） D4：（阿郎身体的颜色是黄褐色） D5：（阿郎身上有黑色斑点） 控制策略的考虑顺序为

C1：把已经执行过得一组规则从冲突集合中去掉 C2：选择具有更新数据的一组规则

C3：选择规则条件部分文字最多的一组规则 C4：选择任意一组规则 试问用前向推理如何运作？

解： 事实 D1 D6、D2、D3 D7、D4、D5

规则 R1 消去 R6 消去 消去 R9 冲突集合 {R1，{D1}} {R1，{D1}} 策略 C2 C1 更新数据库 D6：阿郎是哺乳动物 D7：阿郎是食肉动物 D8：阿郎是猎豹 {R6，{D2、D3、C3 D6}} {R1，{D1}} C1 {R6，{D2、D3、C1 D6}} {R9，{D4、D5、C3 D7}

11、论述产生式系统求解问题的基本过程。

答：产生式系统问题求解的基本过程为：

① 初始化综合数据库，把欲解决问题的已知事实送入综合数据库中。

② 检查规则库中是否存在尚未使用过的规则，若有则执行③；否则转⑦。

③ 检查规则库的未使用规则中是否存在有其前提可与综合数据库中已知事实相匹配的规则，若有则从中选择一个；否则转⑥。

④ 执行当前选中规则，并对该规则作上标记，把执行该规则后所得到的结论作为新的事实放入综合数据库；如果该规则的结论是一些操作，则执行这些操作。

⑤ 检查综合数据库中是否包含了该问题的解，若已包含，则说明已求出解，问题求解过程结束；否则，转②。

⑥ 当规则库中还有未使用规则，但均不能与综合数据库中的已有事实相匹配时，要求用户进一步提供关于该问题的已知事实，若能提供，则转②；否则，说明该问题无解，终止问题求解过程。

⑦ 若知识库中不再有未使用规则，也说明该问题无解，终止问题求解过程。

12、设个体域D?{1,2}，求公式G?(?x)(?y)P(x,y)在D上的解释，并指出每一种解释下公式

G的真值

解：谓词公式的解释主要是对公式中的个体常量、函数、谓词按如下规则赋值： （1） 为每一个个体常量指派D中的一个元素 （2） 为每个n元函数指派一个映射、

由于公式G中没有包含个体常量和函数，直接为谓词指派真值 如果指派真值如下表所示： P（1,1） T P（1,2） F P（2,1） T P（2,2） F 则公式G?(?x)(?y)P(x,y)根据上表的解释，其真值为T 但若指派真值如下表所示： P（1,1） T P（1,2） T P（2,1） F P（2,2） F 则公式G?(?x)(?y)P(x,y)根据上表的解释，其真值为F

13、 考虑下面的句子： （1）每个程序都存在BUG

（2）含有BUG的程序无法工作 （3）P是一个程序

问题：

（1） 采用一介谓词逻辑表示上述知识

（2） 使用归结原理和自然演绎推理两种方式证明P不能工作 解：（1） 定义谓词

BUG（X）——X 存在BUG Program（X）——X 是程序 Work（X）——X 能工作 事实及规则的表示

R1：(?x)(Program(x)?BUG(x)) R2：(?y)(BUG(x)??Work(x)) F1：Program(P) （2） A、

利用归结原理证明P不能工作

结论取反：Work(P)) （公式1） R1化简字句为：?Program(x)?BUG(x) （公式2） R2化简字句为：?BUG(y)??Work(y) （公式3） F1化简字句为：Program(P) （公式4） 归结过程如下：

公式（2）和公式（4）归结为：

BUG(P) 其中{Px} 公式（5）

公式（5）和公式（3）归结为：

?Work(P)其中{Py} 公式（6）

公式（6）和公式（1）归结为：

NIL 公式（7）

结论得证：P不能工作 B、 自然演绎证明P不能工作 过程如下：

已知Program(P)

规则R1：(?x)(Program(x)?BUG(x))

利用三段论可得：BUG(P)

利用规则R2：(?y)(BUG(x)??Work(x)) 利用三段论可得：?Work(P) 结论得证

14、按“师生框架”、“教师框架”、“学生框架”的形式写出一个框架系统的描述。

解：师生框架

Frame

Name：Unit（Last-name，First-name） Sex：Area（male，female） Default：male Age：Unit（Years）

Telephone：Home Unit（Number）

Mobile Unit（Number）

教师框架

Frame

AKO Major：Unit（Major-Name） Lectures：Unit（Course-Name） Field：Unit（Field-Name）

Project ：Area（National，Provincial，Other） Default：Provincial

Paper：Area（SCI，EI，Core，General） Default：Core

学生框架

Frame

AKO< Teachers-Students > Major：Unit（Major-Name） Classes：Unit（Classes-Name）

Degree：Area（doctor，mastor, bachelor） Default：bachelor

15、假设张被盗，公安局派出5个人去调查。案情分析时，贞察员A说：“赵与钱中至少有一个人作案”，贞察员B说：“钱与孙中至少有一个人作案”，贞察员C说：“孙与李中至少有一个人作案”，贞察员D说：“赵与孙中至少有一个人与此案无关”，贞察员E说：“钱与李中至少有一个人与此案无关”。如果这5个侦察员的话都是可信的，使用归结演绎推理求出谁是盗窃犯。 解：(1) 先定义谓词和常量

设C(x)表示x作案，Z表示赵，Q表示钱，S表示孙，L表示李 (2) 将已知事实用谓词公式表示出来

赵与钱中至少有一个人作案：C(Z)∨C(Q) 钱与孙中至少有一个人作案：C(Q)∨C(S) 孙与李中至少有一个人作案：C(S)∨C(L)

赵与孙中至少有一个人与此案无关：? (C (Z)∧C(S))，即 ?C (Z) ∨?C(S) 钱与李中至少有一个人与此案无关：? (C (Q)∧C(L))，即 ?C (Q) ∨?C(L) (3) 将所要求的问题用谓词公式表示出来，并与其否定取析取。 设作案者为u，则要求的结论是C(u)。将其与其否)取析取，得：

? C(u) ∨C(u)

(4) 对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：

C(Z)∨C(Q) ?C (Z) ∨?C(S)

C(Q)∨?C(S) C(Q)∨C(S)

?C(u)∨C(uC(Q) {Q/u} C(Q)

因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：

C(S)∨C(L) ?C (Q) ∨?C(L)

C(S)∨?C(Q) C(Q)∨C(S)

?C(u)∨C(uC(S) {S/u} C(S)

因此，孙也是盗窃犯。

16、用合适的方法表述Hanoi塔问题。在Ａ针上串有4个金片，小金片在大金片上面。现要求将Ａ针的金片全部移到Ｂ针上。移动操作要遵守下列规则：

（1）一次只能搬一个金片；

（2）不能将大金片放在小金片上； （3）可以利用C针

试采用问题归求解方法构造与或树，并写出操作过程及最少搬动次数。

解：可以采用与/或树表示法。设有编号分别为1、2、3的三个金片，1号比2号小，2号比三号小，有A、B、C三针，如题要把A针上的金片全部搬到B针上。

第一步：设四元组(i,j,k,l)表示问题的任一状态，用→表示状态的转化。i代表4号金片所在的针，j代表3号金片所在的针，k代表2号金片所在的针，l代表1号金片所在的针。则原问题可以表述为（A,A,A,A）→（B,B,B,B）

第二步：利用归约的方法，原问题可以分解为以下三个子问题。 （1）（A，A，A，A）→（A，C，C，C） （2）（A，C，C，C）→（B，C，C，C） （3）（B，C，C，C）→（B，B，B，B） 其中（1）又可以归约为

①（A，A，A，A）→（A，A，B，B）；

其中（A，A，A，A）→（A，A，A，C） （A，A，A，C）→（A，A，B，C） （A，A，B，C）→（A，A，B，B）

共三步

②（A，A，B，B）→（A，C，B，B）； 共一步 ③（A，C，B，B）→（A，C，C，C）

其中（A，C，B，B）→（A，C，B，A）

（A，C，B，A）→（A，C，C，A） （A，C，C，A）→（A，C，C，C） 共三步

（2）可以归约为：

④（B，C，C，C）→（B，C，A，A）； 其中（B，C，C，C）→（B，C，C，B） (B，C，C，B）→（B，C，A，B）

(B，C，A，B）→（B，C，A，A） 共三步

⑤（B，C，A，A）→（B，B，A，A）共一步； ⑥（B，B，A，A）→（B，B，B，B） 其中（B，B，A，A）→（B，B，A，C）

（B，B，A，C）→（B，B，B，C） （B，B，B，C）→（B，B，B，B）

共三步。综上所述：共搬运15次。

（A,A,A,A）→（B,B,B,B） （A,A,A,A）→（A,C,C,C） （A,C,C,C）→（B,C,C,C） （B,C,C,C）→（B,B,B,B） （A,A,A,A）→（A,A,B,B） （A,C,B,B）→（A,C,C,C） （A,A,B,B）→（A,C,B,B） （B,C,C,C）→（B,C,A,A） （B,B,A,A）→（B,B,B,B） （B,C,A,A）→（B,B,A,A） 17、先进专家系统具有哪些特点？

专家系统是一种具有大量专门知识和经验的智能程序系统，它能运用领域专家多年积累的经验和专门知识，模拟领域专家的思维过程，解决该领域中需要专家才能解决的复杂问题。先进专家系统是指在传统专家系统的基础上，引入一些新思想、新技术所产生的新型专家系统。先进专家系统的特性主要有以下几点 (1) 并行分布式处理功能 (2) 多专家协同工作 (3) 更强的自学习能力 (4) 更新的推理机制

(5) 自纠错和自完善能力 (6) 先进的智能接口

(7) 更多的先进技术被引入和融合

18、对于八数码问题，评价函数定义为：

f(x)?d(x)?W(x)

其中d(x)表示节点x在搜索树中的深度，W(x)表示节点x中不在目标状态中相应位置的数码个数。以此评价函数为评价标准进行启发式搜索，该搜索算法是否满足A*算法？为什么？并画出相应的状态空间搜索图。

解：在上面确定h(x)时，尽管并不知道h*(x)具体为多少，但采用单位代价时，通过对“不在位的目标状态中相应位置的数码个数”的估计，可以得到至少移动h(x)步才能狗到达目标，显然

h(x)?h*(x)。因此它满足A*算法的要求。所以以此为评价函数是A*算法。

本文来源：https://www.bwwdw.com/article/tm5o.html