人工智能期末复习题

1、l 简述产生式系统分为几个局部及其主要功能 (10)答案：产生式系统分为三局部，分别为综合数据库、规那么集和控制策略。综合数据库中保存了推理的初始状态、中间结果和目标状态。规那么集中的规那么是描述能够使状态发生改变的操作或者方法，它的形式是IF<前件> THEN<后件>。控制策略描述了当对某一状态而言有很多规那么可用时，系统应该先采用哪一条规那么。l 简述回溯策略与深度优先策略的不同点。(10)答案：回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索，而回溯搜索那么不是图搜索。 在回溯搜索中，只保存了从初始节点到当前节点的搜索路径。而深度优先搜索，那么

2、保存了所有的已经搜索过的路径。 l (10) l (10)l (20 )l 对N5、k3时，求解传教士和野人问题的产生式系统各组成局部进行描述给出综合数据库、规那么集合的形式化描述，给出初始状态和目标条件的描述 (20)答案：1，综合数据库定义三元组：m, c, b 其中：，表示传教士在河左岸的人数。，表示野人在河左岸的人数。，b=1，表示船在左岸，b=0，表示船在右岸。2，规那么集 按每次渡河的人数分别写出每一个规那么，共(3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八种渡河的可能其中(x y)表示x个传教士和y个野人上船渡河，因此共有16个规

3、那么从左岸到右岸、右岸到左岸各八个。注意：这里没有(1 2)，因为该组合在船上的传教士人数少于野人人数。规那么集如下：r1：IF (m, c, 1) THEN (m-3, c, 0)r2：IF (m, c, 1) THEN (m, c-3, 0)r3：IF (m, c, 1) THEN (m-2, c-1, 0)r4：IF (m, c, 1) THEN (m-1, c-1, 0)r5：IF (m, c, 1) THEN (m-1, c, 0) r6：IF (m, c, 1) THEN (m, c-1, 0)r7：IF (m, c, 1) THEN (m-2, c, 0)r8：IF (m, c,

4、 1) THEN (m, c-2, 0)r9 ：IF (m, c, 0) THEN (m+3, c, 1)r10：IF (m, c, 0) THEN (m, c+3, 1) r11：IF (m, c, 0) THEN (m+2, c+1, 1) r12：IF (m, c, 0) THEN (m+1, c+1, 1)r13：IF (m, c, 0) THEN (m+1, c, 1)r14：IF (m, c, 0) THEN (m, c+1, 1)r15：IF (m, c, 0) THEN (m+2, c, 1)r16：IF (m, c, 0) THEN (m, c+2, 1) 3，初始状态：(5

5、, 5, 1)4，结束状态：(0, 0, 0)l 对三枚钱币问题给出产生式系统描述。20设有三枚钱币，其排列处在"正、正、反"状态，现允许每次可翻动其中任意一个钱币，问只许操作三次的情况下，如何翻动钱币使其变成"正、正、正"或"反、反、反"状态。答：1综合数据库定义四元组：x, y, z, n 其中x,y,x0,1，1表示钱币为正面，0表示钱币为反面。n=0,1,2,3，表示当前状态是经过n次翻钱币得到的。2规那么库r1: IF (x, y, z, n) THEN (x, y, z, n+1)r2: IF (x, y, z, n) T

6、HEN (x, y, z, n+1)r3: IF (x, y, z, n) THEN (x, y, z, n+1) 其中x表示对x取反。3初始状态 (1, 1, 0, 0)4结束状态 (1, 1, 1, 3) 或者(0, 0, 0, 3)l 有四人过河，只有一条船，最多可乘坐两人。假设单个过，各需1，1，5，9分钟，假设两人一起过，那么需要的时间以多的为准如需要5分和9分的两人同时乘坐，那么需要9分。问最少需要多少分钟。要求用产生式系统描述该问题，要求给出综合数据库的定义，规那么集，初始状态和结束状态。 (20) 1综合数据库： (m1, m5, m9, b) 设从河的左岸到右岸，其中m1,

7、m5,m9分别表示过河时间需要1分钟，5分钟和9分钟的人，在河左岸的人数。b1表示船在左岸，b0表示船在右岸。 2规那么集： 初始状态：(2, 1, 1, 1) 结束状态 (0, 0, 0, 0) l 宽度优先搜索 (10) 详见课件相关内容 限深度为5l 写出下面的八数码游戏用A算法进行搜索的示意图 (20)初始状态目标状态142083765123804765注：1首先需要简要的描述八数码游戏的产生式系统三要素2最终要写出所采用的规那么序列答案：首先描述产生式系统三要素。综合数据库用二维数组表示，规那么集为上下左右4条规那么。控制策略：f(n) = g(n) + h(n)。选取fn最小的节点

8、进行扩展，扩展时采用左上右下顺序。搜索路径如下： 采用的规那么序列为 右à上à右à下à左l 写出下面的八数码游戏用A算法进行搜索的示意图 (20)初始状态目标状态142083765142730685注：1首先需要简要的描述八数码游戏的产生式系统三要素2最终要写出所采用的规那么序列首先描述产生式系统三要素。综合数据库用二维数组表示，规那么集为上下左右4条规那么。控制策略：f(n) = g(n) + h(n)。选取fn最小得节点进行扩展，扩展时采用左上右下顺序。gn为不在位的将牌数搜索路径如下：规那么序列如下：4分下右上右l 把下面的谓词公式化成子句集： (

9、10)(x) ( (y)P(x,y) à (y)(Q(x,y)àR(x,y) ) (x) ( (y)P(x,y) à (y)(Q(x,y)àR(x,y) )=>(x) ( (y)P(x,y) à (y)( Q(x,y) R(x,y) ) (a)=>(x) ( (y)P(x,y) à (y)( Q(x,y) R(x,y) ) (b)=>(x)( (y)P(x,y) (y)( Q(x,y) R(x,y) ) (c)=>(x) (y) ( P(x,y) ( Q(x,y) R(x,y) ) (d)=>(x) (y

10、)( P(x,y) Q(x,y) (P(x,y) R(x,y) ) (e)=>(x) ( P(x,f(x) Q(x,f(x) (P(x, f(x) R(x, f(x) (f)故子句集为 P(x,f(x) Q(x,f(x) , P(x, f(x) R(x, f(x) (g)换名后的字句集： P(x1,f(x1) Q(x1,f(x1) , P(x2, f(x2) R(x2, f(x2) l 化子句集的方法 (10)例：($z) ("x)($y)(P(x) ÚQ(x) ®R(y) ÚU(z)=> ($z) ("x)($y)(P(x) &#

11、218;Q(x) Ú R(y) ÚU(z)=> ($z) ("x)($y)(P(x) ÙQ(x) Ú R(y) ÚU(z)=> ("x) (P(x) ÙQ(x) Ú R(f(x) ÚU(a)=> ("x)(P(x) ÙQ(x) Ú R(f(x)ÚU(a)=> ("x)P(x) Ú R(f(x)ÚU(a) Ù Q(x)Ú R(f(x)ÚU(a) P(x) Ú R(f

12、(x)ÚU(a) ÙQ(x)Ú R(f(x)ÚU(a) P(x) Ú R(f(x)ÚU(a), Q(x)Ú R(f(x)ÚU(a)P(x1) Ú R(f(x1)ÚU(a), Q(x2)Ú R(f(x2)ÚU(a)l (10)l 命题逻辑归结 详见课件 10· 证明公式：(P Q) (Q P) (10)· 证明： 1根据归结原理，将待证明公式转化成待归结命题公式：(P Q) (Q P)2分别将公式前项化为合取范式：P Q P Q结论求后的后项化为合取范式：(

13、Q P) (QP) Q P两项合并后化为合取范式：P QQ P 3那么子句集为： PQ，Q，P子句集为： PQ，Q，P4对子句集中的子句进行归结可得：1.      PQ2.      Q3.      P4.      Q，1，3归结5.      ð，2，4归结由上可得原公式成立。l P(x, x, z), P(f(y), f(B),

14、 y) 求mgu (10)前缀表示：(P x x z)(P (f y) (f B) y)置换：(f y)/x (P (f y) (f y) z)(P (f y) (f B) y)置换：B/y, 并使得(f B)/x(P (f B) (f B) z)(P (f B) (f B) B)置换：B/z得到置换：(f B)/x， B/y，B/z置换后的结果： (P (f B) (f B) B)l 求 W=P(a,x,f(g(y), P(z,f(z),f(u)的mgu (10)l 找出集Px，z，y，Pw，u，w，PA，u，u的mgu。10思路：先求Px，z，y与Pw，u，w的mgu，然后再求中间结果和P

15、A，u，u的mgu，此即所求先将3个谓词表示为如下形式：P x z y (1)P w u w (2)P A u u (3)S1 = w/x, u/z, w/y。 用S1将12变换为Pw，u，w。下面求23的mgu。令S2 A/w, A/u 那么三者的mgu为S1S2 = A/x, A/y, A/z, A/w, A/ul 设公理集：P, (PÙQ) ®R,(SÚT) ®Q,T求证：R 要求画出归结树 (20)化子句集： (PÙQ) ®R=> (PÙQ)ÚR=> PÚQÚR (S

16、8;T) ®Q=> (SÚT)ÚQ=> (SÙT)ÚQ=> (SÚQ) Ù(TÚQ)Þ SÚQ, TÚQ子句集：(1) P(2) PÚQÚR(3) SÚQ(4) TÚQ(5) T(6) R目标求反子句集：(1) P(2) PÚQÚR(3) SÚQ(4) TÚQ(5) T(6) R目标求反归结：此处直接绘制归结树即可l 设公理集： ("x)(R(x)®L(x)("x)(D(x)®L(x)($x)(D(x)ÙI(x)求证： ($x)(I(x)ÙR(x) (20)化子句集： ("x)(R(x)®L(x) => ("x)(R(x)ÚL(x)=> R(x)ÚL(x) (1)("x)(D(x)®L(x)=> ("x)(D(x)ÚL(x)=> D(x)ÚL(x) (2) ($x)(D(x)ÙI(x)=> D(A)