搜索
1第一章课后习题答案第1题答：1，综合数据库定义三元组：（m,c,b）其中：，表示传教士在河左岸的人数。，表示野人在河左岸的认输。，b=1，表示船在左岸，b=0，表示船在右岸。2，规则集规则集可以用两种方式表示，两种方法均可。第一种方法：按每次渡河的人数分别写出每一个规则，共(30)、(03)、(21)、(11)、(10)、(01)、(20)、(02)八种渡河的可能（其中(xy)表示x个传教士和y个野人上船渡河），因此共有16个规则（从左岸到右岸、右岸到左岸各八个）。注意：这里没有(12)，因为该组合在船上的传教士人数少于野人人数。规则集如下：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)第二种方法：将规则集综合在一起，简化表示。规则集如下：r1：IF(m,c,1)and0i+j〈=3and(i=jori=0)THEN(m-i,c-j,0)r2：IF(m,c,0)and0i+j〈=3and(i=jori=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灌满水*/2r2：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)andL5+L2=5THEN(L5+L2,0)/*L2到入L5中*/r6：IF(L5,L2)andL5+L25THEN(5,L5+L2-5)/*L2到入L5中*/r7：IF(L5,L2)andL5+L2=2THEN(0,L5+L2)/*L5到入L2中*/r8：IF(L5,L2)andL5+L25THEN(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)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，规则集3r1: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次翻钱币得到的。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中规则的应用与R2中规则的执行结果无关，也与Ｒ1中其他的规则的执行无关。所以可以认为，先将R1中所有的规则对D应用，然后再按照原来的次序应用R2中的规则。因此对于本题的情况，这样得到的综合数据库与D'是相同的。而由于R1中一条规则的执行与其他的规则无关，所以R1中规则的执行顺序不会影响到最终的结果。因此满足可交换产生式系统的第三个条件。因此这样一个产生式系统是一个可交换的产生式系统。4第二章课后习题第1题答：为了方便起见，我们用((AB)()())这样的表表示一个状态。这样得到搜索图如下：第2题提示：可定义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题5答：定义h1=n*k，其中n是还未走过的城市数，k是还未走过的城市间距离的最小值。h2＝，其中n是还未走过的城市数，ki是还未走过的城市间距离中n个最小的距离。显然这两个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*的条件。下面我们来证明h(n)＝M+C-2B是满足A*条件的。我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要摆渡次。其中分子上的－3表示剩下三个留待最后一次运过去。除以2是因为一个来回可以运过去2人，需要个来回，而来回数不能是小数，需要向上取整，这个用符号表示。而乘以2是因为一个来回相当于两次摆渡，所以要乘以2。而