人工智能答案 第二章

树式搜索：a,盲目搜索（穷举式搜索）{广度优先 深度优先}b,启发式搜索{全局择优、局部择优，分支界限、最近择优、A算法、A*算法}线式搜索：ab启发式搜索，即为有导向的搜索，利用“启发性信息”引导搜索。所谓的启是用来估计搜索树上节点与目标节点接近程度的一种函数，通常即为h(x)。OPENCLOSED表：动态数据结构，记录考察过得节点。深度优先搜索算法的特点是①般不能保证找到最优解；②当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制；③法与问题无关，具有通用性；④于图搜索方法广度优先搜索算法的特点是② 问题有解时，一定能找到解；②当问题为单位耗散值，并且问题有解时，一定能找到最优解；③效率低；④方法与问题无关，具有通用性；⑤属于图搜索方法。fwsgf0101初始状态S0：(0,0,0,0)目标状态：(1,1,1,1)不合法的状态:(1,0,0,*),(1,*,0,0),(0,1,1,*),(0,*,1,1)操作集F={P1，P2，P3，P4，Q1，Q2，Q3，Q4}操作符条件操作符条件动作ssq1gf=0，w＝0q2f=1，s＝1，f=0，s＝0q3sf=0，g＝0p1f=0，w=0，sgf=1，w=1p2f=0，s=0，f=1，s=1p3f=0，g=0，wsf=1，g=1q0f=1，sgwf=0(0,0,0,0)(0,0,0,0)q2p2(1,0,1,0)q0p3(0,0,1,0)(1,0,1,1)q2(0,0,0,1)q1p1q3q2p2p2p3q2p2q0p2(1,1,1,0)(0,1,0,0)(1,1,0,1)(0,1,0,1)(1,1,1,1)q3q2方案有两种：p2q0p3q2p2q0p2p2→q0→p1→q2→p3→q07题和9题参考第8题。8.琴键翻动（供参考(q0,q1,q20，关状态为1，全部可能的状态为：Q0=(0,0,0);Q1=(0,0,1);Q2=(0,1,0)Q3=(0,1,1);Q4=(1,0,0);Q5=(1,0,1)Q6=(1,1,0);Q7=(1,1,1)。F＝{a,b,aq0bq1cq2问题的状态空间为<{Q5},{Q0Q7},{a,b,c}>问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5Q73Q5Q03a（（0，0，0）（1，0，0）cb（0，0，1）cb（1，1，0）aa（1，0，1）b（0，1，0）cbc（1，1，1） a10. 设用二元组(S,S表示问题的状态,SA所在的杆A B A号,SB所在的杆号,这样,9种,可B表示如下：二阶梵塔的全部状态这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)及表示：A(i,j)Aij号杆上;B(i,j)Bij12个操作，它们分别是：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)这样由题意,问题的初始状态为(1,1),目标状态为(3,3),则二阶梵塔 问 题 可 用 状 态 图 表 示 912种操作,二阶梵塔问题的状态空间图如图：三阶同理可得。11代价树如下图所示：分别给出宽度优先及深度优先搜索策略下的搜索过程和解。其中，F、I、J、L是目标节点。A32BC2 1 5 2DA32BC2 1 5 2DEFG132331HIJKL M3 2OP－﹥G－﹥E－﹥D－﹥M－﹥解为：A－﹥B－﹥E－﹥J深度优先搜索过程为：A－﹥C－﹥G－﹥M－﹥P－﹥O－﹥L，G（L）=7，解为：A－﹥C－﹥G－﹥L1213.用极小极大方法求N的最佳走步。N4 A4 A1B44144CD469-1-214346441-46165425-1-2341-4142最佳路径为N-〉A-〉B-〉C-〉D≥2NA≥2NA≤2B≥2C≥4≥1EF≤2≤-1≤-2H≤3IJ≤1K≤-5L≤1≤3N≤2N323-1-214346541-5617 5326习题习题14博弈树于规则的演绎推理。求下列谓词公式的子句集(1)xy(P(x,y)Q(x,y))解：去掉存在量词变为：P(a,b)Q(a,b)变成子句集{P(a,b),Q(a,b)}(2)xy(P(x,y)Q(x,y))解：去掉蕴涵符号变为：xy(¬P(x,y)Q(x,y))去掉全称量词变为：¬P(x,y)Q(x,y)变成子句集{¬P(x,y)Q(x,y)}(3)x{P(x)y[zQ(x,z)zR(x,y,z)]}P(x)Q(x,z)R(x,f(x),z)(4)xyzuvw(P(x,y,z,y,v,Q(x,y,z,y,v,R(x,y,z,u,v,{p(a,y,f(y),y,v,g(y,v))Q(a,y,f(y),y,v,g(y,v)),p(a,x,f(x),x,z,g(x,z))R(a,x,f(x),h(x),z,g(x,z))}试判断下列子句集中哪些是不可满足的（1）使用删除策略（2）归结用合一算法求下列公式集的最一般合一。（1）W={Q(a,x),Q(y,b)}最一般合一为:{a/y,b/y}（2）W{Q(x，y，z)，Q(u，h(v,v)，u)}最一般合一为：{z/u,h(v,v)/y,z/x}或{x/u,h(v,v)/y,x/z}是否可肯定是F(1) F (x)(P(x)(Q(x)∧R(x))1F (x)(P(x)∧S(x)2G (x)(S(x)∧R(x))证明：利用归结反演法，先证明F1∨F2∨¬G是不可满足的。求子句集：F1(1)¬P(x)∨Q(x)F1(2)¬P(z)∨R(z)SF2(3)P(a)F2(4)S(a)(¬G)(5)¬S(y)∨¬R(y)(¬G)利用归结原理进行归结(6)R(a) [(2),(3),σ1={a/z}](7)¬R(a) [(4),(5),σ2={a/y}](8)Nil [(6),(7)]SGF1F2的逻辑结果。(x)((y)P(x，y)∧Q(y))(x)((y)P(x，y)∧Q(y))(y)（R(y)¬(x)R(x)(x)P(x，y)¬Q(y))GG证明：利用归结反演法证明，先证明F¬G、¬G化成子句集：(1)¬P(x，y)∨¬Q(y)∨R(f(x))(2)¬P(v，u)∨¬Q(u)∨T(v,f(u))Q(b)P(a，b)(5)¬R(z)对上述式子进行归结：（6）¬P(x，b)∨R(f(x)) （7）R(f(x)) （8）NIL （5）和{f(x)/z}所以G的逻辑结论。（3）F1F2F3

(x)(A(x)∧¬B(x)(y)(D(x，y)∧C(y)))(x)(E(x)∧A(x)∧(y)(D(x，y)E(y)))(x)(E(x)¬B(x))G (x)(E(x)∧C(x))证明：利用归结反演法证明，先证明F1F2F3¬G是不可满足的。求子句集：F1：（1）¬A(x)∨B(x)∨D(x，w)（2）¬A(y)∨B(y)∨C(t)F2（3）E(a)（4）A(a)（5）¬D(a，z)∨E(z)F3（6）¬E(u)∨¬B(u)¬G（7）¬E(v)∨¬C(v)对子句集进行归结：（8）B(a) （）{a/u}]（9）C(a) （）{a/v}]（10B(a)∨C(t) [2）{a/y}]（1）C(a) [810{a/t}]（12Nil 6用归结原理证明下述推理正确。已知：狗都会吠叫和咬人。结论：松狮是吵人的。松狮是狗。结论：松狮是吵人的。B(x):x将上述各语句翻译成谓词公式：F1:x(D(x)(B(x)F(x)))F2:x(F(x)N(x))G:x(G(x)N(x))F3:G:x(G(x)N(x))利用归结反演法，先证明F1F2F3¬G是不可满足的。F1F2F3¬G的子句集为（1）¬D(x)B(x)（2）¬D(y)F(y)（3）¬F(z)N(z)（4）¬G(u)D(u)（5）G（a）进行归结得：（7B（） （（{a/x}]（8F（） （（{a/y}]（9）F(a) （（{a/z}]（1）NIL （（]得证。Sam、ClydeOscarSam是粉红色的；Clyde是灰色的且喜欢Oscar；Oscar是粉红色或者是灰色（但不是两种颜色）且喜欢用归结反演方法证明一只灰色大象喜欢一只粉红色大象。解首先定义如下谓词：Pink(x)表示x是粉红色的大象。Gray(x)x是灰色的大象。Likes（x，y）表示喜欢y。已知条件可以表示成如下谓词公式：Pink（Sam）Gray（Clyde）Likes（Clyde，Oscar）3GraOscaPinOsca）Like（Osca，Sa）设求证的公式为：G：xy（Gray（x）Pink（y）Likes（x，y）把其否定化为子句形式Pink（Sam）Gray（Clyde）Likes（Clyde，Oscar）Gray（Oscar）Pink（Oscar）Likes（Oscar，Sam）¬Gray（x）¬Pink（y）¬Likes（x，y）进行归结：¬Gra（¬Like（xSa） （（）{Sam/y}Gra（Osca） 57{Oscar/x}Pink(Oscar) （）Grax¬Like（Osca） 69）{Oscar/y}¬Like（Osca，Sa） （10）{Oscar/y}（12Nil 31）{Sam/y}8张某被盗，公安局派五个侦察员去调查，研究案情时，侦察员ABC侦察员DE解：定义谓词用P（x）表示x作案，a，b，c，d得话可用谓词公式表示为（1） P（a）∨P（b）（2） P（b）∨P（c）（3）P（c）∨P（d）（4）¬P（a）∨¬P（c）（5）¬P（b）∨¬P（d）要求的公式为G：xP(x) (即存在x，x是罪)将其化为否定形式再析取一个辅助谓词PA(x) （6）P（x）∨PA（x）对上面式子进行归结得（7）¬P（d）∨P（c）(2)(5