人工智能复习题整理

1..神州大学和东方大学两校篮球队在东方大学进行一场比赛，结局的比分是85：89，用语义网络表示。

2.. 张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员A说“赵与钱中至少有一人作案”；侦察员B说“钱与孙中至少有一人作案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与孙中至少有一人与此案无关”；侦察员E说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。解：第一步：将5位侦察员的话表示成谓词公式，为此先定义谓词。

设谓词P(x)表示是作案者，所以根据题意：

A: P(zhao) ∨ P(qian) B: P(qian) ∨ P(sun)

C: P(sun) ∨ P(li) D: ﹁P(zhao) ∨﹁P(sun)

E: ﹁P(qian) ∨﹁P(li)

以上每个侦察员的话都是一个子句。

第二步：将待求解的问题表示成谓词。设y是盗窃犯，则问题的谓词公式为P(y)，将其否定并与ANSWER(y)做析取：

﹁P(y) ∨ ANSWER(y)

第三步：求前提条件及﹁P(y) ∨ ANSWER(y)的子句集，并将各子句列表如下：

（1）P(zhao) ∨ P(qian)

（2）P(qian) ∨ P(sun)

（3）P(sun) ∨ P(li)

（4）﹁P(zhao) ∨﹁P(sun)

（5）﹁P(qian) ∨﹁P(li)

（6）﹁P(y) ∨ ANSWER(y)

第四步：应用归结原理进行推理。

（7）P(qian) ∨﹁P(sun) (1)与(4)归结

（8）P(zhao) ∨﹁P(li) (1)与(5)归结

（9）P(qian) ∨﹁P(zhao) (2)与(4)归结

（10） P(sun) ∨﹁P(li) (2)与(5)归结

（11）﹁P(zhao) ∨ P(li) (3)与(4)归结

（12） P(sun) ∨﹁P(qian) (3)与(5)归结

（13） P(qian) (2)与(7)归结

（14） P(sun) (2)与(12)归结

（15） ANSWER(qian) (6)与(13)归结，σ={qian/y}

（16） ANSWER(sun) (6)与(14)归结, σ={sun/y}

所以，本题的盗窃犯是两个人：钱和孙。

3.任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter

的父亲是谁？

解：第一步：将已知条件用谓词公式表示出来，并化成子句集。那么，要先定义谓词。

（1）定义谓词：

设Father(x,y)表示x是y的父亲。

设Brother(x,y)表示x和y是兄弟。

（2）将已知事实用谓词公式表示出来：

F1: 任何兄弟都有同一个父亲。

???

( x)( y)( z)( Brother(x,y)∧Father(z,x)→Father(z,y))

F2: John和Peter是兄弟。

Brother(John, Peter)

F3: John的父亲是David。

Father(David, John)

（3）将它们化成子句集，得

S1={﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y), Brother(John, Peter), Father(David, John)}

第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER做析取。

设Peter的父亲是u，则有：Father(u, Peter)

将其否定与ANSWER做析取，得

G: ﹁Father(u, Peter) ∨ ANSWER(u)

第三步：将上述公式G化为子句集S2，并将S1和S2合并到S。

S2={﹁Father(u, Peter) ∨ ANSWER(u)}

S=S1∪S2

将S中各子句列出如下：

（1）﹁Brother(x,y)∨﹁Father(z,x)∨Father(z,y)

（2）Brother(John, Peter)

（3）Father(David, John)

（4）﹁Father(u, Peter) ∨ ANSWER(u)

第四步：应用归结原理进行归结。

（5）﹁Brother(John,y) ∨ Father(David,y)

（1）与（3）归结，σ={ David/z, John/x} （6）﹁Brother(John, Peter) ∨ ANSWER(David)

（4）与（5）归结，σ={ David/u, Peter/y} （7）ANSWER(David) （2）与（6）归结

第五步：得到了归结式ANSWER(David)，答案即在其中，所以u=David,即Peter

的父亲是David。

4.、滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下：

其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是：

（1）任意一个将牌可以移入相邻的空格，规定其耗散值为1；

（2）任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可）。对这个问题，定义一个启发函数h(n)，并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨别这个h(n)是否满足下界范围？在你的搜索树中，对所有的节点满足不满足单调限制？

提示：可定义h为：h＝B右边的W的数目

设j节点是i节点的子节点，则根据走法不同，h(i)-h(j)的值和C(i, j)分为如下几种情况：

（1）B或W走到了相邻的一个空格位置，此时：h(i)-h(j)=0, C(i,j)=1；

（2）W跳过了1或2个W，此时h(i)-h(j)=0, C(i,j)=1或2；

（3）W向右跳过了一个B（可能同时包含一个W），此时：h(i)-h(j)=-1, C(i,j)=1或2；

（4）W向右跳过了两个B，此时：h(i)-h(j)=-2, C(i,j)=2；

（5）W向左跳过了一个B（可能同时包含一个W），此时：h(i)-h(j)=1, C(i,j)=1或2；

（6）W向左跳过了两个B，此时：h(i)-h(j)=2, C(i,j)=2；

（7）B跳过了1或2个B，此时h(i)-h(j)=0, C(i,j)=1或2；

（8）B向右跳过了一个W（可能同时包含一个B），此时：h(i)-h(j)=1, C(i,j)=1或2；

（9）B向右跳过了两个W，此时：h(i)-h(j)=2, C(i,j)=2；

（10）B向左跳过了一个W（可能同时包含一个B），此时：h(i)-h(j)=-1, C(i,j)=1或2；

（11）B向左跳过了两个W，此时：h(i)-h(j)=-2, C(i,j)=2；纵上所述，无论是哪一种情况，具有: h(i)-h(j)≤C(i,j) 且容易验证h(t)=0，所以该h是单调的。由于h满足单调条件，所以也一定有h(n)≤h*(n)，即满足A*条件。

第3