搜索
第一章课后习题1、对N＝5、k≤3时，求解传教士和野人问题的产生式系统各组成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态和目标条件的描述），并画出状态空间图。2、对量水问题给出产生式系统描述，并画出状态空间图。有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。3、对梵塔问题给出产生式系统描述，并讨论N为任意时状态空间的规模。相传古代某处一庙宇中，有三根立柱，柱子上可套放直径不等的N个圆盘，开始时所有圆盘都放在第一根柱子上，且小盘处在大盘之上，即从下向上直径是递减的。和尚们的任务是把所有圆盘一次一个地搬到另一个柱子上去（不许暂搁地上等），且小盘只许在大盘之上。问和尚们如何搬法最后能完成将所有的盘子都移到第三根柱子上（其余两根柱子，有一根可作过渡盘子使用）。求N＝2时，求解该问题的产生式系统描述，给出其状态空间图。讨论N为任意时，状态空间的规模。4、对猴子摘香蕉问题，给出产生式系统描述。一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱子，攀登箱子等）。设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为a，箱子位置为b，香蕉位置为c），如何行动可摘取到香蕉。5、对三枚钱币问题给出产生式系统描述及状态空间图。设有三枚钱币，其排列处在正、正、反状态，现允许每次可翻动其中任意一个钱币，问只许操作三次的情况下，如何翻动钱币使其变成正、正、正或反、反、反状态。6、说明怎样才能用一个产生式系统把十进制数转换为二进制数，并通过转换141.125这个数为二进制数，阐明其运行过程。7、设可交换产生式系统的一条规则R可应用于综合数据库D来生成出D'，试证明若R存在逆，则可应用于D'的规则集等同于可应用于D的规则集。8、一个产生式系统是以整数的集合作为综合数据库，新的数据库可通过把其中任意一对元素的乘积添加到原数据库的操作来产生。设以某一个整数子集的出现作为目标条件，试说明该产生式系统是可交换的。第二章课后习题第二章课后习题1、用回溯策略求解如下所示二阶梵塔问题，画出搜索过程的状态变化示意图。对每个状态规定的操作顺序为：先搬1柱的盘，放的顺序是先2柱后3柱；再搬2柱的盘，放的顺序是先3柱后1柱；最后搬3柱的盘，放的顺序是先1柱后2柱。2、滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下：其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是：（1）任意一个将牌可以移入相邻的空格，规定其耗散值为1；（2）任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可）。对这个问题，定义一个启发函数h(n)，并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨别这个h(n)是否满足下界范围？在你的搜索树中，对所有的节点满足不满足单调限制？3、对1.4节中的旅行商问题，定义两个h函数（非零），并给出利用这两个启发函数用算法A求解1.4节中的五城市问题。讨论这两个函数是否都在h*的下界范围及求解结果。4、2.1节四皇后问题表述中，设应用每一条规则的耗散值均为1，试描述这个问题h*函数的一般特征。你是否认为任何h函数对引导搜索都是有用的？5、对N＝5，k≤3的M－C问题，定义两个h函数（非零），并给出用这两个启发函数的A算法搜索图。讨论用这两个启发函数求解该问题时是否得到最佳解。6、证明OPEN表上具有f(n)＜f*(s)的任何节点n，最终都将被A*选择去扩展。7、如果算法A*从OPEN表中去掉任一节点n，对n有f(n)＞F（F＞f*(s)），试说明为什么算法A*仍然是可采纳的。8、用算法A逆向求解图2.7中的八数码问题，评价函数仍定义为f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相会。9、讨论一个h函数在搜索期间可以得到改善的几种方法。10、四个同心圆盘的扇区数字如图所示，每个圆盘可单独转动。问如何转动圆盘使得八个径向的4个数字和均为12。第三章课后习题1、数字重写问题的变换规则如下：6→3，34→3，16→4，23→2，14→2，22→1，1问如何用这些规则把数字6变换成一个由若干个1组成的数字串。试用算法AO*进行求解，并给出搜索图。求解时设k-连接符的耗散值是k个单位，h函数值规定为：h（1）＝0，h（n）＝n（n≠1）。2、余一棋的弈法如下：两棋手可以从5个钱币堆中轮流拿走一个、两个或三个钱币，拣起最后一个钱币者算输。试通过博弈证明，后走的选手必胜，并给出一个简单的特征标记来表示取胜策略。3、对下图所示的博弈树，以优先生成左边节点顺序来进行α-β搜索，试在博弈树上给出何处发生剪枝的标记，并标明属于α剪枝还是β剪枝。4、AO*算法中，第7步从S中选一个节点，要求其子孙不在S中出现，讨论应如何实现对S的控制使得能有效地选出这个节点。如下图所示，若E的耗散值发生变化时，所提出的对S的处理方法应能正确工作。5、如何修改AO*算法使之能处理出现回路的情况。如下图所示，若节点C的耗散值发生变化时，所修改的算法能正确处理这种情况。6、对3×3的一字棋，设用+1和-1分别表示两选手棋子的标记，用0表示空格，试给出一字棋产生式系统的描述。7、写一个α-β搜索的算法。8、用一个9维向量C来表示一字棋棋盘的格局，其分量根据相应格内的×，空或○的标记分别用+1，0，或-1来表示。试规定另一个9维向量W，使得点积C·W可作为MAX选手（棋子标记为×）估计非终端位置的一个有效的评价函数。用这个评价函数来完成几步极小-极大搜索，并分析该评价函数的效果。第四章课后习题1、化下列公式成子句形式：（1）（x）[P（x）→P（x）]（2）{~{（x）P（x）}}→（x）[~P（x）]（3）~（x）{P（x）→{（y）[P（y）→P（f（x，y））]∧~（y）[Q（x，y）→P（y）]}}（4）（x）（y）{[P（x，y）→Q（y，x）]∧[Q（y，x）→S（x，y）]}→（x）（y）[P（x，y）→S（x，y）]2、以一个例子证明置换的合成是不可交换的。3、找出集{P（x，z，y），P（w，u，w），P（A，u，u）}的mgu。4、说明下列文字集不能合一的理由：（1）{P（f（x，x），A），P（f（y，f（y，A）），A）}（2）{~P（A），P（x）}（3）{P（f（A），x），P（x，A）}5、已知两个子句为Loves（father（a），a）~Loves（y，x）∨Loves（x，y）试用合一算法求第一个子句和第二个子句的第一个文字合一时的结果。6、用归结反演法证明下列公式的永真性：（1）（x）{[P（x）→P（A）]∧[P（x）→P（B）]}（2）（z）[Q（z）→P（z）]→{（x）[Q（x）→P（A）]∧[Q（x）→P（B）]}（3）（x）（y）{[P（f（x））∧Q（f（B））]→[P（f（A））∧P（y）∧Q（y）]}（4）（x）（y）P（x，y）→（y）（x）P（x，y）（5）（x）{P（x）∧[Q（A）∨Q（B）]}→（x）[P（x）∧Q（x）]7、以归结反演法证明公式（x）P（x）是[P（A1）∨P（A2）]的逻辑推论，然而，（x）P（x）的Skolem形即P（A）并非[P（A1）∨P（A2）]的逻辑推论，请加以证明。8、给定下述语句：Johnlikesallkindsoffood.Applesarefood.Anythinganyoneeatsandisn'tkilledbyisfood.Billeatspeanutsandisstillalive.SueeatseverythingBilleats.（1）用归结法证明Johnlikespeanuts。（2）用归结法提取回答WhatfooddoesSueeat?9、已知事实公式为（（x）（y）（z）（Gt（x，y）∧Gt（y，z）→Gt（x，z））（u）（v）（Succ（u，v）→Gt（u，v）（x）（~Gt（x，x））求证Gt（5，2）试判断下面的归结过程是否正确？若有错误应如何改进：10、设公理集为（u）LAST（cons（u，NIL），u）（cons是表构造函数）（x）（y）（z）（LAST（y，z）→LAST（cons（x，y），z））（LAST（x，y）代表y是表x的最末元素）（1）用归结反演法证明如下定理：（v）LAST（cons（2，cons（1，NIL）），v）（2）用回答提取过程求表（2，1）的最末元素v。（3）简要描述如何使用这个方法求长表的最末元素。11、对一个基于规则的几何定理证明系统，把下列语句表示成产生式规则：（1）两个全等的三角形的对应角相等。（2）两个全等的三角形的对应边相等。（3）如果两个三角形对应边是相等的，则这两个三角形全等。（4）一个等腰三角形的底角是相等的。12、我们来考虑下列一段知识：Tony、Mike和John属于Alpine俱乐部，Alpine俱乐部的每个成员不是滑雪运动员就是一个登山运动员，登山运动员不喜欢雨而且任一不喜欢雪的人不是滑雪运动员，Mike讨厌Tony所喜欢的一切东西，而喜欢Tony所讨厌的一切东西，Tony喜欢雨和雪。以谓词演算语句的集合表示这段知识，这些语句适合一个逆向的基于规则的演绎系统。试说明这样一个系统怎样才能回答问题有没有Alpine俱乐部的一个成员，他是一个登山运动员但不是一个滑雪运动员呢？13、一个积木世界的状态由下列公式集描述：ONTABLE（A）CLEAR（E）ONTABLE（C）CLEAR（D）ON（D，C）HEAVY（D）ON（B，A）WOODEN（B）HEAVY（B）ON（E，B）绘出这些公式所描述的状态的草图。下列语句提供了有关这个积木世界的一般知识：每个大的蓝色积木块是在一个绿色积木块上。每个重的木制积木块是大的。所有顶上没有东西的积木块都是蓝色的。所有木制积木块是蓝色的。以具有单文字后项的蕴涵式的集合表示这些语句。绘出能求解哪个积木块是在绿积木块上这个问题的一致解图（用B规则）。答案第一章课后习题答案说明：由于人工智能的很多题目都很灵活，以下解答仅供参考。第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)第二种方法：将规则集综合在一起，简化表示。规