哈工大人工智能复习题

第一章 人工智能概述

1、请举例说明人工智能这门科学研究的内容、特点、难点，研究目标？ 答：研究的内容：

启发式搜索理论

搜索的方法很多，如回溯、图搜索、启发式等等，主要是给定一些经验做指导提高搜索效率。该方面的研究已经有了比较成熟的技术。

◆ 各种推理方法

常识推理有知识不完全、不够用等问题，如鸟会飞，但是鸵鸟不会飞。

◆ 知识的模型化和表示方法

知识表示很重要，方法主要有逻辑、产生式、语义网络、框架等。现在还不能完全说清楚知识表示到底是什么。

◆ 人工智能系统结构及语言

Lisp 语言主要在美国，Prolog 语言主要在欧洲使用比较广泛。

◆ 机器学习

当前系统大多用归纳的学习、依赖知识库的学习，没有很成熟的方法。神经网络、遗传算法等理论的应用也在探讨之中。

特点：

人工智能是一门知识的科学。以知识为对象，研究知识的获取、表示和使用。

· 人工智能的系统过程是，数据处理->知识处理，数据->符号。符号表示的是知识而不是数值、数据。

· 问题求解过程有启发，有推导。

· 人工智能是引起争论最多的科学之一。

难点：

◆知识获取、（知识表示、机器学习）；

◆ 实现时的规模扩大问题；

◆ 应用前景（封闭的专家系统--机器学习问题）

研究目标：

远期目标：揭示人类智能的根本机理，用智能机器去模拟、延伸和扩展人类智能。 近期目标：建造智能计算机代替人类的部分智力劳动

2、请举例说明人工智能有哪些研究及应用领域？参考教材P12-18

3、人工智能研究有哪此不同学派？它们的基本思想是什么？你认同哪一种观点为什么？参考教材P18-20

第二章 知识表示

1、设有如下语句，请用相应的谓词公式分别把他们表示出来：

a) 有的人喜欢梅花， 有的人喜欢菊花， 有的人既喜欢梅花又喜欢菊花。 b) 有的人每天下午都去打篮球。

c) 新型计算机速度又快， 存储容量又大。

d) 不是每个计算机系的学生都喜欢在计算机上编程序。

e) 凡是喜欢编程序的人都喜欢计算机。

答：

a) 定义谓词：LIKE(x,y)表示：x 喜欢y, PERSON(x)

((∃x )PERSON(x ) ∧LIKE(x , 梅花)) ∧((∃y )PERSON(y ) ∧LIKE(y , 菊花)) ∧((∃x )PERSON(x ) ∧LIKE(x , 梅花) ∧LIKE(y , 菊花))

b) PLAY (x,y):表示x 打y ，AFTERNOON(t), 表示t 是下午

(∃x )(∀t ) (AFTERNOON(t ) → PLAY(x, 篮球) )

c) Computer(x):：x 是计算机；NewType(x)：x 是新型的。

Have Speed(x,y)： x 的速度是y ； High(y): y 是高的

HaveMemory(x,z)：x 的存储容量是z 。Large(z)：z 是大的。

(Computer(x)∧NewType(x))→(High(y)∧Have Speed(x,y))∧(Large(z)∧HaveMemory(x,z))

d) Computer(x): x是计算机系的，Student(x): x 是学生，Like(x,y)

￢(∀x )((Computer(x) ∧Student(x))→Like (x, programming))

e) (∀x )(Person(x) ∧Like(x, programming) →Like(x, computer)

2、请画图说明产生式系统的基本结构及其各组成部分。请参考教材P38

3、设有如下问题：八数码难题。

a) 在一个3×3的方框内放有8个编号的小方块；

b) 紧邻空位的小方块可以移入到空位上；

c) 通过平移小方块可将某一布局变换为另一布局。

请用产生式规则表示移动小方块的操作。

解：空格向上移：IF 空格上方有数字 THEN 空格向上移

4、请把下列命题用一个语义网络表示出来：

1) 树和草都是植物

