人工智能考题.doc

1、人工智能网上中考试题 1. 填空题（共12分，每小题2分）1）知识表示的性能应从以下二个方面评价：_和_；后者又分二个方面_和 _。 2) 框架系统的特性继承功能可通过组合应用槽的三个侧面来灵活实现，它们是 _。3）KB系统通常由以下三个部分组成：_；KB系统的开发工具和环境可分为以下三类：_。 4）按所用的基本学习策略可以将机器学习方法划分为以下几类：_ _。 5) 主观Bayes方法将推理规则表示为P Q形式，称_为先验似然比， _ 为条件似然比，_为规则的充分性因子。6）自然语言理解中，单句理解分二个阶段：_和_，后者又分二个步骤：_和_。 2、 问答题（共20分，每小题5分） 1）阐述

2、示例学习所采用的逐步特化学习策略，并说明学习过程中正、反例的作用。 2）为什么要在框架系统中实行相容匹配技术？如何实现？ 3）阐述Xps的冲突解法和推理引擎，并说明综合数据库中事实元素的时间标签在冲突解法中起的作用。 4）什么是问题归约？问题归约的操作算子与一般图搜索有何不同？与或图启发式搜索算法AO*的可采纳性条件是什么？ 3、 简单计算题（共35分，每小题7分） 1）按书上图8.5中给定的文法规则，再追加2条：N football, V play；画出英语句子”The boy play little football”的句法分析树。 2）已知有如下不确定推理规则： r1：C11C12 H1

3、 0.7； r2：H1 H 0.5； r3：C21C22 H 0.6； r4：(C31C32)C33 H 0.8； CF(C11) = 0.8， CF(C12) = 0.9，CF(C21) = 0.3，CF(C22) = 0.6， CF(C31) = 0.9，CF(C32) = 0.5，CF(C33) =0.7； 请应用MYCIN的确定性方法求出CF(H)。 3）把语句“每个学生都喜欢老师上的一门课。”表示为语义网络。 4）设计八数码游戏的评价函数f(n)，使其满足A*算法的要求；设初始和目 8 1 3 1 2 3 标棋盘布局分别为2 4 和 8 4 ，画出使用该评价函数的搜索图，并 7 6

