人工智能课后习题答案.pdf

人工智能课后习题答案 第一章课后习题答案 说明:由于人工智能的很多题目都很灵活，以下解答仅供参考。第 1 题 答:1，综合数据库 定义三元组:(m,c,b)其中:，表示传教士在河左岸的人数。，表示野人在河左岸的认输。，b=1，表示船在左岸，b=0，表示船在右岸。2，规则集 规则集可以用两种方式表示，两种方法均可。第一种方法:按每次渡河的人数分别写出每一个规则，共(3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八种渡河的可能(其中(x y)表示 x 个传教士和 y 个野人上船渡河)，因此共有 16 个规则(从左岸到右岸、右岸到左岸各八个)。注意:这里没有(1 2)，因为该组合在船上的传教士人数少于野人人数。规则集如下:r1:IF(m,c,1)THEN(m-3,c,0)r2:IF(m,c,1)THEN(m,c-3,0)r3:IF(m,c,1)THEN(m-2,c-1,0)r4:IF(m,c,1)THEN(m-1,c-1,0)r5:IF(m,c,1)THEN(m-1,c,0)r6:IF(m,c,1)THEN(m,c-1,0)r7:IF(m,c,1)THEN(m-2,c,0)r8:IF(m,c,1)THEN(m,c-2,0)r9:IF(m,c,0)THEN(m+3,c,1)r10:IF(m,c,0)THEN(m,c+3,1)r11:IF(m,c,0)THEN(m+2,c+1,1)r12:IF(m,c,0)THEN(m+1,c+1,1)r13:IF(m,c,0)THEN(m+1,c,1)r14:IF(m,c,0)THEN(m,c+1,1)r15:IF(m,c,0)THEN(m+2,c,1)r16:IF(m,c,0)THEN(m,c+2,1)1 第二种方法:将规则集综合在一起，简化表示。规则集如下:r1:IF(m,c,1)and 0=j or i=0)THEN(m-i,c-j,0)r2:IF(m,c,0)and 0=j or i=0)THEN(m+i,c+j,1)3，初始状态:(5,5,1)4，结束状态:(0,0,0)第 2 题 答:1，综合数据库 定义两元组:(L5,L2)其中:0=L5=5，表示容量为 5 升的壶的当前水量。0=L2=2，表示容量为 2 升的壶的当前水量。2，规则集 r1:IF(L5,L2)THEN(5,L2)/*将 L5 灌满水*/r2:IF(L5,L2)THEN(L5,2)/*将 L2 灌满水*/r3:IF(L5,L2)THEN(0,L2)/*将 L5 水到光*/r4:IF(L5,L2)THEN(L5,0)/*将 L2 水到光*/r5:IF(L5,L2)and L5+L25 THEN(5,L5+L2-5)/*L2 到入 L5 中*/r7:IF(L5,L2)and L5+L25 THEN(L5+L2-2,2)/*L5 到入 L2 中*/3，初始状态:(5,0)4，结束条件:(x,1)，其中 x 表示不定。当然结束条件也可以写成:(0,1)第 3 题 答:1，综合数据库 定义三元组:(A,B,C)其中 A,B,C 分别表示三根立柱，均为表，表的元素为 1,N 之间的整数，表示N 个不同大小的盘子，数值小的数表示小盘子，数值大的数表示大盘子。表的第一个元素表示立柱最上面的柱子，其余类推。2，规则集 为了方便表示规则集，引入以下几个函数:first(L):取表的第一个元素，对于空表，first 得到一个很大的大于 N 的数值。tail(L):取表除了第一个元素以外，其余元素组成的表。cons(x,L):将 x 加入到表 L 的最前面。规则集:r1:IF(A,B,C)and(first(A)first(B)THEN(tail(A),cons(first(A),B),C)2 r2:IF(A,B,C)and(first(A)first(C)THEN(tail(A),B,cons(first(A),C)r3:IF(A,B,C)and(first(B)first(C)THEN(A,tail(B),cons(first(B),C)r4:IF(A,B,C)and(first(B)first(A)THEN(cons(first(B),A),tail(B),C)r5:IF(A,B,C)and(first(C)first(A)THEN(cons(first(C),A),B,tail(C)r6:IF(A,B,C)and(first(C)first(B)THEN(A,cons(first(C),B),tail(C)3，初始状态:(1，2，.，N)，()，()4，结束状态:()，()，(1，2，.，N)问题的状态规模:每一个盘子都有三中选择:在 A 上、或者在 B 上、或者在 C上，共 N 个盘子，所以共有种可能。即问题的状态规模为。第 4 题 答:1，综合数据库 定义 5 元组:(M,B,Box,On,H)其中:M:猴子的位置 B:香蕉的位置 Box:箱子的位置 On=0:猴子在地板上 On=1:猴子在箱子上 H=0:猴子没有抓到香蕉 H=1:猴子抓到了香蕉 2，规则集 r1:IF(x,y,z,0,0)THEN(w,y,z,0,0)猴子从 x 处走到 w 处 r2:IF(x,y,x,0,0)THEN(z,y,z,0,0)如果猴子和箱子在一起，猴子将箱子推到 z 处 r3:IF(x,y,x,0,0)THEN(x,y,x,1,0)如果猴子和箱子在一起，猴子爬到箱子上 r4:IF(x,y,x,1,0)THEN(x,y,x,0,0)如果猴子在箱子上，猴子从箱子上下来 r5:IF(x,x,x,1,0)THEN(x,x,x,1,1)如果箱子在香蕉处，猴子在箱子上，猴子摘到香蕉 其中 x,y,z,w 为变量 3，初始状态(c,a,b,0,0)4，结束状态(x1,x2,x3,x4,1)其中 x1,x4 为变量。第 5 题 答:1，综合数据库 定义四元组:(x,y,z,n)其中 x,y,x?0,1，1 表示钱币为正面，0 表示钱币为方面。n=0,1,2,3，表示当前状态是经过 n 次翻钱币得到的。3 2，规则库 r1:IF(x,y,z,n)THEN(x,y,z,n+1)r2:IF(x,y,z,n)THEN(x,y,z,n+1)r3:IF(x,y,z,n)THEN(x,y,z,n+1)其中x 表示对 x 取反。3，初始状态(1,1,0,0)4，结束状态(1,1,1,3)或者(0,0,0,3)第 6 题 提示:将十进制数分为整数部分和小数部分两部分。用四元组(a,b,c,d)表示综合数据库，其中 a,b 表示到目前为止还没有转换的十进制数的整数部分和小数部分，c,d 表示已经转换得到的二进制数的整数部分和小数部分。然后根据十进制数转换二进制数的原理，分别定义整数的转换规则和小数的转换规则，一次规则的执行，转换得到二进制数的一位。第 7 题 答:设规则 R 的逆用 R表示。由题意有 R 应用于 D 后，得到数据库 D，由可交换系统的性质，有:rule(D)rule(D)其中 rule(D)表示可应用于 D 的规则集合。由于 R是 R的逆，所以 R应用于 D后，得到数据库 D。同样由可交换系统的性质，有:rule(D)rule(D)综合上述两个式子，有 rule(D),rule(D)。第 8 题 答:说明一个产生式系统是可交换的，就是要证明该产生式系统满足可交换产生式系统的三条性质。(1)该产生式系统以整数的集合为综合数据库，其规则是将集合中的两个整数相乘后加入到数据库中。由于原来数据库是新数据库的子集，所以原来的规则在新数据库中均可以使用。所以满足可交换产生式系统的第一条性质。(2)该产生式系统以某个整数的子集的出现为目标条件，由于规则执行的结果只是向数据库中添加数据，如果原数据库中已经满足目标了，即出现了所需要的整数子集，规则的执行结果不会破坏该整数子集的出现，因此新的数据库仍然会满足目标条件。满足可交换产生式系统的第二个性质。(3)设 D 是该产生式系统的一个综合数据库。对 D 施以一个规则序列后，得到一个新的数据库 D。该规则序列中的有些规则有些是可以应用于 D 的，这些规则用 R1 表示。有些规则是不能应用于 D 的，这些规则用 R2 表示。由于 R1 中的规则可以直接应用与 D，所以 R1 4 中规则的应用与 R2 中规则的执行结果无关，也与,1 中其他的规则的执行无关。所以可以认为，先将 R1 中所有的规则对 D 应用，然后再按照原来的次序应用R2 中的规则。因此对于本题的情况，这样得到的综合数据库与 D是相同的。而由于 R1 中一条规则的执行与其他的规则无关，所以 R1 中规则的执行顺序不会影响到最终的结果。因此满足可交换产生式系统的第三个条件。因此这样一个产生式系统是一个可交换的产生式系统。第二章 第 1 题 答:为了方便起见，我们用(AB)()()这样的表表示一个状态。这样得到搜索图如下:第 2 题 提示:可定义 h 为:h,B 右边的 W 的数目 5 设 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;跳过了两个 W，此时:h(i)-h(j)=-2,C(i,j)=2;(11)B 向左 纵上所述，无论是哪一种情况，具有:h(i)-h(j)?C(i,j)且容易验证 h(t)=0，所以该 h 是单调的。由于 h 满足单调条件，所以也一定有h(n)?h*(n)，即满足 A*条件。第 3 题 答:定义 h1=n*k，其中 n 是还未走过的城市数，k 是还未走过的城市间距离的最小值。h2,，其中 n 是还未走过的城市数，k 是还未走过的城市间距离中 n 个最小的距离。显 i 然这两个 h 函数均满足 A*条件。第 4 题 提示:对于四皇后问题，如果放一个皇后的耗散值为 1 的话，则任何一个解的耗散值都是 4。因此如果 h 是对该耗散值的估计，是没有意义的。对于像四皇后这样的问题，启发函数应该是对找到解的可能性的评价。比如像课上讲到的，利用一个位置放皇后后，消去的对角线的长度来进行评价。第 5 题 答:定义 h1=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*的条件。6 下面我们来证明 h(n),M+C-2B 是满足 A*条件的。我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河 2 人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要摆渡次。其中分子上的,3表示剩下三个留待最后一次运过去。除以2是因为一个来回可以运过去 2 人，需要 个来回，而来回数不能是小数，需要向上取整，这个用符号表示。而乘以 1，则表示将剩下的 3 个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+1=M+C。综合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子表示为: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 值最小的节点扩展，当该节点是目标节点时，算法结束。并且由可采纳性定理，知道这时 A*找到了从初始节点到目标节点的最佳路径，即 f(t)=f*(s)。如果这时 OPEN 中存在 f(n)f*(s)的节点 n，由于f(n)f*(s)的节点，不会被 A*所扩展。所以如果从 OPEN 表中去掉 f(n)f*(s)的节点，不会影响 A*的可采纳性。而 F 是 f*(s)的上界范围，因此去掉 f(n)F 的节点也同样不会影响 A*的可采纳性。第 8 题 提示:对于 8 数码问题，逆向搜索和正向搜索是完全一样的，只是把目标状态和初始状态对调就可以了。第 9 题 提示:在搜索期间改善 h 函数，是一种动态改变 h 函数的方法。像改进的 A*算法中，对 NEST 中的节点按 g 值的大小选择待扩展的节点，相当于令这些节点的h,0，就是动态修改 h 函数的一种方法。由定理 6，当 h 满足单调条件时，A*所扩展的节点序列，其 f 是非递减的。对于任何节点 i，j，如果 j 是 i 的子节点，则有 f(i)?f(j)。利用该性质，我们可以提出另一种动态修改 h 函数的方法:f(j)=max(f(i),f(j)以 f(j)作为节点 j 的 f 值。f 值的改变，隐含了 h 值的改变。当 h 不满足单调条件时，经过这样修正后的 h 具有一定的单调性质，可以减少重复节点的可能性。第 10 题 提示:很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式，很多情 况下，也不一定能清晰的写成一个函数的形式。8 为了叙述方便，我们将两个相对的扇区称为相对扇区，图中阴影部分的扇区称为阴影扇区，非阴影部分的扇区称为非阴影扇区。由题意，在目标状态下，一个扇区的数字之和等于 12，一个相对扇区的数字之和等于 24，而一个阴影扇区或者非阴影扇区的数字之和为 48。为此，我们可以将目标进行分解，首先满足阴影扇区的数字之和为 48(这时非阴影部分的 o 数字和也一定为 48)。为了这个目标我们可以通过每次转动圆盘 45 实现。在第一个目标被满足的情况下，我们再考虑第二个目标:每一个相对扇区的数字和为24。在实现这个目标 o 的过程中，我们希望不破坏第一个目标。为此我们采用转动 90 的方式实现，这样即可以调整相对扇区的数字和，又不破坏第一个目标。在第二个目标实现之后，我们就可以实现最终目标:扇区内的数字和为 12。同样我们希望在实现这个目标的时候，不破坏前两个目标。o 为此我们采用转动 180 的方式实现。这样同样是即可以保证前两个目标不被破坏，又可以实现第三个目标。经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第一、第二个目标的实现，都能够实现第三个目标呢,有可能不一定。在这种情况下，就需要在发现第三个目标不能实现时，重新试探其他的第一、第二个目标。第三章 第三章课后习题答案 说明:由于人工智能的很多题目都很灵活，以下解答仅供参考。第 1 题 答:此题要求按照课中例题的方式，给出算法，以下是每个循环结束时的搜索图。上面这种做法比较简单，也可以如下做:9 10 第 2 题 答:从该搜索图可以看出，无论先走者选择哪个走步，后走者都可以走到标记为 A的节点，该节点只剩下一枚钱币，所以先走者必输。对于一般的具有 n 个钱币的情况，当 n,4m，1 时，后走者存在取胜策略。因为后走者可以根据先走者的走法，选择自己的走法，使得双方拿走的钱币数为 4，这样经过 m 个轮回后，共拿走了 4m 个钱币，只剩下了一枚钱币，而此时轮到先走者走棋。所以在这种情况下，后走者存在取胜的策略。对于钱币数不等于 4m，1 的情况，先走者可以根据实际的钱币数选择取走的钱币数，使得剩下的钱币数为 4m，1 个，此时先走者相当于 4m，1 个钱币时的后走者了。因此在这种情况下，先走者存在获胜的策略。第 3 题 答:11 第 4 题 答:略 第 5 题 答:略 第 6 题 答:略 第 7 题 答:略 第 8 题 答:略 12