2) 树和草都有叶和根

3) 水草是草，且生长在水中

4) 果树是树，且会结果

5) 梨树是果树中的一种，它会结梨

5、请对下列命题分别写出它们的语义网络：

a) 每个学生都有一台计算机。

b) 高老师从3月到7月给计算机系学生讲《计算机网络》课。

c) 学习班的学员有男，有女，有研究生，有本科生。

d) 创新公司在科海大街56号，刘洋是该公司的经理，他32岁，硕士学位。 e) 红队与蓝队进行足球比赛，最后以3：2的比分结束。

第三章 确定性推理

1、下列子句是否可以合一，如果可以，写出最一般合一。

a)

b)

c)

d) P(x, B, B) 和 P(A, y, z) P( g( f (v)) , g(u) ) 和 P(x , x) P( x , f(x) ) 和 P(y, y) P(y, y , B) 和 P( z, x , z)

解：1) P(x, B, B) 和 P(A, y, z) 可以合一：

Mgu = { A/x, B/y, B/z}

2) P( g( f (v)) , g(u) ) 和 P(x , x) 不可以合一

3) P( x , f(x) ) 和 P(y, y) 不可以合一

4) P(y, y , B) 和 P( z, x , z) 可以合一

Mgu = { B/x, B/y, B/z}

2、将下面的公式化成子句集

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

解： ～( (( P ∨ ～Q) → R) → (P ∧ R))

= (( P ∨ ～Q) → R) ∧ ～(P ∧ R)

= (～( P ∨ ～Q) ∨ R ) ∧ (～P ∨～R)

= (～P ∨ R) ∧ (Q ∨ R) ∧ (～P ∨～R)

建立子句集：

S = { ～P ∨ R , Q ∨ R , ～P ∨～R }

3、Herbrand 定理解决了一个什么意义上的问题？

答：将无限的不可数的论域上的问题，转化成为在可数的H 论域上讨论的问题。该定理在理论上保证了归结原理的可靠性。

4、设S={ P(x), Q(f(x), y) }，试写出H 域上的元素，并写出S 的一个基例。 解： H ＝ { a, f(a), f(f(a)) , ……}

S 中子句的一个基例为：

P(a), Q(f(a), f(a)) 或者

P(f(a)) , Q(f(f(a)), a)

5、设已知：

a) 如果x 是y 的父亲， y 是z 的父亲， 则x 是z 的祖父；

b) 每个人都有一个父亲。

试用归结演绎推理证明：对于某个u ，一定存在一个人v, v是u 的祖父。 解：定义谓词：father(x,y): 表示x 是y 的父亲。

Grandfather(x,y):表示x 是y 的祖父。

已知条件的谓词公式表示如下：

1) (∀x ) (∀y ) (∀z )father(x , y ) ∧father(y , z ) →Grandfather(x , z )

2) (∀y )(∃x )father(x , y )

结论的谓词公式表示：

(∀u )( ∃v )Grandfather( v , u )

将结论取反并入条件形成公式集F ：

{(∀x )(∀y ) (∀z )father(x , y ) ∧father(y , z ) →Grandfather(x , z ) ， (∀y )(∃x )father(x , y ) ，(∀u )( ∃v )Grandfather( v , u )}

将公式集F 化为子句集S ：

{￢father(x , y ) ∨￢father(y , z ) ∨Grandfather(x , z ) ，father(f (w ), w ),

￢Grandfather( f (u ), u )}

对子句集S 进行归结：对于子句￢father(x , y ) ∨￢father(y , z ) ∨Grandfather(x , z ) 可以先在内部进行合一。

6、用归结法证明：存在一个绿色物体，如果有如下条件存在：

a) 如果可以推动的物体是蓝色的，那么不可以推动的物体是绿色的 b) 所有的物体或者是蓝色的，或者是绿色的，但不能同时具有两种颜色。 c) 如果存在一个不能推动的物体，那么所有的可推动的物体是蓝色的。 d) 物体O1是可以推动的

e) 物体O2是不可以推动的

