《人工智能及其应用》(蔡自兴)课后习题答案第3章.doc

第三章 搜索推理技术3-1 什么是图搜索过程?其中，重排OPEN表意味着什么，重排的原则是什么?图搜索的一般过程如下：(1) 建立一个搜索图G(初始只含有起始节点S)，把S放到未扩展节点表中（OPEN表）中。(2) 建立一个已扩展节点表（CLOSED表），其初始为空表。(3) LOOP：若OPEN表是空表，则失败退出。(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号(5) 若n为一目标节点，则有解并成功退出。此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)(6) 扩展节点n，生成不是n的祖先的那些后继节点的集合M。将M添入图G中。 (7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针，并将它们加进OPEN表。对已经在OPEN或CLOSED表上的每个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8) 按某一任意方式或按某个探试值，重排OPEN表。 (9) GO LOOP。重排OPEN表意味着，在第(6)步中，将优先扩展哪个节点，不同的排序标准对应着不同的搜索策略。重排的原则当视具体需求而定，不同的原则对应着不同的搜索策略，如果想尽快地找到一个解，则应当将最有可能达到目标节点的那些节点排在OPEN表的前面部分，如果想找到代价最小的解，则应当按代价从小到大的顺序重排OPEN表。3-2 试举例比较各种搜索方法的效率。宽度优先搜索(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。有界深度优先搜索(1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。(2) 如果OPEN为一空表，则失败退出。(3) 把第一个节点(节点n)从OPEN表移到CLOSED表。(4) 如果节点n的深度等于最大深度，则转向(2)。(5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。(6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。等代价搜索方法以g(i)的递增顺序扩展其节点，其算法如下：(1) 把起始节点S放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解;否则令g(S)=0。(2) 如果OPEN是个空表，则没有解而失败退出。(3) 从OPEN表中选择一个节点i，使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点i(要是有目标节点的话)；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。(4) 如果节点i为目标节点，则求得一个解。(5) 扩展节点i。如果没有后继节点，则转向第(2)步。(6) 对于节点i的每个后继节点j，计算g(j)=g(i)+c(i,j)，并把所有后继节点j放进OPEN表。提供回到节点i的指针。(7) 转向第(2)步。3-3 化为子句形有哪些步骤?请结合例子说明之。任一谓词演算公式可以化成一个子句集。其变换过程由下列九个步骤组成：(1)消去蕴涵符号将蕴涵符号化为析取和否定符号(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄·摩根定律(3)对变量标准化对哑元改名以保证每个量词有其自己唯一的哑元(4)消去存在量词引入Skolem函数，消去存在量词如果要消去的存在量词不在任何一个全称量词的辖域内，那么我们就用不含变量的Skolem函数即常量。(5)化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形 = (前缀) (母式) 前缀 = 全称量词串母式 = 无量词公式(6)把母式化为合取范式反复应用分配律，将母式写成许多合取项的合取的形式，而每一个合取项是一些谓词公式和(或)谓词公式的否定的析取(7)消去全称量词消去前缀，即消去明显出现的全称量词(8)消去连词符号(合取)用合取项1,合取项2替换明显出现的合取符号(9)更换变量名称更换变量符号的名称，使一个变量符号不出现在一个以上的子句中3-4 如何通过消解反演求取问题的答案?给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下：(1)否定L，得L；(2)把L添加到S中去；(3)把新产生的集合L，S化成子句集；(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。3-5 什么叫合适公式?合适公式有哪些等价关系?合式公式的递归定义为：(1) 原子谓词公式是合式公式(2) 若A为合式公式，则A的否定也是合式公式(3) 若A、B都是合式公式，则A AND B, AOR B, AèB, Aß>B 也都是合式公式(4) 若A是合式公式，x为A中的自由变元，则(ANY x)A 和 (EXT x)A 都是合式公式(5) 只有按规则(1)(4)求得的公式，才是合式公式等价关系有：否定之否定蕴含与与或形式的等价狄.摩根定律分配律交换律结合律逆否律否定跨越量词全称量词同与或连词量词中的哑元3-6 用宽度优先搜索求图3.33所示迷宫的出路。图 3.33 迷宫一例第一步SàAàB第二步BàHBàC第三步HàGCàF最终路径为SàAàBàCàF3-7 用有界深度优先搜索方法求解图3.34所示八数码难题。2812316384754765 So Sg图 3-34八数码难题按顺时针方向(上、右、下、左)试探，尝试移动空格，将最大深度定为5S0(So)28163754S128316754S228316475S328316475S428314765S523184765S62318476523184765S712384765S8(Sg)123847653-8 应用最新的方法来表达传教士和野人问题，编写一个计算机程序，以求得安全渡过全部6个人的解答。提示：在应用状态空间表示和搜索方法时，可用(Nm，Nc)来表示状态描述，其中Nm和Nc分别为传教士和野人的人数。初始状态为(3，3)，而可能的中间状态为(0，1)，(0，2)，(0，3)，(1，1)，(2，1)，(2，2)，(3，0)，(3，1)和(3，2)等。3-9 试比较宽度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实例数据加以说明。3-10 一个机器人驾驶卡车，携带包裹(编号分别为1、2和3)分别投递到林(LIN)、吴(WU)和胡(HU)3家住宅处。规定了某些简单的操作符，如表示驾驶方位的drive(x,y)和表示卸下包裹的unload(z)；对于每个操作符，都有一定的先决条件和结果。试说明状态空间问题求解系统如何能够应用谓词演算求得一个操作符序列，该序列能够生成一个满足AT(#1，LIN)AT(#2，WU)AT(#3,HU)的目标状态。初始状态可描述为：AT(#1, LIN) AND AT(#2, WU) AND AT(#1, HU) AND AT(#1, CAR) AND AT(#2, CAR) AND AT(#3, CAR)目标状态可描述为：AT(#1, LIN) AND AT(#2, WU) AND AT(#1, HU) AND AT(#1, CAR) AND AT(#2, CAR) AND AT(#3, CAR)对每个操作符都有一定的先决条件和结果，详细如下drive(x, y)先决条件：AT(CAR, x)结果： AT(CAR, y)unload(z)先决条件：AT(z, CAR) AND AT(CAR, x)结果： AT(z, CAR) AND AT(z, x)原问题就转换为寻找一个可将初始状态转换到目标状态的操作序列如何求得该操作序列?3-11 规则演绎系统和产生式系统有哪几种推理方式?各自的特点为何?规则演绎系统的推理方式有正向推理、逆向推理和双向推理项目正向推理逆向推理推理方向从if部分向then部分推理的过程，它是从事实或状况向目标或动作进行操作的从then部分向if部分推理的过程，它是从目标或动作向事实或状况进行操作的目标表达式文字的析取任意形式事实表达式任意形式文字的合取双向推理组合了正向推理和逆向推理的优点，克服了各自的缺点，具有更高的搜索求解效率。产生式系统的推理方式有正向推理、逆向推理和双向推理项目正向推理逆向推理驱动方式数据驱动目标驱动推理方法从一组数据出发向前推导结论从可能的解答出发，向后推理验证解答启动方法从一个事件启动由询问关于目标状态的一个问题而启动透明程序不能解释其推理过程可解释其推理过程推理方向由底向上推理由顶向下推理优点算法简单，容易实现搜索目的性强，推理效率高缺点盲目搜索，可能会求解许多与总目标无关的子目标，每当总数据库内容更新后都要遍历整个规则库，推理效率低目标的选择具有盲目性，可能会求解许多假的目标；当可能的结论数目很多时，推理效率不高；当规则的右部是执行某种动作而不是结论时，逆向推理不便使用适用场合已知初始数据，而无法提供推理目标，或解空间很大的一类问题，如监控，预测，规划，设计等问题结论单一或者已知目标结论，而要求验证的系统，如选择，分类，故障诊断等问题典型系统CLIPS, OPSPROLOG双向推理结合了正向推理和逆向推理的长处，克服了两者的短处，其控制策略比两者都要复杂3-12 为什么需要采用系统组织技术?有哪几种系统组织技术?如果不采用系统组织技术，而直接写出包含所有知识的规则，并让系统利用这些规则，找出一条从给定状态到目标状态的路径，这种方法有严重的缺点：(1) 随着规则的增加，既要加入新的规则，又要使新规则不与现有规则产生冲突，这将使问题变得愈来愈困难(2) 在问题求解过程中，由于每一步都必须考虑所有规则，效率就会大大降低，然而，实际上却往往是只有应用完一组规则之后，才考虑另一组别的规则(3) 一种问题求解技术和知识表达形式可能对问题的某一部分是最好的，而对另一部分却不是最好的因此，采用系统组织技术，将一个大系统中的知识分成一组相对独立的模块比较合适。有3种系统组织技术：议程表、黑板法和Delta极小搜索法3-13 研究不确定性推理有何意义?有哪几种不确定性?不确定性推理是研究复杂系统不完全性和不确定性的有力工具。有3种不确定性，关于证据的不确定性(观测有误差)，关于结论的不确定性和多个规则支持同一事实时的不确定性。3-14 单调推理有何局限性?什么叫缺省推理?非单调推理系统如何证实一个节点的有效性?单调系统不能很好地处理常常出现在现实问题领域中的3类情况，即不完全的信息、不断变化的情况、以及求解复杂问题过程中生成的假设有两种方法可以证实节点的有效性：(1) 支持表。 ( SL (IN-节点表) (OUT- 节点表) )如果某节点的IN节点表中提到的节点当前都是IN, 且OUT节点表中提到的节点当前都是OUT，则它是有效的(2) 条件证明。( CP(结论)(IN-假设)(OUT-假设) )条件证明(CP)的证实表示有前提的论点，无论何时，只要在IN假设中的节点为IN, OUT假设中的节点为OUT, 则结论节点往往为IN，于是条件证明的证实有效。3-15 在什么情况下需要采用不确定推理或非单调推理?不完全的信息、不断变化的情况、以及求解复杂问题过程中生成的假设3-16 下列语句是一些几何定理，把这些语句表示为基于规则的几何证明系统的产生式规则：(1) 两个全等三角形的各对应角相等。(2) 两个全等三角形的各对应边相等。(3) 各对应边相等的三角形是全等三角形。(4) 等腰三角形的两底角相等。规则(1): IF 两个三角形全等 THEN 各对应角相等规则(2): IF 两个三角形全等 THEN 各对应边相等规则(3): IF 两个三角形各对应边相等 THEN 两三角形全等规则(4): IF 它是等腰三角形 THEN 它的两底角相等