发布时间 : 星期四 文章人工智能课后答案更新完毕开始阅读
r6：IF (L5, L2) and L5+L2>5 THEN (5, L5+L2-5) /* L2到入L5中 */ r7：IF (L5, L2) and L5+L2<=2 THEN (0, L5+L2) /* L5到入L2中 */ r8：IF (L5, L2) and L5+L2>5 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) 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次翻钱币得到的。 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中规则的执行顺序不会影响到最终的结果。因此满足可交换产生式系统的第三个条件。
因此这样一个产生式系统是一个可交换的产生式系统。 第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题
答：定义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人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要