解： 把上述条件化为逻辑表达式：

1) (x)( pushable (x) ) → blue(x) ) → (

3) (x) (～pushable(x)) → (

4) pushable(O1)

5) ～pushable(O2)

将结果命题否定：

～(x)(green(x))

将条件表达式和结果命题化为子句形：

由条件1

(1) pushable(x)∨green(x)

(2) ～blue(a)∨pushable(y)∨green(x)

由条件2

(3) ～green(x)∨～blue(x)

(4) green(x)∨blue(x)

由条件3

(5) pushable(x)∨～pushable(y)∨blue(y)

由条件4

(6) pushable(O1)

由条件5

(7) ~pushable(O2)

由结论

(8) ～green(x)

归结：

(9) ～blue(x) ∨ pushable(y) (2) (8)

(10) ～blue(x) (7) (9)

(11) blue(x) (4) (8)

(12) □ (10)(11) x)(～pushable(x) → green(x) ) 2) (x) ( ( (blue(x) ∧ ～green(x)) ∨ (～blue(x) ∧ green(x))) x) ( pushable(x) → blue(x) )

7、已知事实公式为 （（x ）（y ）（z ）（Gt （x ，y ）∧Gt （y ，z ）→Gt （x ，z ））

（u ）（v ）（Succ （u ，v ）→Gt （u ，v ）

（~Gt（x ，x ）） （x ）

求证Gt （5，2）

试判断下面的归结过程是否正确？若有错误应如何改进：

8、我们来考虑下列一段知识：

a) Tony 、Mike 和John 属于Alpine 俱乐部，

b) Alpine 俱乐部的每个成员不是滑雪运动员就是一个登山运动员， c) 登山运动员不喜欢雨而且任一不喜欢雪的人不是滑雪运动员，

d) Mike 讨厌Tony 所喜欢的一切东西，而喜欢Tony 所讨厌的一切东西， e) Tony 喜欢雨和雪。

以谓词演算语句的集合表示这段知识，使得这些语句适合一个逆向的基于规则的演绎系统。若想利用基于规则的逆向推理回答问题" 有没有Alpine 俱乐部的一个成员，他是一个登山运动员但不是一个滑雪运动员呢？" ，问题应该如何表示呢？

答： 我们用Skier(x)表示x 是滑雪运动员，Alpinist(x)表示x 是登山运动员，Alpine(x)表示x 是Alpine 俱乐部的成员。

问题用谓词公式表示如下：

已知：

(1) Alpine(Tony)

(2) Alpine(Mike)

(3) Alpine(John)

(4) (∀x){Alpine(x)→[Skier(x)∨Alpinist(x)]}

(5) (∀ x){Alpinist(x)→~Like(x, Rain)}

(6) (∀ x){~Like(x, Snow)→~ Skier(x)}

(7) (∀ x){Like(Tony, x)→~Like(Mike, x)}

(8) (∀ x){~Like(Tony, x)→Like(Mike, x)}

(9) Like(Tony, Snow)

(10) Like(Tony, Rain)

目标：(∃x){Alpine(x)∧Alpinist(x)∧~Skier(x)}

9、一个积木世界的状态由下列公式集描述：

ONTABLE （A ） CLEAR （E ）

ONTABLE （C ） CLEAR （D ）

ON （D ，C ） HEA VY （D ）

ON （B ，A ） WOODEN （B ）

HEA VY （B ） ON （E ，B ）

下列语句提供了有关这个积木世界的一般知识：

每个大的蓝色积木块是在一个绿色积木块上。

每个重的木制积木块是大的。

所有顶上没有东西的积木块都是蓝色的。

所有木制积木块是蓝色的。

以具有单文字后项的蕴涵式的集合表示这些语句。绘出能求解" 哪个积木块是在绿积木块上" 这个问题的一致解图（用B 规则）。

解：知识的谓词表示：

