《人工智能考试重点总结42》由会员分享，可在线阅读，更多相关《人工智能考试重点总结42（60页珍藏版）》请在金锄头文库上搜索。
1、状态空间表示法例：设N个传教士带领N个野人划船渡河，且为安全起见，渡河需遵循两个约束：（1）船上的人数不得超过载重限量，设为K个人；（2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士数目。应如何规划渡河方案？ 为便于理解状态空间表示法，可简化该问题到一个特例：N=3，K=2。 解解：首先选取取描述问题状状态的方法。在在这个问题中中，需要考虑虑两岸的修道道士人数和野野人数，还需需要考虑船在在左岸还是在在右岸。从而而可用一个三三元组来表示示状态 S=(m, c, b)其中，m表示左左岸的修道士士人数，c表示左岸的的野人数，bb表示左岸的的船数。 右岸岸的状态可由由下式确定： 右
2、岸岸修道士数 m=33-m 右岸岸野人数 c=3-c 右岸岸船数 b=1-b 在这这种表示方式式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因因此，共有4442=32种状状态。 这32种状态并并非全有意义义，除去不合合法状态和修修道士被野人人吃掉的状态态，有意义的的状态只有116种： S0=(3, 3, 1) S1=(3, 22, 1) S22=(3, 1, 1) SS3=(2, 2, 11) S4=(1, 1, 1) S5=(0, 33, 1) S66=(0, 2, 1) SS7=(0, 1, 11) S8=(3, 2, 0) S9=(3, 11, 0) S110=(3, 0,
3、 00) SS11=(22, 2, 0) S12=(1, 11,0) S133=(0, 2, 0) S114=(0, 1, 00) SS15=(00, 0, 0)有了这些状态，还还需要考虑可可进行的操作作。 操作是是指用船把修修道士或野人人从河的左岸岸运到右岸，或或从河的右岸岸运到左岸。 每个操操作都应当满满足如下条件件： 一是船船至少有一个个人（m或c）操作，离离开岸边的mm和c的减少数目目应该等于到到达岸边的mm和c的增加数目目； 二是每每次操作船上上人数不得超超过2个； 三是操操作应保证不不产生非法状状态。 因此，操操作应由条件件部分和动作作部分： 条件：只有当其条条件具备时才才能使用
4、动作：刻划了应用用此操作所产产生的结果。 操作的表示： 用符号号Pij表示从从左岸到右岸岸的运人操作作 用符号号Qij表示从从右岸到左岸岸的操作其中： i表示示船上的修道道士人数 j表示示船上的野人人数操作集 本问题题有10种操作可可供选择： F=P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20 下面以以P01和Q01为例来来说明这些操操作的条件和和动作。 操作符符号 条条件 动作 P011 bb=1, mm=0或3, c1 b=0, c=c-1 Q011 b=0, m=0或3，c2 b=11, c=cc+1 于是，从初始状状态出发，可可画出该问题
5、题的状态空间间有向图，见见图1.1。 二阶梵塔问题n 设用Sk=(SSk0,Skk1)表示问问题的状态，Sk0表示金片A所在钢针号，Sk1表示金片B所在钢针号，全部可能的状态有九种：S0=(1,11), S11=(1,22), S22=(1,33) S3=(2,11),S4=(2,2), S5=(2,3) S6=(3,11), S77=(3,22),S8=(3,3)问题的初始状态态集合为S=S0 目标标状态集合为为G=S44, S8 初始状态S0和和目标状态SS4、S8如图所示示 操作作分别用A(i, j)和B(i, j)表示 A(i, j)表示把金片片A从第i号钢针移到到j号钢针上； B(i
6、, j)表示把金片片B从第i号钢针一到到第j号钢针上。共共有12种操作，它它们分别是： AA(1, 22) AA(1, 33) AA(2, 11) AA(2, 33) AA(3, 11) AA(3, 22) BB(1, 22) BB(1, 33) B(2, 1) B(2, 3) B(3, 1) B(3, 2) 根据上上述9种可能的状状态和12种操作，可可构成二阶梵梵塔问题的状状态空间图，如如下图所示。 s-指指示初始状态态节点；G-指示示搜索图； OPEN-用于存存放待扩展节节点的表； CLOSEE-用于于存放已扩展展节点的表； FIRSTT(OPENN)-指指示取OPEEN表首的节节点作为当
7、前前要被扩展的的节点n； REMOVVE(n,OOPEN)-将节点点n从OPEEN表中删去去； ADD(nn,CLOSSE)-把节点n加加入到CLOOSE表中； EXPANND(n)-扩展节节点n。 深度优先宽度优先在33的方格格棋盘上，分分别放置了表表有数字1、2、3、4、5、6、7、8的八张牌，初初始状态S00，目标状态态Sg，如下图图所示。可以以使用的操作作有 空格格左移，空格格上移，空格格右移，空格格下移即只允许把位于于空格左、上上、右、下方方的牌移入空空格。要求应应用宽度优先先和深度优先先搜索策略寻寻找从初始状状态到目标状状态的解路径径。 评价函数的的格式:f(n)=g(n) + h
8、(n) f(n): 评价函函数 h(n): 启发函函数 g*(n): 从初始始结点s到结点n的最短路径径的耗散值； h*(n): 从从结点n到目标结点点g的最短路径径的耗散值； f*(n)=g*(n)+hh*(n): 从初始结结点s经过结点n到目标结点点g的最短路径径的耗散值； g(nn)、h(nn)、f(nn)分别是g*(n)、h*(n)、ff*(n)的的估计值。 在A算法法中，如果满满足条件：h(n)h*(n) 则A算算法称为A*算法。解树的耗散值可可按如下规则则计算： (1)若n为终止节点点，则其代价价h(n)=0； (2)若n为或节点，且且子节点为nn1, n22, ,nk，则n的代价
9、为：其中，c(n, ni)是是节点n到其子节点点ni的边代价价。 (3)若n为与节点，且且子节点为nn1, n22, ,nk，则n的代价可用用和代价法或或最大代价法法。 若用和和代价法，则则其计算公式式为： 若用最最大代价法，则则其计算公式式为： (4)若n是端节点，但但又不是终止止节点，则nn不可扩展，其其代价定义为为h(n)=。 (5)根节点的的代价即为解解树的代价。 知识表示方法法部分参考答答案 2.8 设有如如下语句，请请用相应的谓谓词公式分别别把他们表示示出来：s(1) 有的人人喜欢梅花，有有的人喜欢菊菊花，有的人人既喜欢梅花花又喜欢菊花花 。解：定义谓词ddP(x)：x是是人L(x
10、,y)：x喜欢y其中，y的个体体域是梅花花，菊花。将知识用谓词表表示为：(x )(P(x)L(x, 梅花)L(x, 菊花)L(x, 梅花)L(x, 菊花)(2) 有人每每天下午都去去打篮球。解：定义谓词P(x)：x是是人B(x)：x打打篮球A(y)：y是是下午将知识用谓词表表示为：a(x )(y) (A(yy)B(x)P(x)(3) 新型计计算机速度又又快，存储容容量又大。解：定义谓词NC(x)：xx是新型计算算机F(x)：x速速度快 B(x)：x容容量大将知识用谓词表表示为：(x) (NCC(x)F(x)B(x)(4) 不是每每个计算机系系的学生都喜喜欢在计算机机上编程序。解：定义谓词S(x
11、)：x是是计算机系学学生L(x, prragrammming)：x喜欢编编程序U(x,commputerr)：x使用用计算机将知识用谓词表表示为： (x) (S(x)L(x, pragrramminng)U(x,ccomputter)(5) 凡是喜喜欢编程序的的人都喜欢计计算机。解：定义谓词P(x)：x是是人L(x, y)：x喜欢yy将知识用谓词表表示为：(x) (P(x)L(x,ppragraammingg)L(x, compuuter)2.11 用谓谓词表示法求求解修道士和和野人问题。在在河的北岸有有三个修道士士、三个野人人和一条船，修修道士们想用用这条船将所所有的人都运运过河去，但但要受
12、到以下下条件限制：(1) 修道士士和野人都会会划船，但船船一次只能装装运两个人。(2) 在任何何岸边，野人人数不能超过过修道士，否否则修道士会会被野人吃掉掉。假定野人愿意服服从任何一种种过河安排，请请规划出一种种确保修道士士安全的过河河方案。要求求写出所用谓谓词的定义、功功能及变量的的个体域。解：（1）定义义谓词先定义修道士和和野人人数关关系的谓词：G(x,y,SS)： 在状状态S下x大大于yGE(x,y,S)：在状状态S下x大大于或等于yy其中，x,y分分别代表修道道士人数和野野人数，他们们的个体域均均为0,11,2,3。再定义船所在岸岸的谓词和修修道士不在该该岸上的谓词词：Boat(z,S
13、)：状态态S下船在zz岸EZ(x,S)： 状态SS下x等于00，即修道士士不在该岸上上其中，z的个体体域是L,R，L表表示左岸，RR表示右岸。 再定义义安全性谓词词： Saffety(zz,x,y,S)(G(x,0,S)GE(x,y,S)(EZ(x,S)其中，z,x,y的含义同同上。该谓词词的含义是：状态S下，在在z岸，保证证修道士安全全，当且仅当当修道士不在在该岸上，或或者修道士在在该岸上，但但人数超过野野人数。该谓谓词同时也描描述了相应的的状态。再定义描述过河河方案的谓词词：L-R(x, x1, yy, y1,S)：x11个修道士和和y1个野人人渡船从河的的左岸到河的的右岸条件：Safeety(L,x-x1,y-y1,S)Safetty(R,33-x+x11,3-y+y1,S)Boat(L,S)动作：Safeety(L,x-x1,y-y1,S)Saf
