人工智能与专家系统模拟题.doc

总分核分人姓 名一、密封线内不准答题。二、姓名、学号不许涂改，否则试卷无效。三、考生在答题前应先将姓名、学号、年级和班级填写在指定的方框内。四、试卷印刷不清楚。可举手向监考教师询问。学 号所在年级、班级密封注意 意：卷号：B 二O一二 二O一三 学年第二 学期期末考试 人工智能与专家系统 试题 （ 11计算机科学 专业用） 闭卷 题号一二三四五六七八九十题分264105010得分注意：学号、姓名和所在年级班级不写、不写全或写在密封线外者，试卷作废。一、 求子句集的MGU（10分）二、 请用鲁宾逊归结原理证明：任何通过历史考试并中了彩票的人是快乐的。任何肯学习或幸运的人可以通过所有的考试。John不学习但很幸运。任何人只要是幸运就能中彩。求证：John 是快乐的。（10分） 三. 设有三只琴键开关一字排开, 初始状态为“关、开、 关”, 问连按三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关, 而且只能按一个开关。 请画出状态空间图。 （10分）四 判断下列公式是否为可合一，若可合一，则求出其最一般合一。（20分）(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b)(4) P(f(y), y, x), P(x, f(a), f(b) (5) P(x, y), P(y, x)五 判断下列子句集中哪些是不可满足的：（20分）(1) PQ, Q, P, P(2) PQ , PQ, PQ, PQ (3) P(y)Q(y) , P(f(x)R(a)(4) P(x)Q(x) , P(y)R(y), P(a), S(a), S(z)R(z)(5) P(x)Q(f(x),a) , P(h(y)Q(f(h(y), a)P(z)(6) P(x)Q(x)R(x) , P(y)R(y), Q(a), R(b) 六 设有如图4-34的与/或/树，请分别按和代价法及最大代价法求解树的代价。（10分）ABCDt2t3t4t1图4.34 习题4.14的与/或树56217223E七、应用全局择优求解重排九宫问题 问题的初始状态S0和目标状态Sg分别为： 2 3 1 2 3S0 = 1 8 4 Sg = 8 4 7 6 5 7 6 5 可使用的算符集F=（F1，F2，F3，F4）其中：F1：空格左移，F2：空格上移，F3：空格右移，F4：空格下移（10分）1、应用全局择优搜索，画出搜索树。（2分） 2、给出问题的解，解的代价是多少。（6分） 3、给出open表与closed表在算法终止后的内容。（2分） 4、算法循环多少次终止。参考答案zhqang/u,computer/vzhqang/xW/xPass(x,computer) Win(x,prize) Happy(x)Lucky(w) Win(w,prize)Pass(w,computer) Happy(w) Lucky(w)Happy(zhang)Pass(zhang,computer) Lucky(zhang)Lucky(zhang)Pass(zhang,computer)Lucky(u) Pass(u,v)Lucky(zhang)Lucky(zhang)NIL一a) 解：k=0;S0=S;0=;S0不是单元素集，求得差异集D0=a/z,其中z是变元，a是项，且z不在a中出现。k=k+1=1b) 有1=0a/z=a/z=a/z，c) S1=S0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u),S1不是单元素集，d) 求得差异集D1=x,h(a,u),k=k+1=2;2=1h(a,u)/x=a/z,h(a,u)/x,(4分)e) S2=S1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)，f) S2不是单元素集，求得差异集D2=g(y),u,k=k+1=3g) 3=2g(y)/u=a/z,h(a,u)/xg(y)/u=a/z,h(a,g(y)/x,g(y)/uh) S3=S2g(y)/u=P(a,h(a,g(y),f(g(y)是单元素集。根据求MGU算法，MGU=3=a/z,h(a,g(y)/x,g(y)/u二证明：先将问题用谓词描述如下：(x)(Pass(x,computer) Win(x,prize) Happy(x)(x) (y)(Study(x)Lucky(x) Pass(x,y)Study(zhang) Lucky(zhang)(x)( Lucky(x) Win(x,prize)结论“张是快乐的”的否定Happy(zhang)(3分)将上述公式转化为子句集如下：（1）Pass(x,computer) Win(x,prize) Happy(x)(2) Study(y) Pass(y,z)(3) Lucky(u) Pass(u,v)(4) Study(zhang)(5) Lucky(zhang)(6) Lucky(w) Win(w,prize)(7) Happy(zhang) (3分)三解： 用（K1,K2,K3）表示三个开关的状态，取值为0时表示闭合，为1时表示打开。则初始状态为（0，1，0）。根据题设要求，一个状态I的下一个状态和I只能有一位取值不同（此即状态转换规则），据此可以画出状态空间图。（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）从此状态图不难看出：经过连续三步有状态（0，1，0）只能到达状态（0，0，0）而不能到达状态（1，1，1），即会出现状态“关，关，关”，但不会出现“开，开，开”。四解：(1) 可合一，其最一般和一为：=a/x, b/y。(2) 可合一，其最一般和一为：=y/f(x), b/z。(3) 可合一，其最一般和一为：= f(b)/y, b/x。(4) 不可合一。(5) 可合一，其最一般和一为：= y/x。五解：(1) 不可满足，其归结过程为：PQQPPNIL(2) 不可满足，其归结过程为：PQPQQPQPQQNIL(3) 不是不可满足的，原因是不能由它导出空子句。(4) 不可满足，其归结过程略(5) 不是不可满足的，原因是不能由它导出空子句。(6) 不可满足，其归结过程略六解：若按和代价法，则该解树的代价为： h(A)=2+3+2+5+2+1+6=21若按最大代价法，则该解树的代价为： h(A)=maxh(B)+5, h(C)+6 = max(h(E)+2)+5, h(C)+6 = max(max(2, 3)+2)+5, max(2, 1)+6=max(5+5, 2+6)=10七解：（15分）（1）应用全局择优搜索，画出搜索树g1=0h1=3f1=3左右下g2=1h2=2f2=3g3=1h3=4f3=5g4=1h4=3f4=4下g5=2h5=1f5=3右下g6=3h6=0f6=3g7=3h7=2f7=5 （2分）（2）给出问题的解问题的解：空格左移，空格下移，空格右移。解的代价：g6 =3（6分）（3）给出open表与closed表在算法终止后的内容closed=（1（3），2（3），5（3），6（3）open=(4(4),3(5) ,7(5)（2分）（4）算法循环多少次终止算法循环执行4次