人工智能课后答案

1、第一章课后习题 1、对N = 5、k F ( F f*(s)，试说明为什么算 法A*仍然是可采纳的。 x) P ( x) A Q (A) V Q (B) T (二 x) P (x )A Q (x) 7、以归结反演法证明公式(匸x) P( x)是P (Ai)V P (A2)的逻辑推论，然而， G x) P (X)的Skolem形即P (A)并非P (Ai)V P (A2)的逻辑推论，请加以证明。 (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; (

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*条件。 答：定义h1= n*k，其中n是还未走过的城市数，k是还未走过的城市间距离的最小值。 h2=*l ，其中n是还未走过的城市数，ki是还未走过的城市间距离中n个最小的距离。 显然这两个h函数均满足A*条件。 第4题 提示：对于四皇后问题，如果放一个皇后的耗散值为 1的话，则任何一个解的耗散值都 是4。因此如果h是对该耗散值的

3、估计，是没有意义的。对于像四皇后这样的问题，启发函 数应该是对找到解的可能性的评价。比如像课上讲到的， 利用一个位置放皇后后，消去的对 角线的长度来进行评价。 第5题 答：定义h仁M+C-2B，其中M , C分别是在河的左岸的传教士人数和野人人数。B= 1 表示船在左岸，B= 0表示船在右岸。 也可以定义h2=M+C。 h1是满足A*条件的，而h2不满足。 要说明h(n) = M+C不满足A*条件是很容易的，只需要给出一个反例就可以了。比如状态(1, 1, 1), h(n)=M+C=1+1=2,而实际上只要一次摆渡就可以达到目标状态，其最优路径的耗散值为 1。所以不满足A*的条件。 F面我们来

4、证明 h(n) = M+C-2B是满足A*条件的。 也就是说，船一次可 我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件, 以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2 人，而船仍然在左岸。而最后剩下的三个人， 则可以一次将他们全部从左岸运到右岸。 所以， 在不考虑限制条件的情况下，也至少需要摆渡 X2 + 1 2 次。其中分子上的 -3 表示剩下三个留待最后一次运过去。除以2是因为一个来回可以运过去 2人，需要 2个来回，而”来回数不能是小数，需要向上取整，这个用符号r 1表示。而乘以 2是因为一个来回相当于两次摆渡，所以要乘以 2。而最后的+

5、1，则表示将剩下的3个 运过去，需要一次摆渡。 化简有: M十 C-3 2 x 2 *1 i+1 =+ M + C - 2 2 再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此 对于状态(M , C, 0)来说，其所需要的最少摆渡数，相当于船在左岸时状态(M+1 , C, 1)或(M , C+1, 1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需 要的最少摆渡数为：(M+C+1)-2+1。其中(M+C+1)的 + 1表示送船回到左岸的那个人，而最 后边的+ 1，表示送船到左岸时的一次摆渡。 化简有：(M+C+1)-2+ 仁M+C。 综

6、合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子表示为：M+C-2B。 其中B=1表示船在左岸，B=0表示船在右岸。由于该摆渡次数是在不考虑限制条件下，推 出的最少所需要的摆渡次数。因此，当有限制条件时，最优的摆渡次数只能大于等于该摆渡 次数。所以该启发函数 h是满足A*条件的。 第6题 答：题目的另一个说法是：当A*结束时，OPEN表中任何一个具有f(n)f*(s)的节点都被 扩展了。 用反证法证明。 假设在A*结束的时候，OPEN表中有一个节点 n没有被扩展，且f(n)f*(s)。A*算法每次从 OPEN表中取出f值最小的节点扩展，当该节点是目标节点时，算法结束。并且由可采纳

7、性 定理，知道这时 A*找到了从初始节点到目标节点的最佳路径，即f(t)=f*(s)。如果这时OPEN 中存在f(n)f*(s)的节点n,由于f(n)f(t)，则这时A*算法应选择n扩展，而不是目标 t，与 A* 已经结束矛盾。 第7题 答：因为A*选作扩展的任何一个节点n,均有f(n) f*(s)的节点，不会 被A*所扩展。所以如果从OPEN表中去掉f(n)f*(s)的节点，不会影响A*的可采纳性。而F 是f*(s)的上界范围，因此去掉f(n)F的节点也同样不会影响A*的可采纳性。 第8题 提示： 对于 8 数码问题, 逆向搜索和正向搜索是完全一样的, 只是把目标状态和初始状 态对调就可以了

8、。 第9题 提示：在搜索期间改善 h函数，是一种动态改变 h函数的方法。像改进的 A*算法中， 对NEST中的节点按g值的大小选择待扩展的节点， 相当于令这些节点的 h= 0,就是动态修 改 h 函数的一种方法。 由定理6，当h满足单调条件时，A*所扩展的节点序列，其 f是非递减的。对于任何节点 i, j，如果j是i的子节点，则有f(i)用该性质，我们可以提出另一种动态修改h函数的 方法： f(j)=max(f(i), f(j) 以f(j)作为节点j的f值。f值的改变，隐含了 h值的改变。 当 h 不满足单调条件时,经过这样修正后的 h 具有一定的单调性质,可以减少重复节点的 可能性。 第10

9、题 提示：很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式，很多情 况下，也不一定能清晰的写成一个函数的形式。 为了叙述方便，我们将两个相对的扇区称为相对扇区，图中阴影部分的扇区称为阴影扇 区，非阴影部分的扇区称为非阴影扇区。由题意，在目标状态下，一个扇区的数字之和等于 12, 一个相对扇区的数字之和等于24,而一个阴影扇区或者非阴影扇区的数字之和为48。 为此，我们可以将目标进行分解，首先满足阴影扇区的数字之和为48 （这时非阴影部分的 数字和也一定为 48）。为了这个目标我们可以通过每次转动圆盘45。实现。在第一个目标 被满足的情况下，我们再考虑第二个目标：每一个相对扇区的数

10、字和为24。在实现这个目 标的过程中，我们希望不破坏第一个目标。为此我们采用转动90。的方式实现，这样即可以 调整相对扇区的数字和，又不破坏第一个目标。 在第二个目标实现之后， 我们就可以实现最 终目标：扇区内的数字和为 12。同样我们希望在实现这个目标的时候，不破坏前两个目标。 为此我们采用转动 180。的方式实现。这样同样是即可以保证前两个目标不被破坏，又可以 实现第三个目标。经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第 一、第二个目标的实现，都能够实现第三个目标呢有可能不一定。在这种情况下，就需要在 发现第三个目标不能实现时，重新试探其他的第一、第二个目标。 第三章课

11、后习题答案 说明：由于人工智能的很多题目都很灵活，以下解答仅供参考。 第1题 答：此题要求按照课中例题的方式，给出算法，以下是每个循环结束时的搜索图。 9 6) 从该搜索图可以看出，无论先走者选择哪个走步，后走者都可以走到标记为A的节点， 该节点只剩下一枚钱币，所以先走者必输。对于一般的具有n个钱币的情况，当n= 4Xm + 1时，后走者存在取胜策略。因为后走者可以根据先走者的走法，选择自己的走法，使得双 方拿走的钱币数为 4,这样经过m个轮回后，共拿走了 4Xm个钱币，只剩下了一枚钱币， 而此时轮到先走者走棋。所以在这种情况下，后走者存在取胜的策略。对于钱币数不等于 4Xm + 1的情况，先

12、走者可以根据实际的钱币数选择取走的钱币数，使得剩下的钱币数为 4Xm + 1个，此时先走者相当于 4 Xm+ 1个钱币时的后走者了。因此在这种情况下，先走者存在获 胜的策略。 答: 0 - 3 C- s S- 0 E- T 5 I 0 G-5 3 5 C 2-Z 0 C- E 5 (J (A)d(A x)o(/)v(AM)dJ (A)dl(AX (x)d(xA) () M)d A (x)dl(AQ)(xA) (A)d-l(Aa)A(x)d(xA) (x)d仪口) A(x)d(XA) (x)d(如 (x)d(x岛)(乙) (x)d A (x)d (x)d A (x)d(XA) (x)dJ (x)

13、dl(x) (L ):昜 3-2 - r-T- a t t o 3-1- iiii miiorniin rnnrn iin 宀o OA=)SO oA=)dOA E)s(eOA0-(cxl (CXIA=)S (cxl (cxlA=)d(cxlAro)s(CXIA 6)d -( (LA=)S( (LA=)d(e 50 (LAro)d _( (A=)S( (A=)d (Aro)s(e )0丄 (A=)s(A=)d(Aro)s(Aro)cn(A=)s(A=)d(e A)0(A 6)4 _( n)s ( n)d (Ax)s (X A)o 一 n)s ( n)d(Ax)s(A x)d一 n)s( n)d

14、(x A)o(Ax)d=A)(nB)(AA)(xB) _( n)s( n)d丄 0(A x)s(x )0丄 (A x)b(Ax)dD(A)(nB)(A(XB) _( n)s( n)d 0(A)s_(X A)0(nQQ)(AP)(XB) _(.n)s(n)d=(nD)0(Ax)s(xA)o n)s( n)d=A)(naa(Ax)s (X A)0丄 (A x)d D(A 日)(XT _( n)s( n)d =(n 甲 0(Ax)s (x A)o丄 (Ax)dD(A0)(x _(A Esf (A x)d一(AAKX 甲 0(；)sf (X A)O _(Asf (Ax)d一(AA)(X 甲 0(A k

15、)sf (X A)O(cxlz E)o(qro=)d -(N)d (Nro)o(q)d-sd) 0(z)d(zro)o(q g)d 丄 (zro)o(q)dwsd) a(z)d(z(Ax=)dw_(z)d(z(A)Gn(zx)o丄 _(Ax=)d(A)dD(A 旦(X 旦 asd (zx)o 丄(z _(Ax=)dsd一(A g (x)d)(x旦 asd(zx)o=zp (A)d 一(A A)(x)d)(x a(z)d(zx)o=ZEQ)(A)d=Af(x)dMXA) a(A)d(A)d=f(x)dMXA) a(A)d(Ax)o=AA(A)d=A#f(x)d)(XA) 答：设有两个置换 s仁a

16、/x和s2=x/y，合适公式P(x, y)。则： P(x, y)s1s2=P(a, x) P(x, y)s2s1=P(a, a) 二者不相等。所以说，置换的合成是不可交换的。 第3题 答：Ax, A./y, A/z, A/w, A/u 第4题 答：(1)P(f(x, x)，A), P(f(y，f(y，A)，A) 在合一时，f(x,x)要与f(y,f(y,a)进行合一，x置换成y后，y要与f(y,a)进行合一，出现 了嵌套的情况，所以不能进行合一。 (2) P( A)，P( x) 一个是谓词P, 个是P的反，不能合一。 (3) P( f( A)，x)，P( x，A) 在合一的过程中，x置换为f(

17、A)，而f(A)与A不能合一。 第5题 答：略 第6题 答：(1)x) P (x) F (A) A P (x) F ( B) 目标取反化子句集: (二X)P (x) TP (A) A P (x) TP ( B) (二x) P (x)V P (A) A P (x)V P (B) (ix)P (x)A P(A) V P (x)A P ( B) (x)P (x)A P(A) V P (x) A P (x)A P (A) V P ( B) (x)P ( x)A P(A)V P (x) A P (x)V P ( B) A P (A)V P( B) P (x)A P (A)V P ( x) A P (x)

18、V P ( B) A P (A)V P ( B) 得子句集： 1, P(x1) 2, P(A)V Px2 3, P(x3)V P(B) 4, P(A)V P(B) (2)(|z) Q (z) tp (z) t(二x) Q (x) tp (A) A Q (x) tp ( B) 目标取反化子句集: (Ez)Q(z) tP(z) Tx)Q(x) TP(AAQ(x) tP(B) C z)Q(z)V P(z) t(x)Q(x)V P(A) A Q(x) V P(B) C z)Q(z)V P(z)V (=x)Q(x) V P(A)A Q(x) V P(B) C z)( x)Q(z)V P(z)A Q(x)

19、A P(A)V Q(x) A P(B) C z)( x)Q(z)V P(z)A Q(x)A Q(x) V P(B)A P(A) V Q(x) A P(A) V P(B) 卜Q(z)V P(z)A Q(x)人Q(x) V P(B)人P(A)V Q(x) A P(A) V P(B) 得子句集： 1, Q(z)V P(z) 2, Q(x2) 3, Q(x3) V P(B) 4, P(A)V Q(x4) 5, P(A)V P(B) (3) (亠)(匸y) P (f (x)A Q ( f ( B) P (f (A)A P (y)A Q (y) 目标取反化子句集： Gx)Qy)P(f(x) A Q(f(B

20、) TP(f(AA P(y)A Q(y) Gx)Ly)P(f(x) A Q(f(B) V P(f(A) A P(y)A Q(y) (x)( y)P(f(x) A Q(f(B) A P(f(A) V P(y)V Q(y) P(f(x)A Q(f(B) A P(f(A) V P(y)V Q(y) 得子句集： 1, P(f(x1) 2, Q(f(B) 3, P(f(A) V P(y3) V Q(y3) (4)(nx)(|1y) P (x, y)( - ly)(匸x) P (x, y) 目标取反化子句集： (匸 x)C y)P(x, y) f( y)(二 x)P(x, y) (工x)(.y)P(x,

21、y) V C-y)rx)P(x, y) (工x)(. y)P(x, y) V(rv)(77u)P(u, v) (二x)(，y)P(x, y) A (二v)(，u)P(u, v) (匚x)( y)(匸v)( u)P(x, y) A P(u, v) P(a, y)A P(u, f(y) 得子句集: 1, P(a, y1) 2, P(u, f(y2) (5)(|X)P (x)A Q (A)V Q ( B) 宀(匸 x) P ( x)A Q (x) 目标取反化子句集： C x)P(x)A Q(A)V Q(B) t(x)P(x)A Q(x) (、x)P(x)A Q(A) V Q(B)V (二x)P(x)

22、A Q(x) ( Jx)P(x)A Q(A) V Q(B) A (x)P(x)V Q(x) ( Jx)P(x)A Q(A) V Q(B) A (y)卜P(y) V Q(y) C x)( y)P(x)A Q(A) V Q(B)A P(y)V Q(y) P(x)A Q(A) V Q(B) A P(y)V Q(y) 得子句集： 1, P(x) 2, Q(A)V Q(B) 3, P(y)V Q(y) 答：(1)将(二X)P ( X)取反化为子句： (二 x) P ( X) = ( X)P (X) 与条件P (A1)v P (A2)合在一起得子句集: P (X), P (A1)V P (A2) VP(

23、Ai ) VFC NIL 所以，公式(I X) P (x)是P (A1 )V P (A2)的逻辑推论。 (2) 对于(工x) P (x)的Skolem形，即P (A),取反后为P (A),与条件P (A1) V P (A2)合在一起得子句集： P (A) , P (A1)V P (A2) 该子句集不能进行归结，故P (A)不是P ( A1)V P (A2)的逻辑推论。 第8题 答：该问题用谓词公式描述如下： 已知： (1) ( x)Food(x) tLike(John, x) (2) Food(Apple) (3) C x)C y)Eat(y, x)A Kill(x, y) t Food(x)

24、 (4) Eat(Bill, Pea nut) A Kill(Pe nut, Bill) (5) x)Eat(Bill, x) tEat(Sue, x) 目标 1 : Like(Joh n, Pea nut) 目标 2 : x)Food(x) A Eat(Sue, x) 已知条件化子句集： (1) (I x)Food(x) tLike(John, x) =(hx)Food(x) V Like(John, x) = Food(x)V Like(John, x) (2) Food(Apple) (3) (I x)C y)Eat(y, x)A Kill(x, y) tFood(x) =C x)(，y

25、)Eat(y, x) A Kill(x, y) V Food(x) =C x)(，y)Eat(y, x) V Kill(x, y) V Food(x) = Eat(y, x)V Kill(x, y) V Food(x) (4) Eat(Bill, Pea nut) A Kill(Pe nut, Bill) = Eat(Bill, Pea nut), Kill(Pe nut, Bill) (5) x)Eat(Bill, x) tEat(Sue, x) =( x)Eat(Bill, x)V Eat(Sue, x) = Eat(Bill, x)V Eat(Sue, x) 目标1取反化子句集： Lik

26、e(Joh n, Pea nut) 目标2取反化子句集： (匸x)Food(x) A Eat(Sue, x) =C x)Food(x) V Eat(Sue, x) = Food(x)V Eat(Sue, x) 对于目标1，经变量换名后，得子句集: Food(x1)V Like(Joh n, x1), Food(Apple), Eat(y2, x2)V Kill(x2, y2) V Food(x2), Eat(Bill, Pea nut), Kill(Pe nut, Bill), Eat(Bill, x3) V Eat(Sue, x3), Like(Joh n, Pea nut)归结树如下： 对

27、于目标2，经变量换名后，得子句集： Food(x1)V Like(Joh n, x1), Food(Apple)，Eat(y2, x2)V Kill(x2, y2) V Food(x2)，Eat(Bill, Pea nut), Kill(Penut, Bill), Eat(Bill, x3) V Eat(Sue, x3), Food(x)V Eat(Sue, x)归结树如下： 修改证明树如下: 得到解答为：Food(Pea nut) A Eat(Sue, Pea nut) 答：该归结过程存在错误。 其原因是由于不同的子句用了相同的变量名引起的。如上图中A、 B两个子句的归结，两个子句中的y应该

28、是不同的变量，在归结时，如果用不同的变量分别 表示，就不会出现这样的问题了。比如B中的y用y1代替，则归结结果如下： 第10题 答：化子句集: (.u) LAST (cons (u, NIL), u) = LAST ( cons ( u, NIL), u) (-x)(y)(| - |z)( LAST (y, z) LAST(cons (x, y), z) =(hx)( y)( . z)( LAST(y, z)V LAST(cons (x, y), = LAST (y, z)V LAST (cons (x, y), z) 目标取反： (二 v) LAST (cons (2, co ns (1,

29、NIL), v) =CJv) LAST (cons (2, cons (1, NIL), v) = LAST (cons (2, cons (1, NIL), v) 经变量换名后，得子句集： LAST (cons ( u, NIL), u) , LAST ( y, z)V LAST (cons (x, y), 归结树如下: z) z) , LAST(cons (2, cons (1, NIL), v) 修改证明树: 得到解答：LAST(cons(2 cons(1, NIL), 1)，表 cons(2, cons(1, NIL)的最后一个元素为 1。 通过以上归结过程， 我们可以看出，该方法求解

30、长表的最后一个元素的方法是，每次将 长表去掉第一个元素，直到最后得到了只有一个元素的表，该元素就是长表的最后一个元素。 第11题 答：略 第12题 答：我们用Skier(x)表示x是滑雪运动员，Alpinist(x)表示x是登山运动员，Alpine(x)表示x是 Alpine俱乐部的成员。 问题用谓词公式表示如下: 已知: (1) Alp in e(To ny) (2) Alpi ne(Mike) Alp in e(Joh n) (4) ( x)Alpine(x) t SAp(x)st(x) (5) ( x)Alpinist(x) t Like(x, Rain) (6) ( x)Like(x,

31、 Snow) t Skier(x) (7) ( x)Like(Tony, x) t Like(Mike, x) (8) ( x)Like(Tony, x) t Like(Mike, x) (9) Like(Tony, Snow) (10) Like(Tony, Rain) 目标：(vx)Alpine(x) A Alpinist(x) A Skier(x) 化子句集： (1) Alpine(Tony) (2) Alpine(Mike) (3) Alpine(John) (x)Alpine(x)t SkAp(x)st(x) = ( x)Alpine(x) V Skier(x) V Alpinist

32、(x) =Alpine(x) V Skier(x) V Alpinist(x) (5) ( x)Alpinist(x) t LiRkeai(nx), = ( x)Alpinist(x) V Like(x, Rain) =Alpinist(x)V Like(x, Rain) (6) ( x)Like(x, Snow)t Skier(x) = ( x)LikeV(x,SSnkoiwer)(x) = Like(x, Snow)V Skier(x) (7) ( x)Like(Tony, x) t Like(Mike,x) = ( x)Like(Tony, x)V Like(Mike, x) =Like

33、(Tony, x)V Like(Mike, x) (8) ( x)Like(Tony, x) t Like(Mike, x) = ( x)Like(Tony, x)V Like(Mike, x) = Like(Tony, x)V Like(Mike, x) (9) Like(Tony, Snow) (10) Like(Tony, Rain) 目标取反： (vx)Alpine(x)A Alpinist(x)A Skier(x) = ( x)Alpine(x)V Alpinist(x)V Skier(x) =Alpine(x) V Alpinist(x) V Skier(x) 经变量换名后，得到子句集： Alpine(Tony)