人工智能答案第二章

1.树式搜索：a,盲目搜索（穷举式搜索）{广度优先深度优先}b,启发式搜索{全局择优、局部择优，分支界限、最近择优、A算法、A*算法}线式搜索：a,盲目搜索{随即碰撞、回溯穷举}b,启发式搜索{不回溯、智能回溯}2.盲目搜索，也就是无导向搜索。在搜索过程中，没有任何背景知识作指导不考虑任何与解有关的信息，随机的或按预定顺序机械地搜索，并判断是否为所求的解，直到找到解或是证明问题无解为止。盲目搜索效率太低，一般只适用于求解比较简单的问题。3.启发式搜索，即为有导向的搜索，利用“启发性信息”引导搜索。所谓的启发性信息就是与问题有关的有利于找到问题解的信息或知识。启发函数，是用来估计搜索树上节点与目标节点接近程度的一种函数，通常即为h(x)。4.OPEN表：动态数据结构，登记记录当前待考察的节点。CLOSED表：动态数据结构，记录考察过得节点。5.深度优先搜索算法的特点是①般不能保证找到最优解；②当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制；③法与问题无关，具有通用性；④于图搜索方法广度优先搜索算法的特点是②
问题有解时，一定能找到解；②当问题为单位耗散值，并且问题有解时，一定能找到最优解；③效率低；④方法与问题无关，具有通用性；⑤属于图搜索方法。6.解：用四元组(f、w、s、g)表示状态，f代表农夫，w代表狼，s代表羊，g代表菜，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。初始状态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}操作符条件动作p1f=0，w=0，s和g相异f=1，w=1p2f=0，s=0，f=1，s=1p3f=0，g=0，w和s相异f=1，g=1q0f=1，s和g相异，w和s相异f=0q1f=1，w＝1，s和g相异f=0，w＝0q2f=1，s＝1，f=0，s＝0q3f=1，g＝1，w和s相异f=0，g＝0(0,0,0,0)(1,0,1,0)p2q2(0,0,1,0)(1,1,1,0)p1q1(1,0,1,1)(0,0,0,1)q0p3q3(0,1,0,0)q2p2(1,1,0,1)p3q3q2p2p2q2(0,1,0,1)(1,1,1,1)p2q2q0方案有两种：p2→q0→p3→q2→p2→q0→p2p2→q0→p1→q2→p3→q0→p27题和9题参考第8题。8.琴键翻动（供参考）解：引入一个三元组(q0,q1,q2)来描述总状态，开状态为0，关状态为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,c}a:把第一个琴键q0翻转一次b:把第二个琴键q1翻转一次c:把第三个琴键q2翻转一次问题的状态空间为{Q5},{Q0Q7},{a,b,c}问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbc10.设用二元组(SA,SB)表示问题的状态,SA表示金盘A所在的杆号,SB表示金盘B所在的杆号,这样,全部可能的状态有9种,可表示如下：二阶梵塔的全部状态这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘从第i号杆移到第j号杆上;B(i,j)表示把B盘从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是：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),则二阶梵塔问题可用状态图表示为由这9种可能的状态和12种操作,二阶梵塔问题的状态空间图如图：三阶同理可得。11代价树如下图所示：分别给出宽度优先及深度优先搜索策略下的搜索过程和解。其中，F、I、J、L是目标节点。宽度优先搜索过程：A－﹥C－﹥B－﹥G－﹥E－﹥D－﹥M－﹥J，G（J）=6，解为：A－﹥B－﹥E－﹥J深度优先搜索过程为：A－﹥C－﹥G－﹥M－﹥P－﹥O－﹥L，G（L）=7，解为：A－﹥C－﹥G－﹥L1213.用极小极大方法求N的最佳走步。469-1-214346441-46165425N4-1-2341-41424414414ABCD最佳路径为N-〉A-〉B-〉C-〉DABCDEFGHIJKLMOP3221521323313214.1.基于谓词逻辑的机器推理方法：自然演绎推理，归结演绎推理，基于规则的演绎推理。2.求下列谓词公式的子句集(1)xy(P(x,y)Q(x,y))解：去掉存在量词变为：P(a,b)Q(a,b)变成子句集{P(a,b),Q(a,b)}(2)xy(P(x,y)Q(x,y))解：去掉蕴涵符号变为：xy(¬P(x,y)Q(x,y))去掉全称量词变为：¬P(x,y)Q(x,y)变成子句集{¬P(x,y)Q(x,y)}习题14博弈树-22-1334641-56173145NABCEFHIJKLN62N335≥4≤2≤-1≤-2≤3≤1≥2≤2≤-5≥1≥2≤1≤3≤2(3){()[(,)(,,)]}xPxyzQxzzRxyz()(,)(,(),)PxQxzRxfxz(4)((,,,,,)(,,,,,)(,,,,,))xyzuvwPxyzyvwQxyzyvwRxyzuvw{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))}3.试判断下列子句集中哪些是不可满足的（1）使用删除策略（2）归结4.用合一算法求下列公式集的最一般合一。（1）W={Q(a,x),Q(y,b)}最一般合一为:{a/y,b/y}（2）{()((,))}WQxyzQuhvvu，，，，，最一般合一为：{z/u,h(v,v)/y,z/x}或{x/u,h(v,v)/y,x/z}5.用归结原理证明，G是否可肯定是F的逻辑结果。(1)F1(x)(P(x)(Q(x)∧R(x))F2(x)(P(x)∧S(x)G(x)(S(x)∧R(x))证明：利用归结反演法，先证明F1∨F2∨¬G是不可满足的。求子句集：(1)¬P(x)∨Q(x)(2)¬P(z)∨R(z)(3)P(a)(4)S(a)(5)¬S(y)∨¬R(y)(¬G)SF1F2利用归结原理进行归结(6)R(a)[(2),(3),σ1={a/z}](7)¬R(a)[(4),(5),σ2={a/y}](8)Nil[(6),(7)]所以S是不可满足得，从而G是F1和F2的逻辑结果。（2）F(x)((y)P(x，y)∧Q(y))(y)（R(y)∧T(x,y)））G¬(x)R(x)(x)(y)P(x，y)¬Q(y))证明：利用归结反演法证明，先证明F¬G是不可满足的。把F、¬G化成子句集：(1)¬P(x，y)∨¬Q(y)∨R(f(x))(2)¬P(v，u)∨¬Q(u)∨T(v,f(u))(3)Q(b)(4)P(a，b)(5)¬R(z)对上述式子进行归结：（6）¬P(x，b)∨R(f(x))（1）和（3）归结，{b/y}（7）R(f(x))（4）和（6）归结，{a/x}（8）NIL（5）和（7）归结{f(x)/z}所以G是F、的逻辑结论。（3）F1(x)(A(x)∧¬B(x)(y)(D(x，y)∧C(y)))F2(x)(E(x)∧A(x)∧(y)(D(x，y)E(y)))F3(x)(E(x)¬B(x))G(x)(E(x)∧C(x))证明：利用归结反演法证明，先证明F1F2F3¬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)[（3）（6）{a/u}]（9）¬C(a)[（3）（7）{a/v}]（10）B(a)∨C(t)[（2）（4）{a/y}]（11）C(a)[（8）（10）{a/t}]（12）Nil[（9）（11）]6用归结原理证明下述推理正确。已知：狗都会吠叫和咬人。任何动物吠叫时总是吵人的。松狮是狗。结论：松狮是吵人的。证明：首先定义如下谓词：B(x):x是咬人的。F(x):x是吠叫的。D(x):x是狗。N(x):x是吵人的。G(x):x是松狮。将上述各语句翻译成谓词公式：F1:x(D(x)(B(x)F(x)))F2:x(F(x)N(x))F3:x(G(x)D(x))G:x(G(x)N(x))利用归结反演法，先证明F1F2F3¬G是不可满足的。F1F2F3¬G的子句集为（1）¬D(x)B(x)（2）¬D(y)F(y)（3）¬F(z)N(z)（4）¬G(u)D(u)（5）G（a）（6）¬N（a）进行归结得：（7）B（a）[（1）（5）{a/x}]（8）F（a）[（2）（5）{a/y}]（9）¬F(a)[（3）（6）{a/z}]（10）NIL[（8）（9）]得证。7.Sam、Clyde、Oscar是三只大象，关于它们，已知如下事实：（1）Sam是粉红色的；（2）Clyde是灰色的且喜欢Oscar；（3）Oscar是粉红色或者是灰色（但不是两种颜色）且喜欢Sam。用归结反演方法证明一只灰色大象喜欢一只粉红色大象。解首先定义如下谓词：Pink(x)表示x是粉红色的大象。Gray(x)表示x是灰色的大象。Likes（x，y）表示喜欢y。已知条件可以表示成如下谓词公式：（1）Pink（Sam）（2）Gray（Clyde）Likes（Clyde，Oscar）（3）（Gray（Oscar）Pink（Oscar））Likes（Oscar，Sam）设求证的公式为：G：xy（Gray（x）Pink（y）Likes（x，y））把其否定化为子句形式(1)Pink（Sam）(2)Gray（Clyde）(3)Likes（Clyde，Oscar）(4)Gray（Oscar）Pink（Oscar）(5)Likes（Oscar，Sam）(6)¬Gray（x）¬Pink（y）¬Likes（x，y）进行归结：（7）¬Gray（x）¬Likes（x，Sam）（1）（6）归结{Sam/y}（8）¬Gray（Oscar）（5）（7）{Oscar/x}（9）Pink(Oscar)（4）（8）（10）¬Gray（x）¬Likes（x，Oscar）（6）（9）归结{Oscar/y}（11）¬Likes（Oscar，Sam）（2）（10）归结{Oscar/y}（12）Nil（3）（11）归结{Sam/y}8张某被盗，公安局派五个侦察员去调查，研究案情时，侦察员A说：“赵与钱中至少有一人作案”；侦察员B说：“钱与孙至少有一人作案”；侦察员C说：“孙与李中至少有一人作案”；侦察员D说：“赵与孙中至少有一人与此案无关”；侦察员E说：“钱与李中至少有一人与此案无关”。如果这五个侦察员说的都可信，试用消解原理求出谁是盗窃犯。解：定义谓词用P（x）表示x作案，a，b，c，d分别代表赵、钱、孙、李，则五个侦察员得话可用谓词公式表示为（1）P（a）∨P（b）（2）P（b）∨P（c）（3）P（c）∨P（d）（4