(

(

(

(x)( ∃y){[BIG(x)∧BLUE(x)]→ON(x, y)∧GREEN(y)} x){[HEAVY(x)∧WOODEN(x)]→BIG(x)} x){CLEAR(x)→BLUE(x)} x){WOODEN(x)→BLUE(x)}

目标：(∃x)( ∃y)GREEN(y)∧ON(x, y)

对规则Skolem 化，对目标用对偶形式Skolem 化后，整理得：

事实：

ONTABLE （A ） CLEAR（E ）

ONTABLE （C ） CLEAR（D ）

ON （D ，C ） HEA VY （D ）

ON （B ，A ） WOODEN（B ）

HEA VY （B ） ON （E ，B ）

规则：

r1:[BIG(x1)∧BLUE(x1)]→ON(x1,f(x1))

r2:[BIG(x2)∧BLUE(x2)]→GREEN(f(x2))

r3:[HEAVY(x3)∧WOODEN(x3)]→BIG(x3)

r4:CLEAR(x4)→BLUE(x4)

r5:WOODEN(x5)→BLUE(x5)

目标：GREEN(y)∧ON(x, y)

容易验证，只有一个解图是一致的，其合一复合为：

{B/x, f(B)/y}

带入目标公式，得到解答：GREEN(f(B))∧ON(B, f(B))

其含义是，积木B 在绿色积木上边。这里的f(B)可以理解为B 下面那个积木。

10、 某问题由下列公式描述：

(1)、（ s ）~P（s ）

（P （g （s ））） (2)、（s ） (3)、（ x ）（s ）（y ）（（P （s ）∧Q （b ，x ，s ））→H （y ） （s ）（Q （b ，x ，s ）→Q （b ，x ，g （s ））） (4)、（x ） (5)、（x ）（s ）（

y ）（~P（s ）→Q （b ，x ，y ））

求证：(x)H(x) 请用基于规则的逆向演绎系统求解(x)H(x)成立。

要求给出一个求得的一致解图，并说明为什么它是一致的；给出目标的解答。

答： 对事实和规则进行skolem 化：

（1）(s)

~P(a)

（2）(s)(P(g(s)))

s)(y)((P(s)∧Q(b，x ，s)) →H(y)

s)(Q(b，x ，s) →Q(b，x ，g(s)))

s)(y)(~P(s)→Q(b，x ，y)) P(g(s))