4、5 7 6 5 标注每个节点的f(n)值。 5）化简以下目标公式（用在基于规则的逆向演绎中），并画出相应的与或图： （x）（$y）P(x) (Q(x) R(x,y) W(x) 4、 假设已知下列事实： （1）超市（Supermarket）卖（Sail）的商品(Goods)便宜(Cheap)。 （2）王（Wang）买（Buy）需要的（Want）便宜商品。 （3）自行车（Bicycle）是商品且超市卖自行车。 （4）王需要自行车。 （5）赵（Zhao）跟随王买同样的商品。 请应用归结反演证明方法回答以下问题： （1）王买自行车吗？ （2）赵买什么商品？ （18分） 5、请使用NOAH系统采用的最少

5、承诺(Least Commitment)策略作下图积木块世界的层次规划,画出规划过程示意图，并举例说明如何应用最少承担策略去解决冲突和利用有益的交互作用。(假定可使用的操作只有STACK(x, y)和UNSTACK(x, y) （15分）人工智能试卷 ( 2008-7-19 20:47 ) 一、 填空题1 一般公认人工智能学科诞生于 1956 年。2 人工智能的研究途径有 符号主义、连接主义 和进化主义。3 知识表示方法中的问题归约思想事实就是 简化，其三要素是初始问题描述、一套简化算子 和一套本原问题的描述 。 4 产生式系统主要有 、知识库和 三部分构成。5 启发式搜索在搜索中使用 启发信

6、息 帮助搜索。6 B规则逆向推理中，要求规则的 是单文字；给出的已知事实必须是 ；匹配的次序是 ；推理的终止条件是 。7 人工智能中处理不确定知识使用的数学方法有概率论、 模糊数学 和粗糙集理论等。8 公式集F= s A, g(y), f( z ) , s x, g(B), f(g(x) 的最一般合一者（mgu）是 A/x,B/y,g(x)/z 。二、 综合题1 简述问题归约的基本思想，并指出其三要素。2 深度优先搜索中为何常采用有界深度优先搜索？深度优先搜索可能出现无解，一直按照这个路径无穷的搜索下去，浪费搜索时间；而有界深度搜索，最大搜索深度到界限返回，节约搜索时间。 3 设有三个瓶子a、

7、b和c，其容积分别为8升、5升和1升，a瓶装满了8升液体。请用状态空间法给出将a瓶8升液体平分成两个4升液体的方案。 4 将下面的公式化为子句集表示。(x) (y) R(x) Q(x,y) ($y) Q(x,y) P(y) 三、 已知a + 2b + 3c + 4d + 5e = 40，a，b，c，d，e 为正整数。用遗传算法求解。请你：1设计染色体（个体）的表示方式；2设计适应度函数；3用实例说明怎样进行交叉和变异操作。四、 用谓词公式表示下面的文子描述。1. 所有的老虎都是有腿的。2. 有的花是不香的。 五、 用语义网络表示下列文字描述(1) Li 7月28日游览了黄山。 (2) 设计一个

8、框架，要求：不少于4各槽；要用到侧面。六、用归结方法证明目标公式G是条件公式F1、F2、F3的逻辑结论。F1: ( A B ) ( D C )F2: A E ( DE )F3: E BG: E C七、 已知事实：P(a) Q(b) R(b) ，规则：r1: P(x) W(x) R(x)，r2: Q(y) S(y)，用F规则正向演绎方法证明目标公式：S(x) W(x)。八、 已知s、a、b、c、g五个城市相互距离如图。构造的启发函数中h(n) 值如下表。g(n) 采用走过城市的实际路程。用下述指定搜索方法，找到从s到达g的路径，并用OPEN表和CLOSED表给出搜索过程。城市h(n)s32a11

9、b9c7g0(1) 不考虑g(n)，即：f(n) = h(n)。(2) 不考虑h(n)，即：f(n) = g(n)，(等代价搜索)。(3) f(n) = g(n) + h(n) 。 规约的基本思想：简化 规约目的：产生本原问题三要素：原始问题描述（S），一套简化算子(O)，一套本原问题描述(P)人工智能导论试卷一 窗体顶端一、 选择1、比起极小 - 极大法来，-剪枝法增大了找不到最佳走步的危险性，但其效率较高。 2、在A算法中，满足单调条件的h必然满足A*算法的条件。 3、设有机器人走迷宫问题，其入口坐标为(x0, y0)，出口坐标为(xt, yt)，当前机器人位置为(x, y)，若定义， 当

10、从入口到出口存在通路时，用A算法求解该问题，定能找到从入口到出口的最佳路径。 窗体底端窗体顶端二、 填空题1、在修正的A算法中，fm的含义是2、对任意节点n，设m是n的子节点，当h满足条件时，称h是单调的。三、 问答题1、简述用A*算法求解问题时为什么会出现重复扩展节点问题，解决的方法有哪些？ 2、简述回溯策略与深度优先策略的不同点。3、某问题由下列公式描述：(1)、试用归结法证明(x)R(x)；(2)、做出修改证明树，提取问题的回答。4、下图所示博弈树，按从左到右的顺序进行-剪枝搜索，试标明各生成节点的到推值，何处发生剪枝，及应选择的走步。5、某问题的状态空间图如下图所示，其中括号内标明的是

11、各节点的h值，弧线边的数字是该弧线的耗散值，试用A算法求解从初始节点S到目标节点T的路径。要求给出搜索图，标明各节点的f值，及各节点的扩展次序，并给出求得的解路径。 6、给19九个数字排一个序列，使得该序列的前n(n=1,.,9) 个数字组成的整数能被n整除。(1)、讨论哪些知识可以帮助该问题的求解。(2)、用产生式系统描述该问题。(给出综合数据库，规则集，上述 知识要在规则集中反映出来) 窗体底端第一章 课后习题窗体顶端1、对N5、k3时，求解传教士和野人问题的产生式系统各组成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态和目标条件的描述），并画出状态空间图。2、对量水问题

12、给出产生式系统描述，并画出状态空间图。有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。3、对梵塔问题给出产生式系统描述，并讨论N为任意时状态空间的规模。相传古代某处一庙宇中，有三根立柱，柱子上可套放直径不等的N个圆盘，开始时所有圆盘都放在第一根柱子上，且小盘处在大盘之上，即从下向上直径是递减的。和尚们的任务是把所有圆盘一次一个地搬到另一个柱子上去（不许暂搁地上等），且小盘只许在大盘之上。问和尚们如何搬法最后能完成将所有的盘子都移到第三

13、根柱子上（其余两根柱子，有一根可作过渡盘子使用）。求N2时，求解该问题的产生式系统描述，给出其状态空间图。讨论N为任意时，状态空间的规模。 4、对猴子摘香蕉问题，给出产生式系统描述。一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱子，攀登箱子等）。设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为a，箱子位置为b，香蕉位置为c），如何行动可摘取到香蕉。 5、对三枚钱币问题给出产生式系统描述及状态空间图。设有三枚钱币，其排列处在正、正、反状态，现允许每次可翻动其中任意一个钱币，问只许操作三次的情况下，如何翻动钱币使其

14、变成正、正、正或反、反、反状态。 6、说明怎样才能用一个产生式系统把十进制数转换为二进制数，并通过转换141.125这个数为二进制数，阐明其运行过程。7、设可交换产生式系统的一条规则R可应用于综合数据库D来生成出D，试证明若R存在逆，则可应用于D的规则集等同于可应用于D的规则集。8、一个产生式系统是以整数的集合作为综合数据库，新的数据库可通过把其中任意一对元素的乘积添加到原数据库的操作来产生。设以某一个整数子集的出现作为目标条件，试说明该产生式系统是可交换的。窗体底端第一章课后习题答案说明：由于人工智能的很多题目都很灵活，以下解答仅供参考。第1题答： 1，综合数据库定义三元组：（m, c, b

15、） 其中：，表示传教士在河左岸的人数。，表示野人在河左岸的认输。，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

16、) 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) T

17、HEN (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) and 0= j or i=0) THEN (m-i, c-j, 0)r2：IF (m, c, 0) and 0= j or i=0) TH

