人工智能原理与应用 (张仰森 著) 高等教育出版社 课后答案

　　人工智能原理与应用 (张仰森 著) 高等教育出版社 课后答案_工学_高等教育_教育专区。人工智能原理与应用 (张仰森 著) 高等教育出版社 习题 第二章 部分答案

　　2.7 解：根据谓词知识表示的步骤求解问题如下： 解法一： (1)本问题涉及的常量定义为： 猴子：Monkey，箱子：Box，香蕉：Banana，位置：a，b，c (2)定义谓词如下： SITE(x，y)：表示 x 在 y 处； HANG(x，y)：表示 x 悬挂在 y 处； ON(x，y)：表示 x 站在 y 上； HOLDS(y，w)：表示 y 手里拿着 w。 (3)根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下： 问题的初始状态表示： SITE(Monkey，a)∧HANG(Banana，b)∧SITE(Box，c)∧~ON(Monkey，Box) ∧~HOLDS(Monkey，Banana) 问题的目标状态表示： SITE(Monkey，b)∧~HANG(Banana，b)∧SITE(Box，b) ∧ON(Monkey，Box)∧HOLDS(Monkey，Banana) 解法二： (1) 本问题涉及的常量定义为： 猴子：Monkey，箱子：Box，香蕉：Banana，位置：a，b，c (2) 定义谓词如下： SITE(x，y)：表示 x 在 y 处； ONBOX(x)：表示 x 站在箱子顶上； HOLDS(x)：表示 x 摘到了香蕉。 (3)根据问题的描述将问题的初始状态和目标状态分别用谓词公式表示如下： 问题的初始状态表示： SITE(Monkey，a)∧SITE(Box，c)∧~ONBOX(Monkey)∧~HOLDS(Monkey) 问题的目标状态表示： SITE(Box，b)∧SITE(Monkey，b)∧ONBOX(Monkey)∧HOLDS(Monkey) 从上述两种解法可以看出，只要谓词定义不同，问题的初始状态和目标状态就不 同。所以，对于同样的知识，不同的人的表示结果可能不同。 2.8 解：本问题的关键就是制定一组操作，将初始状态转换为目标状态。为了用谓词公 式表示操作，可将操作分为条件(为完成相应操作所必须具备的条件)和动作两部分。条件易 于用谓词公式表示， 而动作则可通过执行该动作前后的状态变化表示出来， 即由于动作的执 行， 当前状态中删去了某些谓词公式而又增加一些谓词公式从而得到了新的状态， 通过这种 不同状态中谓词公式的增、减来描述动作。 定义四个操作的谓词如下，操作的条件和动作可用谓词公式的增、删表示： (1)gotox，y)：从 x 处走到 y 处。 条件：SITE(Monkey，x) 动作：删除 SITE(Monkey，x)；增加 SITE(Monkey，y) (2)pushbox (x，y)：将箱子从 x 处推到 y 处。 条件：SITE(Monkey，x)∧SITE(Box，x)∧~ONBOX(Monkey) 动作：删除 SITE(Monkey，x)，SITE(Box，x)；增加 SITE(Monkey，y)，SITE(Box，y) (3)climbbox：爬到箱子顶上。 条件：~ONBOX(Monkey) 动作：删除~ONBOX(Monkey)；增加 ONBOX(Monkey) (4)grasp：摘下香蕉。 条件：~HOLDS(Monkey) ∧ONBOX(Monkey) ∧SITE(Monkey，b) 动作：删除~HOLDS(Monkey)；增加 HOLDS(Monkey) 在执行某一操作前，先检查当前状态是否满足其前提条件。若满足，则执行该操作。 否则，检查另一操作的条件是否被满足。检查的方法就是当前的状态中是否蕴含了操 作所要求的条件。在定义了操作谓词后，就可以给出从初始状态到目标状态的求解过 程。在求解过程中，当进行条件检查时，要进行适当的变量代换。 SITE(Monkey，a) SITE(Box，c) ~ONBOX(Monkey) ~HOLDS(Monkey) ?goto(x，y)，用 a 代 x，用 c 代 y SITE(Monkey，c) SITE(Box，c) ~ONBOX(Monkey) ~HOLDS(Monkey) ? pushbox(x，y)，用 c 代 x，用 b 代 y SITE(Monkey，b) SITE(Box，b) ~ONBOX(Monkey) ~HOLDS(Monkey) ?climbbox SITE(Monkey，b) SITE(Box，b) ONBOX(Monkey) ~HOLDS(Monkey) ?grasp SITE(Monkey，b) SITE(Box，b) ONBOX(Monkey) HOLDS(Monkey) 2.12 解：首先建立棋盘变换的产生式规则。如果把棋盘的每一种布局看做是一个状态矩 阵，本题就变成了从初始状态矩阵到目标状态矩阵的一种变化。 所谓棋盘状态的变化就是希望棋盘上空格周围的棋子能走进空格， 这也可以理解为移动 空格，只要实现空格的上、下、左、右四种移动即可。可通过建立四个条件一操作型的产生 式规则，来实现这四种移动。 设 Sij 为状态矩阵中的第 i 行和第 j 列的数码，i0、j0 表示空格所在的行和列，如果在状 态矩阵中用 0 来表示空格的话，则建立如下四条产生式规则： R1:if (jo – 1≥1) then begin Siojo: = Sio(jo-1); Sio(jo-1): =0 end 空格左移 R2:if (io – 1≥1) then begin Siojo: = S(io-l)jo; S(io-l)jo: =0 end 空格上移 R3:if (Jo + 1≤3) then begin Siojo: = Sio(jo+1); Sio(jo+1): = 0 end 空格右移 R4: if (io + 1≤3) then begin Siojo: = S(io+l)jo; S(io+l)jo: = 0 end 空格下移 然后,建立综合数据库。将棋盘的布局表示为状态距阵的形式存入综合数据库，例如， 可以将本题的初始布局和目标布局以矩阵形式表示为： 2 8 3 1 2 3 S0= 1 6 0 Sg= 8 0 4 7 5 4 7 6 5 综合数据库中,存放着初始状态矩阵和目标状态矩阵以及变换过程中的中间矩阵。 在建立了规则集和综合数据库后，就可以按照产生式规则进行状态变换，实现推理求 解。在进行推理时，可能会有多条产生式规则的条件部分和综合数据库中的已有事实相符， 这样就有可能激活多条规则。 究竟采用哪一条规则作为启用规则， 这就是冲突解决策略问题。 解决冲突的策略有专一性排序、规则顺序等多种，也可以使用一些启发性的信息，根据具体 问题选择。在本题中，我们采用一个启发式函数 h(x)，它表示节点 x 所对应的棋盘中与目标 节点对应的棋盘中棋子位置不同的个数。这里，综合数据库中的初始状态矩阵，能满足规则 R1、R2、R4 的条件，所以有三条匹配规则。利用启发式函数决定哪一条规则为启用规则。 因为规则 R4 的启发式函数值 h(x)=5，规则 R1 的 h(x)=6，规则 R2 的 h(x)=7，也就是说，规 则 R4 所得到的新状态与目标状态差距最小，所以启用规则 R4，依此类推，可以得到到达 目标状态的规则执行序列如下： R4，R1，R2，R2，R1，R4，R3 其执行过程如图 2.19 所示。 2．13 解：设综合数据库中包含了已访问过的城市名的列表、未访问过的城市名的 列表和各城市间的距离表。初始时刻，已访问过的城市名列表中只有 A，未访问过的城市名 列表中有 B、C、D、E。定义如下谓词： not—visit(x)：表示未访问过城市 x； visit—all()：表示已无未访问过的城市； goto(x)：表示去访问城市 x，并将 x 加入已访问的城市列表中，从未访问过的城市 列表中删除它。则建立如下的产生式规则： R1：not—visit(x)→goto(x) R2：visit—all()→goto(A) 当未访问过的城市列表不为空时，激活规则 R1；否则，激活规则 R2。 如果未访问过的城市列表中的城市个数多于一个时，这时规则 R1 的实例就不止一 个。例如，在刚开始时，就有四条规则(分别针对 x=A，x=B，x=C，x=D)被激活，这时可以 根据综合数据库中的城市间距离，构造一个启发式函数 h(x)来解决规则冲突，决定某一条规 则为启用规则。 例如， 在刚开始从 A 出发时， 决定下一访问城市， 由于 B 与 A 的距离最近， 所以 x：=B。依此类推，推销员走的路径为 E、D、C。这时未访问过的城市列表中 S 经为 空，规则 R2 被激活，返回城市 A。 2．15 答：从谓词逻辑表示法来看，一个基本网元相当于一组一阶二元谓词。因为三 元组(节点 1，弧，节点 2)可写成 P(个体 1，个体 2)。其中，个体 1、个体 2 分别对应节点 1、 节点 2，而弧及其上标注的节点 1 与节点 2 的关系由谓词 P 来体现。 产生式表示法以一条产生式规则作为知识的单位，各条产生式规则之间没有直接 的联系。而语义网络则不同，它不仅将基本网元视做一种知识的单位，而且各个基本网元之 间又是相互联系的。人脑的记忆便是由存储大量的这种基本网元来体现的。 2．16 解：(1)本知识涉及的对象有 3 个：鸟、鸽子、信鸽。信鸽是一种鸽子，除了其本身的 属性外，理应具有鸽子的一般特性。而鸽子又是一种鸟，鸟所具有的属性它也具有。 (2)信鸽与鸽子之间是一种类属关系，鸽子和鸟之间也是一种类属关系，它们都可以用 AKO 表示。 (3)整理各对象节点之间的属性，使上层节点所具有的属性不再在下层节点中标出。 (4)将各对象作为一个节点， 而它们之间的关系作为弧， 则得到如图 2． 所示的语义网络。 20 2．17 解：(1)这是一个带有全称量词的语义网络，如图 2．21 所示。其中，s 是全称变量， 代表任一个学生；h 是存在变量，表示某次拥有；bs 也是存在量词，代表多本书；s、h、bs 及其语义联系构成一个子网，是一个子空间，表示每个学生都拥有多本书；节点 g 代表该子 空间，由弧 F 指向其所代表的子空间的具体形式，弧?指出 s 是一个全称变量。节点 GS 代 表整个空间。 (2)根据题意得到如图 2．22 所示的语义网络。这里需要指出的是，设立“讲课”很有必要， 由它向外引出的弧不仅可以指出讲课的主体，而且可以指出讲课的起止时间。 (3)根据题意，这是一个有合取和析取的语义网络，如图 2．23 所示。 (4)此题较简单，根据题意，其语义网络如图 2．24 所示 2．18 解：按照语义网络知识表示步骤，首先进行解题分析： (1)问题涉及的对象有动物、偶蹄动物、哺乳动物、猪、羊、野猪、山羊、绵羊共 8 个对象。 各对象的属性可以根据常识给出，不过，这里特别给出了山羊有角、绵羊能产羊 毛的特点。 (2)羊和猪与偶蹄动物、哺乳动物间是类属关系，偶蹄动物、哺乳动物与动物间也 是类属关系，野猪与猪，山羊、绵羊与羊之间都是类属关系，可用 AKO 表示。 (3)根据信息继承性原则，各上层节点的属性下层都具有，在下层都不再标出，以 避免属性信息的重复。 (4)根据以上分析，本题共涉及 8 个对象，各对象的属性以及它们之间的关系已在 上面指出，所以本题的语义网络应是由 8 个节点构成的有向图，弧上的标注以及各节 点的标注如上所述。语义网络图如图 2．25 所示。 2． 解： 26 用状态空间法进行表示。 根据状态空间表示问题的步骤， 问题求解如下： 第一步，定义问题状态的描述形式。 设 Sk=(Nx，Ny，C)表示修道士和野人在河的左岸的状态。其中，Nx 表示修道士 在左岸的实际人数，Ny 表示野人在左岸的实际人数，C 用来指示船是否在左岸(C=1 表 示在左岸，C=0 表示不在左岸)。 第二步，用所定义的状态描述形式把问题的所有可能状态都表示出来，并确定出 问题的初始状态集和目标状态集。 对于状态 Sk=(Nx，Ny，C)来说，由于 Nx、Ny 的取值有 0、1、2、3 四种可能，C 的取值有 0 和 1 两种可能，所以，本问题所有可能的状态共有 4*4*2=32 种。各状态的 形式描述如下： So=(3，3，1)，S1=(3，2，1)，S2=(3，1，1)，S3=(3，0，1)， S4=(3，3，0)，S5=(3，2，0)，S6=(3，1，0)，S7=(3，0，0)， S8=(2，3，1)，S9=(2，2，1)，S10=(2，1，1)，S11=(2，0，1)， S12=(2，3，0)，S13=(2，2，0)，S14=(2，1，0)，S15=(2，0，0) S16=(1，3，1)，S17=(1，2，1)，S18=(1，1，1)，S19=(1，0，1)， S20=(1，3，0)，S21=(1，2，0)，S22=(1，1，0)，S23=(1，0，0)， S24=(0，3，1)，S25=(0，2，1)，S26=(0，1，1)，S27=(0，0，1)， S28=(0，3，0)，S29=(0，2，0)，S30=(0，1，0)，S3l=(0，0，0)。 在这些状态中，由于有安全约束条件——任何岸边野人的数量都不得超过传教士 的数量(即 Nx≥Ny)，所以只有 20 个状态是合法的，像(1，2，1)、(1，3，1)和(2，3， 1)等都是不合法的状态。而由于这些不合法状态的存在，又会导致某些合法状态是不可 到达的。这样，此问题总共只有 16 种可到达的合法状态，以下划线表示。 问题的初始状态集为：S=｛S0｝={(3，3，1)}，目标状态集为：G={S31}={(0，0，0)} 第三步，定义一组用于状态变换的算符 F。 定义算符 L （i,j)表示划船将 i 个传教士和 j 个野人送到右岸的操作； 算符 R(i,j)表示 划船从右岸将 i 个传教士和 j 个野人带回左岸的操作。 由于过河的船每次最多载两个人， 所以，i 十 j≤2，这样定义的算符组 F 中只可能有如下 10 个算符： F： L(1，0)，L(2，0)，L(1，1)，L(0，1)，L(0，2) R(1，0)，R(2，0)，R(1，1)，R(0，1)，R(0，2) 至此， 该问题的状态空间(S， G)构造完成。 F， 这就完成了对问题的状态空间表示。 为了求解该问题，根据该状态空间的 16 种可到达合法状态和 10 种算符，构造它 的状态转换图，如图 2．26 所示。 在图 2.26 所示的状态空间图中,每个节点只能取 L、R 操作之一，这取决于变量 C 的取值，即船是在左岸还是在右岸。若船在左岸(即 C=1)，则只能取 L 操作，若船在右 岸，则只能取 R 操作。 从初始节点(3，3，1)(状态 So)到目标节点(0，0，0)(状态 S31)的任何一条通路 都是问题的一个解。其中： L(1，1)，R(1，0)，L(0，2)，R(0，1)，L(2，0)，R(1，1)，L(2，0)，R(0，1)， L(0，2)，R(0，1)，L(0，2) 是算符最少的解之一。 2．27 解：用状态空间法进行表示。根据状态空间表示问题的步骤，问题求解如下： 第一步，定义问题状态的描述形式。 以四元组 Sk=(f，h，j，m)作为状态变量，表示农夫、狐狸、鸡和小米是否在 左岸。每个元素可有两个取值 1 或 0，1 表示在左岸，0 表示不在左岸。 第二步，用所定义的状态变量把问题的所有可能状态都表示出来，并确定出 问题的初始状态集和目标状态集。 由于状态变量有 4 个元素，每个元素有 2 种取值，所以共有 16 种可能状态。 各状态的形式描述如下： So =(1，1，1，1)，Sl =(1，1，1，0)，S2 =(1，1，0，1)，S3 =(1，1，0，0)， S4 =(1，0，1，1)，S5 =(1，0，1，0)，S6 =(1，0，0，1)，S7 =(1，0，0，0)， S8 =(0，1，1，1)，S9 =(0，1，1，0)，S10=(0，1，0，1)，S11=(0，1，0，0)， S12=(0，0，1，1)，S13=(0，0，1，0)，S14=(0，0，0，1)，S15=(0，0，0，0)。 问题的初始状态集为：S={S0}={(1，1，1，1)}， 目标状态集为：G={S15}={(0，0，0，0)}。 第三步，定义一组用于状态变换的算符 F。 由于船上除了农夫外，每次只能载狐狸、鸡和小米中的一样，且每次农夫都必 须在船上，故定义算符如下： L(f，j)表示从左岸将第 j 样东西送到右岸(j=1 表示狐狸，j=2 表示鸡，j=3 表示 小米，j=0 表示除农夫外不载任何东西)，f 表示农夫始终在船上。 R(f，j)表示从右岸将第 j 样东西带回左岸。 所以，所定义的算符组 F 中可能有 8 种算符： F：L(f，0)，L(f，1)，L(f，2)，I(f，3)，R(f，0)，R(f，1)， R(f，2)，R(f，3)。 这里要指出的是，操作算符中的 f 可以不要，也就是说，完全可以把操作算符 定义成 L(j)和 R(j)。这里加上 f 是为了表示农夫总是在船上划船。 至此，该问题的状态空间(S，F，G)构造完成。这就完成了对问题的状态空间 表示。 为了求解该问题，根据该状态空间的 16 种状态和 8 种算符，构造它的状态转 换图，如图 2．27 所示。 在图 2．27 所示的状态转换图中，每个节点只能取 L、R 操作之一，这取决于状态变量 中第一个元素 f 的取值。若 f=1，表明农夫在左岸，船也就在左岸(因为农夫始终和船相 随)，这时只能取 L 操作。若 f=0，表明船在右岸，则只能取 R 操作。从初始节点(1，1， 1，1)(状态 So)到目标节点(0，0，0，0)(状态 S15)的任何一条通路都是问题的一个解。 其中： L(f，2)，R(f，0)，L(f，3)，R(f，2)，L(f，1)，R(f，0)，L(f，2)是算符最少的解 之一，如图 2．28 所示。 2．28 解：根据状态空间表示问题的步骤，问题求解如下： (1)定义状态变量。 设 Sk=(w，x，y，z)为状态变量。w 表示猴子在地面上的位置，x 表示猴子是否在 箱子顶上(x=1 表示在箱子顶上， x=0 表示不在箱子顶上)， 表示箱子在地面上的位置， y z 表示猴子是否摘到香蕉(z=1 表示摘到香蕉，z=0 表示没有摘到香蕉)， 猴子和箱子在地 面的位置可能是 a，b，c。 (2)列出所有状态，确定出初始状态集和目标状态集。 由于 w、y 的取值可能是 a、b、c，而 x、z 的取值可能是 0 或 1，所以，这个问题 共有 3* 2* 3*2=36 个状态。如(a，0，c，0)，(a，0，b，0)，(a，0，a，0)，…，(b，0， b，0)，(b，1，b，0)(b，1，b，1)，这里就不一一列出了，状态空间图这里也不画出了。 根据题意，在这 36 种状态中，初始状态 So=(a，0，c，0)，目标状态 Sg=(b，1，b，1)。 (3)定义一组用于状态变换的算符 F，实现状态间的转换。 定义操作算符组如下： F：①goto(x，y)：猴子从 x 处走到 y 处。 ②pushbox(x，y)：猴子将箱子从 x 处推到 y 处。 ③climbbox：猴子爬到箱子顶上。 ④grasp：猴子摘下香蕉。 至此，该问题的状态空间(So，F，Sg)构造完成。 可以从一个含有 36 个状态的状态空间图(其中有很多状态是不必要的)中找到一条 从初始状态到目标状态的最短路径,其所对应的操作符序列如下： goto（a，c） ，pushbox（c，b） ，climbbox，grasp 它就是该问题的解。