（3）(x)(（4）

(（5）(x)(x)( (P(s)∧Q(b，c

，s)) →H(f(s)) Q(b，x ，s) →Q(b，x ，g(s))

~P(s)→Q(b，x ，h(x, s))

经变量换名后，有事实和规则如下：

~P(a)

P(g(s1))

r1: (P(s2)∧Q(b，c ，s2)) →H(f(s2))

r2: Q(b，x3，s3) →Q(b，x3，g(s3))

r3: ~P(s4)→Q(b，x4，h(x4, s4))

用对偶形式对目标skolem 化： (x)H(x)

H(x)

演绎图如下图(这里只给出了一个一致解图) 。

由置换集构造U1和U2：

U1 = (x, s2, x3, s2, x4, s3, s4)

U2 = (f(s2), g(s1), c, g(s3), c, h(x4, s4), a)

由于U1和U2是可合一的，因此该解图是一致解图。合一复合为：

{f(g(h(c, a)))/x, g(h(c, a))/s2, c/x3, h(c, a)/s3, c/x4, h(c, a)/s1, a/s4}} 将该合一复合带入目标中，得到解答： x = f(g(h(c, a)))

第四章 不确定性推理

1、什么是不确定性推理？为什么要采用不确定性推理？P122

2、不确定性推理中要解决哪些基本问题？P123-P124 ==3、已知： ===

规则

R1：E1→H ，CF （H ，E1）＝0.9

R2：E2→H ，CF （H ，E2）＝0.6

R3：E3→H ，CF （H ，E3）＝-0.5

R4：E4∧(E5∨E6) →E1，CF （E1，E4∧(E5∨E6) ）＝0.9

初始数据：CF （E2）＝0.8，CF （E3）＝0.6，CF （E4）＝0.5 CF（E5）＝0.6，CF （E6）＝0.8, CF（H ）=0

求：CF （H ）

解：CF(E1)=0.8*max{0,CF(E4 AND (E5 OR E6))}

=0.8*max{0, min{ CF(E4), CF(E5 OR E6)}}

0.8*max{0, min{0.5, max(CF(E5), CF(E6)}}

0.8*max{0, min{0.5, 0.8}}0.8*max{0, 0.5}

0.8*0.5==0.4

CF1(H)=CF(H,E1)*max{0, CF(E1)} === =0.9*0.4=0.36

CF2(H)=CF(H,E2)*max{0, CF(E2)}

=0.6*0.8=0.48

CF3(H)=CF(H,E3)*max{0, CF(E3)}

=-0.5*0.6=-0.3

CF12(H)=CF1(H)+CF2(H)-CF1(H)*CF2(H)

=0.36+0.48-0.36*0.48=0.67

CF123(H)=(CF12(H)+CF3(H))/(1-min{|CF12(H)|, |CF3(H)|})

=(0.67+(-0.3))/(1-0.3)=0.53

4、当证据E1, E2,E3, E4必然发生后, 看H 的概率变化. 已知H 的先验概率为0.03, 而规则

R1: E1→H LS=20 LN=1

R2: E2→H LS=300 LN=1

R3: E3→H LS=75 LN=1

R4: E4→H LS=4 LN=1

解: (1) 由P(H)=0.03, 得:

O(H)=P(H)/(1-P(H))=0.03/1-0.03=0.030927

(2) 根据R1, 得:

O(H|E1)LS*O(H)20*0.0309270.61854

P(H|E1)O(H)/(1+O(H))0.382

(3) 根据R2, 得:

(3) 根据R2, 得:

O(H|E1,E2)=O(H|E1)/O(H)*O(H|E2)/O(H)*O(H)

=LS*O(H|E1)=300*0.61854=185.562

P(H|E1,E2)=O(H|E1,E2)/(1+O(H|E1, E2)=0.99464

(4) 根据R3, 得:

O(H|E1, E2, E3)=LS*O(H|E1, E2)=13917.15

P(H|E1, E2, E3)=0.99993

(5) 根据R3, 得:

O(H|E1,E2,E3,E4)=LS*O(H|E1,E2,E3)=55668.6

P(H|E1,E2,E3,E4)=0.99998

5、例3: 当证据E 必然发生, 已知H1的先验概率为0.03，而规则 R1：E →H1 LS=20 LN=1

R2：H1→H2 LS=300 LN=0.0001

又知P(H2)的先验概率为0.01时, 计算P(H2|E)？

解: (1) 根据R1及已知P(H1)=0.03, 得:

P(H1|E)LS*P(H1)/((LS-1)*P(H1)+1)

=20*0.03/((20-1)*0.03+1)=0.382

(2) 由于H1 是不确定的, 所以要用插值法.

因为P(H1|E)>P(H1),

当P(H1|E)=P(H1)时, 有:

P(H2|E)P(H2)0.01 = 当P(H1|E)=1时, 有:

P(H2|E)=P(H2|H1) =

=LS*P(H2)/((LS-1)*P(H2))+1

=0.75188

(3) P(H2|E)=0.01+(0.75188-0.01)/(1-0.03)*(0.382-0.03)=0. 2792 =

第五章 搜索策略

1、 对量水问题给出问题描述即状态和操作定义，并画出状态空间图。

有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。

解：

a) 定义两元组：（L5, L2）

其中：0

0

b) 操作规则集

r1：IF (L5, L2) THEN (5, L2) /* 将L5灌满水 */

r2：IF (L5, L2) THEN (L5, 2) /* 将L2灌满水 */

r3：IF (L5, L2) THEN (0, L2) /* 将L5水到光 */

r4：IF (L5, L2) THEN (L5, 0) /* 将L2水到光 */

r5：IF (L5, L2) and L5+L2

r6：IF (L5, L2) and L5+L2>5 THEN (5, L5+L2-5) /* L2到入L5中 */

r7：IF (L5, L2) and L5+L2

r8：IF (L5, L2) and L5+L2>5 THEN (L5+L2-2, 2) /* L5到入L2中 */

c) 初始状态：(5, 0)

d) 结束条件：(x, 1)，其中x 表示不定。当然结束条件也可以写成：(0, 1)