18、EN (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

19、, 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分别表示三根立柱，均为表，表的元素为1N之间的整数，表示N个不同大小的盘子，数值小的数表示小盘子，数值大的数表示大盘子。表的第一个元素表示立柱最上面的柱子，其余类推。2，规则集为了方便表示规则集，引入以

20、下几个函数：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

21、 (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，.，

22、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处r

23、3: 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） 其中x1x4为变量。第5题答： 1，综合数据库定义四元组：（x, y, z, n） 其中x,

24、y,x0,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表示到目

25、前为止还没有转换的十进制数的整数部分和小数部分，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题答： 说明一个产生式系统是可交换的，就是要证明该

26、产生式系统满足可交换产生式系统的三条性质。（1）该产生式系统以整数的集合为综合数据库，其规则是将集合中的两个整数相乘后加入到数据库中。由于原来数据库是新数据库的子集，所以原来的规则在新数据库中均可以使用。所以满足可交换产生式系统的第一条性质。（2）该产生式系统以某个整数的子集的出现为目标条件，由于规则执行的结果只是向数据库中添加数据，如果原数据库中已经满足目标了，即出现了所需要的整数子集，规则的执行结果不会破坏该整数子集的出现，因此新的数据库仍然会满足目标条件。满足可交换产生式系统的第二个性质。 （3）设D是该产生式系统的一个综合数据库。对D施以一个规则序列后，得到一个新的数据库D。该规则序列

27、中的有些规则有些是可以应用于D的，这些规则用R1表示。有些规则是不能应用于D的，这些规则用R2表示。由于R1中的规则可以直接应用与D，所以R1中规则的应用与R2中规则的执行结果无关，也与1中其他的规则的执行无关。所以可以认为，先将R1中所有的规则对D应用，然后再按照原来的次序应用R2中的规则。因此对于本题的情况，这样得到的综合数据库与D是相同的。而由于R1中一条规则的执行与其他的规则无关，所以R1中规则的执行顺序不会影响到最终的结果。因此满足可交换产生式系统的第三个条件。因此这样一个产生式系统是一个可交换的产生式系统。第二章 课后习题窗体顶端1、用回溯策略求解如下所示二阶梵塔问题，画出搜索过程

28、的状态变化示意图。对每个状态规定的操作顺序为：先搬1柱的盘，放的顺序是先2柱后3柱；再搬2柱的盘，放的顺序是先3柱后1柱；最后搬3柱的盘，放的顺序是先1柱后2柱。2、滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下：其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是： （1）任意一个将牌可以移入相邻的空格，规定其耗散值为1；（2）任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可）。对这个问题，定义一个启发函数h(n)，并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨

29、别这个h(n)是否满足下界范围？在你的搜索树中，对所有的节点满足不满足单调限制？ 3、对1.4节中的旅行商问题，定义两个h函数（非零），并给出利用这两个启发函数用算法A求解1.4节中的五城市问题。讨论这两个函数是否都在h*的下界范围及求解结果。4、2.1节四皇后问题表述中，设应用每一条规则的耗散值均为1，试描述这个问题h*函数的一般特征。你是否认为任何h函数对引导搜索都是有用的？ 5、对N5，k3的MC问题，定义两个h函数（非零），并给出用这两个启发函数的A算法搜索图。讨论用这两个启发函数求解该问题时是否得到最佳解。6、证明OPEN表上具有f(n)f*(s)的任何节点n，最终都将被A*选择去扩

30、展。7、如果算法A*从OPEN表中去掉任一节点n，对n有f(n)F（Ff*(s)），试说明为什么算法A*仍然是可采纳的。8、用算法A逆向求解图2.7中的八数码问题，评价函数仍定义为f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相会。9、讨论一个h函数在搜索期间可以得到改善的几种方法。10、四个同心圆盘的扇区数字如图所示，每个圆盘可单独转动。问如何转动圆盘使得八个径向的4个数字和均为12。窗体底端第1题答： 为了方便起见，我们用(AB)()()这样的表表示一个状态。这样得到搜索图如下： 第2题提示：可定义h为：hB右边的W的数目设j节点是i节点的子节点，则根据走法不同，h(i)-h(

31、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跳过

32、了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)

33、，即满足A*条件。 第3题答： 定义h1=n*k，其中n是还未走过的城市数，k是还未走过的城市间距离的最小值。 h2，其中n是还未走过的城市数，ki是还未走过的城市间距离中n个最小的距离。 显然这两个h函数均满足A*条件。 第4题提示：对于四皇后问题，如果放一个皇后的耗散值为1的话，则任何一个解的耗散值都是4。因此如果h是对该耗散值的估计，是没有意义的。对于像四皇后这样的问题，启发函数应该是对找到解的可能性的评价。比如像课上讲到的，利用一个位置放皇后后，消去的对角线的长度来进行评价。第5题答： 定义h1=M+C-2B，其中M，C分别是在河的左岸的传教士人数和野人人数。B1表示船在左岸，B0表示

34、船在右岸。也可以定义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人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情

35、况下，也至少需要摆渡次。其中分子上的3表示剩下三个留待最后一次运过去。除以2是因为一个来回可以运过去2人，需要个来回，而来回数不能是小数，需要向上取整，这个用符号表示。而乘以2是因为一个来回相当于两次摆渡，所以要乘以2。而最后的1，则表示将剩下的3个运过去，需要一次摆渡。化简有：再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此对于状态(M，C，0)来说，其所需要的最少摆渡数，相当于船在左岸时状态(M+1，C，1)或(M，C+1，1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为：(M+C+1)-2+1 。其中(M+C+1

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

37、*算法每次从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

38、*算法中，对NEST中的节点按g值的大小选择待扩展的节点，相当于令这些节点的h0，就是动态修改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题提示：很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式，很多情况下，也不一定能清晰的写成一个函数的形式

39、。为了叙述方便，我们将两个相对的扇区称为相对扇区，图中阴影部分的扇区称为阴影扇区，非阴影部分的扇区称为非阴影扇区。 由题意，在目标状态下，一个扇区的数字之和等于12，一个相对扇区的数字之和等于24，而一个阴影扇区或者非阴影扇区的数字之和为48。为此，我们可以将目标进行分解，首先满足阴影扇区的数字之和为48（这时非阴影部分的数字和也一定为48）。为了这个目标我们可以通过每次转动圆盘45o实现。在第一个目标被满足的情况下，我们再考虑第二个目标：每一个相对扇区的数字和为24。在实现这个目标的过程中，我们希望不破坏第一个目标。为此我们采用转动90o的方式实现，这样即可以调整相对扇区的数字和，又不破坏第

40、一个目标。在第二个目标实现之后，我们就可以实现最终目标：扇区内的数字和为12。同样我们希望在实现这个目标的时候，不破坏前两个目标。为此我们采用转动180o的方式实现。这样同样是即可以保证前两个目标不被破坏，又可以实现第三个目标。 经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第一、第二个目标的实现，都能够实现第三个目标呢？有可能不一定。在这种情况下，就需要在发现第三个目标不能实现时，重新试探其他的第一、第二个目标。 第三章 课后习题窗体顶端1、数字重写问题的变换规则如下：63，343，164，232，142，221，1问如何用这些规则把数字6变换成一个由若干个1组成的数字串。试

41、用算法AO*进行求解，并给出搜索图。求解时设k-连接符的耗散值是k个单位，h函数值规定为：h（1）0，h（n）n（n1）。 2、余一棋的弈法如下：两棋手可以从5个钱币堆中轮流拿走一个、两个或三个钱币，拣起最后一个钱币者算输。试通过博弈证明，后走的选手必胜，并给出一个简单的特征标记来表示取胜策略。3、对下图所示的博弈树，以优先生成左边节点顺序来进行-搜索，试在博弈树上给出何处发生剪枝的标记，并标明属于剪枝还是剪枝。4、AO*算法中，第7步从S中选一个节点，要求其子孙不在S中出现，讨论应如何实现对S的控制使得能有效地选出这个节点。如下图所示，若E的耗散值发生变化时，所提出的对S的处理方法应能正确工

42、作。5、如何修改AO*算法使之能处理出现回路的情况。如下图所示，若节点C的耗散值发生变化时，所修改的算法能正确处理这种情况。6、对33的一字棋，设用+1和-1分别表示两选手棋子的标记，用0表示空格，试给出一字棋产生式系统的描述。7、写一个-搜索的算法。8、用一个9维向量C来表示一字棋棋盘的格局，其分量根据相应格内的，空或的标记分别用+1，0，或-1来表示。试规定另一个9维向量W，使得点积CW可作为MAX选手（棋子标记为）估计非终端位置的一个有效的评价函数。用这个评价函数来完成几步极小-极大搜索，并分析该评价函数的效果。窗体底端第三章课后习题答案说明：由于人工智能的很多题目都很灵活，以下解答仅供

43、参考。第1题答：此题要求按照课中例题的方式，给出算法，以下是每个循环结束时的搜索图。上面这种做法比较简单，也可以如下做：第2题答：从该搜索图可以看出，无论先走者选择哪个走步，后走者都可以走到标记为A的节点，该节点只剩下一枚钱币，所以先走者必输。 对于一般的具有n个钱币的情况，当n4m1时，后走者存在取胜策略。因为后走者可以根据先走者的走法，选择自己的走法，使得双方拿走的钱币数为4，这样经过m个轮回后，共拿走了4m个钱币，只剩下了一枚钱币，而此时轮到先走者走棋。所以在这种情况下，后走者存在取胜的策略。 对于钱币数不等于4m1的情况，先走者可以根据实际的钱币数选择取走的钱币数，使得剩下的钱币数为4m1个，此时先走者相当于4m1个钱币时的后走者了。因此在这种情况下，先走者存在获胜的策略。第3题答：第四章 课后习题窗体顶端1、化下列公