《人工智能与专家系统》课后习题部分答案
第1章
1.1 何谓人工智能?人类智能主要包括那些能力?
1.2 知识工程是在什么背景下提出的?知识工程对人工智能的发展有何重要作用?
1.4 人工智能有哪几个主要学派?各学派的基本理论框架和研究方法有何不同?
1.6 人工智能主要的研究应用领域有哪些?
第2章
2.4 请用相应的谓词公式表示下述语句:
⑴ 有的人喜欢足球,有的人喜欢排球,有的人既喜欢足球又喜欢排球。
MAN(x): x是人 LIKE(x,y): x喜欢y
(
x) (MAN(x)∧LIKE(x, Football)) ∨(
x) (MAN(x)∧LIKE(x, Volleytball))
∨(
x) (MAN(x)∧LIKE(x, Football)∧LIKE(x, Volleytball))
⑵ 不是每一个人都喜欢游泳。
MAN(x): x是人 LIKE(x,y): x喜欢y
?(
x) (MAN(x)→LIKE(x, Swimming) 或者
(
x) (MAN(x)∧?LIKE(x, Swimming))
⑶ 如果没有利息,那么就没有人去储蓄钱。
S(x, y): x储蓄 y M(y): y是钱 I (x): x是利息 MAN(x): x是人
(?(
x) I (x))→(
x)(
y)(MAN(x)∧M(y)→ ?S(x, y))
⑷ 对于所有的x和y,如果x是y的父亲,y是z的父亲,那么x是z的祖父。
FATHER(x,y): x是y的父亲 GRANDPA(x,y): x是y的祖父
(
x)(
y)( FATHER(x,y)∧(
z) FATHER(y,z))→GRANDPA(x,z))
⑸ 对于所有的x和y , 若x是y的孩子,那么y是x的父母。
CHILDE(x,y) : x是y的孩子 PARENT(x,y): x是y的父母
(
x)(
y)( CHILDE(x,y)→PARENT(y,x))
⑹ 登高望远。
CLIMBHIGH(x): x登的高 SEEFAR(x): x望的远
(
x)(CLIMBHIGH(x)→SEEFAR(x))
⑺ 响鼓不用重锤。
P(x): x是鼓 M(x): x是响的 Q(x, y): x使用y N (y): y是锤子 H(y):是重的
(
x)(
y) ( P(x)∧M(x) →?Q (x, y)∧N (y)∧H(y))
⑻ 如果b>a>0 和c>d>0 ,则有 (b *(a+c) / d)>b 。
GREATER(x,y): x大于y f(x): b*(a+c)/d
(GREATER(b, a)∧GREATER(a,0)∧GREATER(b,0)∧GREATER(c,d)
∧GREATER(c,0)∧GREATER(d,0))→GREATER(f(x),b)
2.10 有下述猴子摘香蕉问题:在一个房间的地板上有一只猴子和一个箱子,天花板下挂有一串香蕉,猴子的水平位置为a,箱子的水平位置为b,香蕉的水平位置为c,猴子只有爬到箱子上才能摘到香蕉。猴子被允许有以下4种行为:在地板上行走:在地板上推动箱子:爬到箱子上:摘香蕉。为了规划处猴子摘香蕉的
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
,请把猴子的4种行为表示为4条产生式规则。
解:R1: if 猴子离开a, then 猴子在地板上行走
R2: if 猴子离开a and 箱子离开b, then 猴子推动箱子
R3: if 猴子位置在箱子上, then 猴子爬到箱子上
R4: if 猴子到达c, then 猴子摘香蕉
用四元组P(x,y,z,w)来表示某一时刻猴子,香蕉,箱子的状态
x表示猴子的水平位置 y表示箱子的水平位置
z:z=0时,表示猴子在箱子上面;z=1时,猴子不在箱子上面
w:w=0时,表示猴子没有拿到香蕉;w=1时,猴子拿到香蕉
Move(m):表示猴子在地板上行走
Push(m):表示猴子推动箱子
Stand(m):表示猴子爬到箱子上
Pick(m):表示猴子摘香蕉
P(b,b,1,0) → move(m)
P(c,c,1,0) → push(m)
P(c,c,0,0) → stand(m)
P(c,c,0,1) → pick(m)
2.11 有下述传教士与野人问题:有3名传教士和3名野人来到一条河的左岸,欲乘一条船渡河到右岸,该船的最大负载能力为2人,传教士与野人均可撑船。在任何时候,不论是在右岸还是左岸,如果野人人数超过传教士人数,那么,野人就会吃掉传教士。为了规划出一个渡河方案,把6个人都安全地渡过河去,请用产生式表示法表示求解该问题的所有规划。
解:(1) 综合数据库: 用三元组表示, 即: (ML, CL, BL), 其中0≤ML , CL≤3, BL∈{0, 1}
其中M、C分别代表某一岸上传教士与野人的数目, B=1表示船在这一岸, B=0则表示船不在。 此时问题述简化为:(3, 3, 1) → (0, 0, 0)。
对于N=3的M-C问题,状态空间的总数为4×4×2=32,根据约束条件的要求,可以看出只有20个合法状态。再进一步分析后,又发现有4个合法状态实际上是不可能达到的。因此实际的问题空间仅有16种状态可符合要求,其它的状态不符合要求。下表列出分析的结果:
(ML,CL,BL)
(ML,CL,BL)
(0 0 1)达不到
(0 0 0)
(0 1 1)
(0 1 0)
(0 2 1)
(0 2 0)
(0 3 1)
(0 3 0 ) 达不到
(1 0 1)不合法
(1 0 0)不合法
(1 1 1)
(1 1 0)
(1 2 1) 不合法
(1 2 0) 不合法
(1 3 1) 不合法
(1 3 0) 不合法
(2 0 1) 不合法
(2 0 0) 不合法
(2 1 1) 不合法
(2 1 0) 不合法
(2 2 1)
(2 2 0)
(2 3 1) 不合法
(2 3 0 ) 不合法
(3 0 1) 达不到
(3 0 0)
(3 1 1)
(3 1 0)
(3 2 1)
(3 2 0)
(3 3 1)
(3 3 0) 达不到
(2) 规则集合:
由摆渡操作组成。该问题主要有两种操作: pmc操作(规定为从左岸划向右岸)和qmc操作(从右岸划向左岸)。每次摆渡操作, 船上人数有五种组合, 因而组成有10条规则的集合。下面定义的规则前5条为pmc操作(从左岸划向右岸), 后5条为 qmc操作(从右岸划向左岸)。
R1: if (ML, CL, BL=1) then (ML-1, CL, BL-1); (p10操作)
R2: if (ML, CL, BL=1) then (ML, CL-1, BL-1); (p01操作)
R3: if (ML, CL, BL=1) then (ML-1, CL-1, BL-1); (p11操作)
R4: if (ML, CL, BL=1) then (ML-2, CL, BL-1); (p20操作)
R5: if (ML, CL, BL=1) then (ML, CL-2, BL-1); (p02操作)
R6: if (ML, CL, BL=0) then (ML+1, CL, BL+1); (q10操作)
R7: if (ML, CL, BL=0) then (ML, CL+1, BL+1); (q01操作)
R8: if (ML, CL, BL=0) then (ML+1, CL+1, BL+1); (q11操作)
R9: if (ML, CL, BL=0) then (ML+2, CL, BL+1); (q20操作)
R10: if (ML, CL, BL=0) then (ML, CL+2, BL+1); (q02操作)
(3) 初始和目标状态: 即 (3, 3, 1)和(0, 0, 0)。
建立了产生式系统描述之后, 就可以通过控制策略, 对状态空间进行搜索, 求得一个摆渡操作序列, 使其实现目标状态。
状态空间图是一个有向图, 其节点可表示问题的各种状态(综合数据库), 节点之间的弧线代表一些操作(产生式规则), 它们可把一种状态导向另一种状态。这样建立起来的状态空间图,描述了问题所有可能出现的状态及状态和操作之间的关系, 因而可以较直观地看出问题的解路径及性质。
实际上只有问题空间规模较小的问题才可能作出状态空间图。 由于每个摆渡操作都有对应的逆操作, 即pmc对应qmc, 所以该图也可表示成具有双向弧的形式。
从状态空间图看出解序列相当之多, 但最短解序列只有4个, 例如:
(p11、q10、p02、q01、p20、q11、p20、q01、p02、q01、p02)、
(p11、q10、p02、q01、p02、q11、p20、q01、p02、q10、p11)、
(p02、q01、p02、q01、p20、q11、p20、q01、p02、q01、p02)、
(p02、q01、p02、q01、p20、q11、p20、q01、p02、q10、p11),
均由11次摆渡操作构成。若给定其中任意两个状态分别作为初始和目标状态, 就立即可找出对应的解序列来。在一般情况下, 求解过程就是对状态空间搜索出一条解路径的过程。
以上这个例子说明了建立产生式系统描述的过程, 这也就是所谓问题的表示。对问题表示的好坏, 往往对求解过程的效率有很大影响。一种较好的表示法会简化状态空间和规则集表示。
其中的一条解路径为:
(3 3 1)→(3 1 0) →(3 2 1) →(3 0 0) →(3 1 1) →(1 1 0) →(2 2 1) →(0 2 0) →(0 3 1)
→(0 1 0) → (0 2 1) → (0 0 0)
用语句叙述的解路径(即过河方案)如下:
(1) 初始状态: 3个传教士、3个野人和船均在左岸;
(2) 2个野人由左岸过河到右岸;
(3) 1个野人划船返回左岸;
(4) 2个野人(包括返回的那个)由左岸过河到右岸;
(5) 1个野人划船返回左岸;
(6) 2个传教士由左岸过河到右岸;
(7) 1个传教士和一个野人返回左岸;
(8) 两个传教士(包括返回的那个)由左岸过河到右岸;
(9) 1个野人返回左岸;
(10) 2个野人由左岸过河到右岸;
(11) 1野人返回左岸;
(12) 2个野人由左岸过河到右岸, 至此, 传教士与野人全部过河, 此时3个传教士、3个野人和船全在右岸。
2.13 何谓框架知识表示?给出框架的一般表示形式。
2.16 建立一个“学生”框架网络,其中,至少有“学生基本情况”、“学生课程学习情况”和“学生奖惩情况”三个框架描述。
(略) 参照P31 例题2.6
2.17(1)与会者有男、有女,有的年老、有的年轻。
人
(2)李明是图灵电脑公司的经理,他住在江滨路102号,今年38岁。
年龄
(3)大门前的这棵树从春天到秋天都开花。
结束于
(4) 计算机系的每个学生都学习“人工智能原理” ,它是计算机专业的一门主干课程。
说明:
GS是一个概念结点,它代表具有全程量化的一般事件。
g是一个实例结点,代表GS中的一个具体例子。
S是一个全称变量,表示任意一个学生。
l是一个存在变量,代表某一次学习。
s, l之间的联系构成了一个子空间。
2.19 简述语义网络系统求解问题的基本过程。
2.25 简述面向对象表示的主要特点。
1. 封装性 2. 模块性 3. 继承性 4. 易维护性
第3章
3.2 正向推理流程图:
形成可用知识集
3.3 反向推理流程图:
Y
失败退出
3.10(2)F={P(f(x),b),P(y,z)}
解:①令σ0=ε,F0=F,因F0中含有两个表达式,所以σ0不是最一般合一。
②差异集D0={f(x),y}。
③σ1 =σ0○{f(x)/y}={f(x)/y}。
F1=F0{f(x)/y}={P(f(x),b),P(f(x),z)}。
④差异集D1={b,z}。
⑤σ2 =σ1○{b/z}={f(x)/y, b/z}。
F2=F1{ b/z }={P(f(x), b)}。
因为F2中只含有一个表达式,所以σ2={f(x)/y, b/z}就是最一般合一;
即最一般合一为{ f(x)/y, b/z }。
(4)F={P(f (y), y, x), P(x,f (a),f (b))}
解:①令σ0=ε,F0=F,因F0中含有两个表达式,所以σ0不是最一般合一。
②差异集D0={f(y),x}
③σ1 =σ0○{f(y)/x}={f(y)/x}
F1=F0{f(y)/x}={P(f(y),y,f(y)),P(f(y),f(a),f(b))}。
④差异集D1={y,f(a)}。
⑤σ2 =σ1○{f(a)/y }={f(y)/x, f(a)/ y }。
F2=F1{ f(a)/y }={P(f(f(a)), f(a), f(f(a))) ,P(f(f(a)), f(a),f(b))}。
⑥差异集D2={f(f(a)) ,f(b)}。
⑦σ3 =σ2○{f(a)/b}={f(y)/x, y/ f(a) , f(a)/b}。
F3=F2{ f(a)/ b }={P(f(f(a)), f(a),f(f(a)))}。
因为F3中只含有一个表达式,所以σ3={f(y)/x, f(a) / y, f(a)/b}就是最一般合一,
即最一般合一为{f(y)/x , f(a)/y , f(a)/b}。
3.11 (2)( x) (y)(P(x,y) →Q(x,y))
应用等价关系得: ( x) (y)( P(x,y) ∨Q(x,y))
消去全称量词得:P(x,y) ∨Q(x,y)
(4) ( x) (y) ( z)( (P(x,y) →Q(x,y)∨R(x,z))
应用等价关系得:( x) (y) ( z) ( P(x,y) ∨(Q(x,y) ∨R(x,z)) )
消去存在量词得:( x) (y) ( P(x,y) ∨(Q(x,y) ∨R(x, f(x,y)))
消去全称量词得:P(x,y) ∨(Q(x,y) ∨R(x,f(x,y)))
3.14解:
(1)首先定义谓词:
P(x): 表示x被公司录用
(2)把已知前提及待求解的问题表示成谓词公式:
F1:( x)P(x):三人中至少录用一人
F2:(P(A)∧P(B)) →P(C): 如果录用A而不录用B,则一定录用C
F3: P(B)→P(C):如果录用B,则一定录用C
G:P(C)
(3)将F1、F2、F3化为子句集:
⑴P(z)
⑵ P(A)∨P(B)∨P(C)
⑶ P(B)∨P(C)
⑷ P(C)
(4)应用归结原理进行归结:
⑸P(B)∨P(C) :由⑴与⑵归结 {A\z}
⑹P(C ) :由⑶与⑸归结
⑺NIL :由⑷与⑹归结
所以G是F1、F2、F3的逻辑结论,即公司一定录用C。
3.19解:
(1)首先定义谓词:
R(x): 表示x作案
(2)把已知前提及待求解的问题表示成谓词公式:
F1:R(Z)∨R(Q):赵与钱至少有一人作案
F2:R(Q)∨R(S):钱与孙至少一人作案
F3:R(S)∨R(L):孙与李至少一人作案
F4:R(Z)∨R(S):赵与孙中至少有一人与此案无关
F5:R(Q)∨R(L):钱与李中至少有一人与此案无关
G: ( x)R(x) ∨ANSWER(x):目标否定
(3)将上述公式化为子句集:
⑴R(Z)∨R(Q)
⑵R(Q)∨R(S)
⑶R(S)∨R(L)
⑷R(Z)∨R(S)
⑸R(Q)∨R(L)
⑹R(u)∨ANSWER(u)
(4)对上述公式进行归结:
⑺R(Q)∨R(S) ⑴⑷归结
⑻R(Q) ⑵⑺归结
⑼R(S) ∨R(Q) ⑶⑸归结
⑽R(S) ⑻⑼归结
⑾ANSWER(S) ⑹⑽归结 {S/u}
⑿ANSWER(Q) ⑹⑻归结 {Q/z}
至此,可以得出结论盗窃犯是孙和钱。
3.20解:
(1)首先定义谓词:
EASY(x):表示X是较容易的课程。
LIKE(x,y):表示X是Y喜欢的课程。
SUB(x,y):表示X是Y系的一门课程。
(2)把已知前提及待求解的问题表示成谓词公式:
F1:( x) (EASY(x)→LIKE(Li,x))
F2: EASY(Engineer)
F3: ( x) (SUB(x,PR)→EASY(x))
F4: SUB(PR150,PR)
G: ( x) LIKE(Li,x)∨ANSWER(z)
(3)将上述公式化为子句集:
⑴ EASY(x)∨LIKE(Li,x)
⑵ EASY(Engineer)
⑶ SUB(x,PR)∨EASY(x)
⑷SUB(PR150,PR)
⑸ LIKE(Li,z)∨ANSWER(z)
(4)对上述公式进行归结:
⑹ SUB(x,PR)∨LIKE(Li,x) ⑴⑶归结
⑺ LIKE(Li, PR150) ⑷⑹归结 { PR150/x}
⑻ANSWER(PR150) ⑸⑺归结 { PR150/z}
至此,可以得出结论小李喜欢PR150这门课程。
第4章
4.14解: 评价函数f(x)= d(x) + h(x)
其中: ①h(x)为节点x的状态Sx 与目标节点状态Sg 的棋局不相同的棋子数。
②d(x)为节点x的深度。
规定规则为空格移动(走步规则), 规则选取顺序为: 左(
)、上(
)、右(
)、下(
)。控制策略为: 选取评价函数值最小者进行扩展(往下搜索)。则其搜索的状态空间图如下:
则路径为:S(4) →B(4) →E(5) →I(5) →K(5) →L(5)
4.12 应用宽度优先搜索求解重排九宫问题。问题的初始状态S0和目标状态Sg分别为:
解:解的路径是:S0→空格上移→空格上移→空格上移→空格上移→空格上移→Sg
4.13应用有界深度优先搜索求解重排九宫问题。设搜索深度界限d m=5. 问题的初始状态S0和目标状态Sg分别为:
A
4.19解:
(1)深度优先搜索:
A →C →D →E →B →A ,代价为34。
昆明
(2)代价树宽度优先搜索:(略)
4.20解:
西安→北京 →上海 →昆明 →广州,代价为375
4.22 设有下列农夫过河问题:农夫、狐狸、山羊和白菜都在一条河的左岸,只有农夫可撑船,要将狐狸、山羊和白菜都渡河到右岸去。但是,农夫每次撑船过河时,船上至多只能载狐狸、或者载山羊、或者载白菜。若农夫不在时,则狐狸会吃掉山羊、山羊会吃掉白菜。请选择状态空间方法中的一个合适的搜索方法规划出一个渡河方案,使农夫能把狐狸、山羊和白菜都带过河去。画出搜索树,并给出问题的解。
提示: 用4元组S=(f, x, g, c)表示状态,其中变元f, x, g, c分别表示农夫、狐狸、山羊和白菜在状态S下所在的河岸。若其值为0,则表示在左岸;若其值为1,则表示在右岸。
4.24解:(1)按和代价法:h(B)=7;h(C)=3;h(A)=21
t2
解树为:
(2)按最大代价法:h(B)=5;h(C)=2;h(A)=10
t2
解树为:
3
4.27(1)计算各节点的倒推值(红色标识)
(2)进行α-β剪枝