人工智能期末复习题解读

答案：

产生式系统分为三部分，分别为综合数据库、规则集和控制策略。综合数据库中保存了推理的初始状态、中间结果和目标状态。规则集中的规则是描述能够使状态发生改变的操作或者方法，它的形式是IF<前件> THEN<后件>。控制策略描述了当对某一状态而言有很多规则可用时，系统应该先采用哪一条规则。

●简述回溯策略与深度优先策略的不同点。(10)

    答案：

    回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索，而回溯搜索则不是图搜索。 

在回溯搜索中，只保留了从初始节点到当前节点的搜索路径。而深度优先搜索，则保留了所有的已经搜索过的路径。   

●(10)

●(10)

●(20 )

●对N＝5、k≤3时，求解传教士和野人问题的产生式系统各组成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态和目标条件的描述）    (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个规则（从左岸到右岸、右岸到左岸各八个）。注意：这里没有(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, 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, 1)

4，结束状态：(0, 0, 0)

●对三枚钱币问题给出产生式系统描述。（20）

设有三枚钱币，其排列处在"正、正、反"状态，现允许每次可翻动其中任意一个钱币，问只许操作三次的情况下，如何翻动钱币使其变成"正、正、正"或"反、反、反"状态。

答：

1）综合数据库

定义四元组：（x, y, z, n） 

其中x,y,x∈[0,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) THEN (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)

●有四人过河，只有一条船，最多可乘坐两人。若单个过，各需1，1，5，9分钟，若两人一起过，则需要的时间以多的为准（如需要5分和9分的两人同时乘坐，则需要9分）。问最少需要多少分钟。要求用产生式系统描述该问题，要求给出综合数据库的定义，规则集，初始状态和结束状态。 (20) 

1）综合数据库： (m1, m5, m9, b) 设从河的左岸到右岸，其中m1, m5,m9分别表示过河时间需要1分钟，5分钟和9分钟的人，在河左岸的人数。b＝1表示船在左岸，b＝0表示船在右岸。

 2）规则集： 

初始状态：(2, 1, 1, 1)    

结束状态 (0, 0, 0, 0)     

●宽度优先搜索 (10)  详见课件相关内容  限深度为5

●写出下面的八数码游戏用A算法进行搜索的示意图  (20)

（1）首先需要简要的描述八数码游戏的产生式系统三要素

（2）最终要写出所采用的规则序列

答案：

    首先描述产生式系统三要素。综合数据库用二维数组表示，规则集为上下左右4条规则。控制策略：f(n) = g(n) + h(n)。选取f（n）最小的节点进行扩展，扩展时采用左上右下顺序。

搜索路径如下：

采用的规则序列为 右 上 右 下 左

●写出下面的八数码游戏用A算法进行搜索的示意图 (20)

（1）首先需要简要的描述八数码游戏的产生式系统三要素

（2）最终要写出所采用的规则序列

首先描述产生式系统三要素。综合数据库用二维数组表示，规则集为上下左右4条规则。控制策略：f(n) = g(n) + h(n)。选取f（n）最小得节点进行扩展，扩展时采用左上右下顺序。g（n）为不在位的将牌数

搜索路径如下：

规则序列如下：（4分）

下右上右

●把下面的谓词公式化成子句集： (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)(( ~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)) }

●化子句集的方法 (10)

例：(z) (x)(y){[(P(x) Q(x)) R(y)] U(z)}

 z) (x)(y){[~(P(x) Q(x))  R(y)] U(z)}

 z) (x)(y){[(~P(x) ~Q(x))  R(y)] U(z)}

 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)] 

  R(f(x))U(a)]}

 {[~P(x)  R(f(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)}

●(10)

●命题逻辑归结  详见课件  （10）

证明公式：(P → Q) → (～Q → ～P)   (10)

证明：

 （1）根据归结原理，将待证明公式转化成待归结命题公式：

   → Q) ∧～(～Q → ～P)

（2）分别将公式前项化为合取范式：

   → Q ＝ ～P ∨ Q

  结论求～后的后项化为合取范式：

   ～(～Q → ～P)＝ ～(Q∨～P) ＝ ～Q ∧ P

  两项合并后化为合取范式：

  （～P ∨ Q）∧～Q ∧ P

 （3）则子句集为：

   ～P∨Q，～Q，P}

子句集为： ～P∨Q，～Q，P}

（4）对子句集中的子句进行归结可得：

1.      ～P∨Q

2.      ～Q

3.      P

4.      Q，    （1，3归结）

5.      ，    （2，4归结）    

由上可得原公式成立。

●{P(x, x,  z), P(f(y), f(B), 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)

●求 W={P(a,x,f(g(y))), P(z,f(z),f(u))}的mgu   (10)

●找出集{P（x，z，y），P（w，u，w），P（A，u，u）}的mgu。（10）

思路：先求P（x，z，y）与P（w，u，w）的mgu，然后再求中间结果和P（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将（1）（2）变换为P（w，u，w）。

下面求（2）（3）的mgu。

令S2 ＝ { A/w, A/u }

则三者的mgu为S1﹒S2 = { A/x, A/y, A/z, A/w, A/u}

●设公理集：

 Q) R,

 T) Q,

求证：R  要求画出归结树  (20)

化子句集：

 Q) R

=> ~(PQ)R

=> ~P~QR

 T) Q

=> ~ (ST)Q

=> (~S~T)Q

=> (~SQ) (~TQ)

⇒{~SQ, ~TQ}

子句集：

 ~QR

 Q

 Q

 （目标求反）

子句集：

 ~QR

 Q

 Q

 （目标求反）

归结：

此处直接绘制归结树即可

●设公理集：   

 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)I(A)

=> D(A)                                          (3)

 A)                                            (4)

目标求反：

 x)(I(x)~R(x))

=> (x)~(I(x)~R(x))

=> (x)(~I(x)R(x))

=> ~I(x)R(x)                                  (5)

换名后得字句集：

 L(x1)

 ~L(x2)

    I(A)                                           

  ~I(x5)R(x5)

推理过程如下：

●某问题由下列公式描述：（20）

试用归结法证明(x)R(x)； 

化子句集如下：

归结树如下：