人工智能作业解答--廉师友.pptVIP

人工智能作业解答 西安电子科技大学 廉师友 习题三 6.解：用四元组(f、w、s、g)表示状态， f代表农夫，w 代表狼，s 代表羊，g 代表菜，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸 。 初始状态S0：(0,0,0,0)，目标状态Sg ：(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} 方案有两种： p2→ q0 → p3→ q2 → p2 → q0 → p2 p2→ q0 → p1→ q2 → p3→ q0→ p2 习题三 12 一棵解树由S0,A,D,t1,t2,t3组成；另一棵解树由S0,B,E,t4,t5组成。左边的解树： 按和代价： g(D)=4,g(A)=7,g(S0)=12 按最大代价： g(D)=2,g(A)=5,g(S0)=10 右边的解树： 按和代价：g(E)=2,g(B)=11,g(S0)=18按最大代价： g(E)=2,g(B)=7,g(S0)=14 按和代价计算，左边的解树为最优解树；按最大代价计算，仍然是左边的解树为最优解树。因此，左边的解树为最优解树。 习题三 14.修道士和野人问题。在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制： （1）修道士和野人都会划船，但船一次最多只能运三个人； （2）在任何岸边及船上野人数目都不得超过修道士，否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。请定义启发函数，并给出相应的有哪些信誉好的足球投注网站树。 解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述： S＝(m, c, b) m：左岸的修道士数 c：左岸的野人数 b：左岸的船数 定义启发函数，若满足h（n）≤h*（n），即满足A*条件的。 启发函数1：h（n）=0; 启发函数2： h（n）=M+C; 对状态（1，1，1），不满足h（n）≤h*（n） 先考虑船在左岸的情况： 如果不考虑限制条件，至少需要 [（M+C-3）/2]*2+1 化简后为： [（M+C-3）/2]*2+1=M+C-2 再考虑船在右岸的情况： 同样不考虑限制条件。船在右岸，需要一个人将船运往左岸，因此，对于状态（M，C，0），需要的摆渡数，相当于船在左岸的（M+1，C，1）或（M，C+1，1），所以需要的最少摆渡数为：M+C+1-2+1=M+C 综合条件，需要的最少摆渡数为M+C-2B。 习题五 1.(6)解： 去掉存在量词变为： ?z?v(p(a,b,z,f(z),v,g(z,v))?(Q(a,b,z,f(z),v,g(z,v) ??R(a,z,g(z,v))) 去掉全称量词变为： p(a,b,z,f(z),v,g(z,v)) ?(Q(a,b,z,f(z),v, g(z,v) ??R(a,z, g(z,v)) 适当改名，使子句间不含同名变元： p(a,b,x,f(x),y,g(x,y)) ?(Q(a,b,z,f(z),v, g(z,v) ??R(a,z, g(z,v)) 化成子句集： {p(a,b,x,f(x),y,g(x,y)) , Q(a,b,z,f(z),v, g(z,v) ??R(a,z, g(z,v)) } 3.(5)解： （1）P(x) ?Q(x) （2）? Q(y) ?R(y) （3） ? P(z) ?Q(z) （4） ?R(u) 利用归结原理来判断 （5）?Q(u) [（2）（4）{u/y}] （6）?P(u) [（3）（5）{u/z}] （7）Q(u) [（1）（6）{u/x}] （8）NIL [（5）（7）] 所以原子句集S不可满足 习题五 4.（4） 证明：利用归结反演法，先证明F1∨F2∨?G是不可满足的。化子句集： F1： (1) ?P(x) ∨Q(x) (2) ?P(z) ∨R(z) F2： (3)P(a) (4)S(a) ?G： (5) ?S(y)∨?R(y) 利用归结原理进行归结 (6) R(a) [(2),(3), σ1={a/z}] (7) ?R(a) [(4),(5), σ2 ={a/y}] (8) NIL [(6),(7)] 所以F