2、对三枚钱币问题给出产生式系统描述及状态空间图。

设有三枚钱币，其排列处在" 正、正、反" 状态，现允许每次可翻动其中任意

一个钱币，问只许操作三次的情况下，如何翻动钱币使其变成" 正、正、正" 或" 反、反、反" 状态。

答：

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)

3、有一农夫带一条狼，一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：

a) 船太小，农夫每次只能带一样东西过河；

b) 如果没有农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过河方案，使得农夫，狼，羊和菜都能不受损失的过河，画出相应的状态空间图。

4、图1-2是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A 城出发，经过其他各城一次且仅一次，最后回到A 城，请给出搜索树，找出一条最优线路。P200 图5-33

5、请找出图1-3的与或树所包含的解树。P200 图5-34

6、图1-4是一个五子棋棋盘，A 、B 两人轮流走步，谁先布成五子一线（横线，竖线，对角线均可），谁就获胜，请定义估价函数，并站在A 的立场上，找出当前的最佳走步。P200 5-36

7、某问题的状态空间图如下图所示，其中括号内标明的是各节点的h 值，弧线边的数字是该弧线的代价，试用A 算法求解从初始节点S 到目标节点T 的路径。要求给出搜索图，标明各节点的f 值，及各节点的扩展次序，并给出求得的解路径。

答：搜索图如图所示，其中括号内标出的是节点的f 值，圆圈内的数字是扩展的次序。

F(16)

得到的解路径为：S-B-F-J-T

8、有四人过河，只有一条船，最多可乘坐两人。若单个过，各需1，1，5，9分钟，若两人一起过，则需要的时间以多的为准（如需要5分和9分的两人同时乘坐，则需要9分）。问最少需要多少分钟。

(1)、给出问题的状态及操作描述，初始状态和结束状态。

(2)、定义一个h 函数，并说明是否满足A*条件。

(3)、用A 算法求解该问题，给出状态搜索图，标出扩展次序、各节点的f 值、解路径及解路径的代价。

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

操作规则集：

初始状态：

(2, 1, 1, 1)

结束状态

(0, 0, 0, 0)

h 函数：

h(n) = m - b，其中m 为在左岸的人数，b 为船是否在左岸。

对于任意两个节点ni 和nj ，其中nj 是ni 的子节点。

当ni 中b ＝1时，则nj 中b ＝0，因此：max(h(ni)-h(j))=(m-1)-(m-1)=0, 而C(ni, nj)最小为1，因此h(ni)-h(nj)

当ni 中b ＝0时，则nj 中b ＝1，因此：max(h(ni)-h(j))=m-m=0, 而C(ni, nj)最小为1，因此h(ni)-h(nj)

而对于目标节点t ，h(t)=0。

因此该h 函数满足单调性条件。所以h 满足A*条件。

9、下图所示博弈树，按从左到右的顺序进行α-β剪枝搜索，试标明各生成节点

的到推值，何处发生剪枝，及应选择的走步。

解：

第6章机器学习

1、什么是机器学习？为什么要研究机器学习？P203

2、说明机器学习系统的基本结构，并说明各部分的作用。P206

3、叙述机械式学习的基本原理及学习过程。P208

4、请画出实例学习的两空间模型，并说明实例学习的过程。P211-214

第7章 神经网络及连接学习

1、什么是人工神经网络？请画出单层感知器模型图？P237图7-12

2、人工神经网络的学习机理主要有哪两种不同的观点。其主要思想是什么？单层感知器学习属于哪种机制。P234

3、请画出M-P 神经元模型，写出输出函数的定义，并列举出两种以上的功能函数。P230