当前位置:首页 >> 理学 >>

人工智能答案 第二章


1.

2.

3.

4. 5.

树式搜索:a,盲目搜索(穷举式搜索){ 广度优先 深度优先} b,启发式搜索{全局择优、局部择优,分支界限、最近择优、A 算法、A*算法} 线式搜索:a,盲目搜索{随即碰撞、回溯穷举} b,启发式搜索{不回溯、智能回溯} 盲目搜索,也就是无导向搜索。在搜索过程中,没有任何背景知识作指导不 考虑任何与解有关的信息,随机的或按预定顺序机械地搜索,并判断是否 为所求的解,直到找到解或是证明问题无解为止。盲目搜索效率太低,一 般只适用于求解比较简单的问题。 启发式搜索,即为有导向的搜索,利用“启发性信息”引导搜索。所谓的启 发性信息就是与问题有关的有利于找到问题解的信息或知识。启发函数, 是用来估计搜索树上节点与目标节点接近程度的一种函数,通常即为 h(x)。 OPEN 表:动态数据结构,登记记录当前待考察的节点。 CLOSED 表:动态数据结构,记录考察过得节点。 深度优先搜索算法的特点是 ① 般不能保证找到最优解; ② 当深度限制不合理时,可能找不到解,可以将算法改为可变深度限 制; ③ 法与问题无关,具有通用性; ④ 于图搜索方法 广度优先搜索算法的特点是 ② 问题有解时,一定能找到解; ②当问题为单位耗散值,并且问题有解时,一定能找到最优解; ③效率 低; ④方法与问题无关,具有通用性; ⑤属于图搜索方法。

6.解:用四元组(f、w、s、g)表示状态, f 代表农夫,w 代表狼,s 代表羊,g 代表菜,其中每个元素都可为 0 或 1,用 0 表示在左 岸,用 1 表示在右岸 。 初始状态 S0:(0,0,0,0) 目标状态:(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}

操作符 条件

动作

p1 p2 p3 q0

f=0,w=0,s 和 g 相异 f=1,w=1 f=0,s=0, f=1,s=1

f=0,g=0,w 和 s 相异 f=1,g=1 f=1,s 和 g 相异,w 和 f=0 s 相异

q1 q2 q3
(0,0,0,0) q2 p2

f=1,w=1,s 和 g 相异 f=0,w=0 f=1,s=1, f=0,s=0

f=1,g=1,w 和 s 相异 f=0,g=0

(1,0,1,0) q0
p3 q2

(0,0,1,0) q3 q1 p1 q2 (1,1,1,0) p2

(1,0,1,1) p2
p3

(0,0,0,1) q2 p2
q0 p2

(0,1,0,0) q3

(1,1,0,1)

(0,1,0,1) q2

(1,1,1,1)

方案有两种:p2→ q0 → p3→ q2 → p2 → q0 → p2 p2→ q0 → p1→ q2 → p3→ q0→ p2 7 题和 9 题参考第 8 题。 8.琴键翻动 (供参考)解:引入一个三元组(q0,q1,q2)来描述总状态,开状态为 0,关状态为 1,全部可能的状态为 : Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0)

Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。

翻动琴键的操作抽象为改变上述状态的算子,即 F={a, b, c} a:把第一个琴键 q0 翻转一次 b:把第二个琴键 q1 翻转一次 c:把第三个琴键 q2 翻转一次 问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}> 问题的状态空间图如下页所示:从状态空间图,我们可以找到 Q5 到 Q7 为 3 的两条路径, 而找不到 Q5 到 Q0 为 3 的路径, 因此, 初始状态“关、 开、 关”连按三次琴键后只会出现“关、 关、 关” 的状态。

a (0,0,0) c (1,0,0) b

(0,0,1) a (1,0,1)

c

b

(1,1,0) a

b

(0,1,0) c c

b (1,1,1) a (0,1,0)

10. 设用二元组(SA,SB)表示问题的状态, SA 表示金盘 A 所在的杆 号, SB 表示金盘 B 所在的杆号, 这样, 全部可能的状态有 9 种, 可 表示如下:

二阶梵塔的全部状态

这里的状态转换规则就是金盘的搬动规则,分别用 A(i,j)及 B(i,j) 表示:A(i,j)表示把 A 盘从第 i 号杆移到第 j 号杆上;B(i,j)表示把 B 盘从第 i 号杆移到第 j 号杆上。经分析,共有 12 个操作,它们分 别是:A(1,2), B(1,2), A(1,3), B(1,3), A(2,1), B(2,1), A(2,3), A(3,1), A(3,2) B(3,2)

B(2,3), B(3,1),

这样由题意,问题的初始状态为(1, 1),目标状态为(3, 3), 则二阶梵 塔 问 题 可 用 状 态 图 表 示 为

由这 9 种可能的状态 和 12 种操作, 二阶梵塔问题的状态空间图如图:

三阶同理可得。

11 代价树如下图所示:分别给出宽度优先及深度优先搜索策略下的 搜索过程和解。其中,F、I、 J、L 是目标节点。
A 3 B 2 D 1 H 3 I 2 J 1 E 3 K 5 F 3 L 3 O 2 C 2 G 1 M 2 P

宽度优先搜索过程: A-﹥ C-﹥ B -﹥ G-﹥E -﹥D-﹥ M-﹥ J,G(J)=6, 解为:A-﹥ B-﹥ E-﹥ J 深度优先搜索过程为:A-﹥ C-﹥ G-﹥M-﹥P-﹥O-﹥L,G(L)

=7, 解为:A-﹥ C-﹥G-﹥L 12 13.用极小极大方法求 N 的最佳走步。
N
4 B 4 4C D -1 -2 3 4 4 1 1 4 A 1 4

-4

1

4

2

4 6 9 -1 -2 1 4 3 4 6 4 4 1 -4 6 1 6 5 4 2 5
最佳路径为 N-〉A-〉B-〉C-〉D

14.
≥2 N ≤2 A B

≥2

C ≤-2 H ≤3 I

≥4 J

≥1 ≤1

E L ≤1

F ≤3 N N

≤2

≤-1

K ≤-5

≤2

3

2

3

-1 -2

3 1

4

3

4

6

5

4

1

-5

6

1

7

5

3

2

6

习题 14 博弈树

1.基于谓词逻辑的机器推理方法:自然演绎推理,归结演绎推理,基 于规则的演绎推理。 2. 求下列谓词公式的子句集 (1) ?x?y(P(x,y) ?Q(x,y)) 解:去掉存在量词变为:P(a,b)?Q(a,b) 变成子句集{ P(a,b),Q(a,b)} (2) ?x ?y(P(x,y) ?Q(x,y)) 解:去掉蕴涵符号变为:?x ?y(? P(x,y) ? Q(x,y)) 去掉全称量词变为:? P(x,y) ? Q(x,y) 变成子句集{ ? P(x,y) ? Q(x,y)}

(3) ?x{P( x) ? ?y[?zQ( x, z ) ? ?zR( x, y, z )]}
?P( x) ? Q( x, z ) ? R( x, f ( x), z )

(4) ?x?y?z?u?v?w(P(x, y, z, y,v, w) ? Q(x, y, z, y,v, w) ? R(x, y, z,u, v, w)) {p(a,y,f(y),y,v,g(y,v)) ?Q(a,y,f(y),y,v,g(y,v)), p(a,x,f(x),x,z,g(x,z)) ?R(a,x,f(x),h(x),z,g(x,z))}
3. 试判断下列子句集中哪些是不可满足的 (1)使用删除策略 (2)归结

4.用合一算法求下列公式集的最一般合一。
(1)W={Q(a,x),Q(y,b)} 最一般合一为:{a/y,b/y} (2) W ? {Q( x,y,z ),Q(u,h(v, v),u)} 最一般合一为:{z/u,h(v,v)/y,z/x}或{x/u,h(v,v)/y,x/z}

5.用归结原理证明,G 是否可肯定是 F 的逻辑结果。 (1) F1 F2 G (?x)(P(x)?(Q(x)∧R(x)) (?x) (P(x) ∧S(x) (?x)(S(x) ∧R(x))

证明:利用归结反演法,先证明 F1 ∨ F2 ∨?G 是不可满足的。

求子句集: (1) ?P(x) ∨Q(x) (2) ?P(z) ∨R(z) (3)P(a) (4)S(a) (5) ?S(y) ∨ ? R(y) (?G)
F2 F1

S

利用归结原理进行归结 (6)R(a) (7) ? R(a) (8)Nil [(2),(3), σ 1={a/z}] [(4),(5), σ 2 ={a/y}] [(6),(7)]

所以 S 是不可满足得,从而 G 是 F1 和 F2 的逻辑结果。
(2)F G (?x) ( (?y)P(x,y) ∧ Q(y)) ?(?y)(R(y) ∧ T(x,y)) ) ? (?x) R(x) ? (?x) (?y) P(x,y) ?? Q(y))

证明:利用归结反演法证明,先证明 F ? ? G 是不可满足的。 把 F、? G 化成子句集: (1) ? P(x,y) ∨? Q(y) ∨R(f(x)) (2) ? P(v,u) ∨? Q(u) ∨T(v, f(u)) (3) Q(b) (4) P(a,b) (5) ? R(z) 对上述式子进行归结: (6) ? P(x,b) ∨R(f(x)) (7)R(f(x)) (8)NIL 所以 G 是 F、的逻辑结论。 (1)和(3)归结,{b/y} (4)和(6)归结,{a/x} (5)和(7)归结{f(x)/z}

(3)F1 (?x) (A(x)∧? B(x)?( ?y) (D(x,y)∧C(y))) F2 (?x) (E(x)∧A(x) ∧ (?y) (D(x,y)?E(y))) F3 (?x) (E(x)? ? B(x)) G (?x) (E(x) ∧C (x)) 证明:利用归结反演法证明,先证明 F1 ? F2 ? F3 ? ? G 是不可满足的。 求子句集: F1: (1)? A(x)∨B(x) ∨D(x,w) (2)? A(y)∨B(y) ∨C(t) F2 (3)E(a) (4)A(a) (5)?D(a,z) ∨E(z)

F3 (6)? E(u) ∨? B(u) ? G (7)? E(v) ∨? C(v) 对子句集进行归结: (8)? B(a) [(3) (6){a/u}] (9)? C(a) [(3) (7){a/v}] (10)B(a) ∨C(t) [(2) (4){a/y}] (11)C(a) [(8) (10){a/t}] (12)Nil [(9) (11)] 6 用归结原理证明下述推理正确。 已知:狗都会吠叫和咬人。 任何动物吠叫时总是吵人的。 松狮是狗。 结论:松狮是吵人的。 证明:首先定义如下谓词: B(x):x 是咬人的。 F(x):x 是吠叫的。 D(x):x 是狗。 N(x):x 是吵人的。 G(x):x 是松狮。 将上述各语句翻译成谓词公式: F1: ?x (D(x)? (B(x) ? F(x))) F2: ?x (F(x)?N(x)) F3: ? x (G(x) ? D(x)) G: ?x (G(x)? N(x)) 利用归结反演法,先证明 F1 ? F2 ? F3 ? ?G 是不可满足的。 F1 ? F2 ? F3 ? ?G 的子句集为 (1)?D(x) ? B(x) (2)?D(y) ? F(y) (3)?F(z) ? N(z) (4)?G(u) ? D(u) (5)G(a) (6)?N(a) 进行归结得: (7)B(a) [(1) (5){a/x}] (8)F(a) [(2) (5){a/y}] (9)?F(a) [(3) (6){a/z}] (10)NIL [(8) (9)] 得证。

7.Sam、Clyde、Oscar 是三只大象,关于它们,已知如下事实: (1)Sam 是粉红色的; (2)Clyde 是灰色的且喜欢 Oscar; (3)Oscar 是粉红色或者是灰色(但不是两种颜色)且喜欢 Sam。 用归结反演方法证明一只灰色大象喜欢一只粉红色大象。 解 首先定义如下谓词: Pink(x)表示 x 是粉红色的大象。

Gray(x) 表示 x 是灰色的大象。 Likes(x,y)表示喜欢 y。 已知条件可以表示成如下谓词公式: (1)Pink(Sam) (2)Gray(Clyde)?Likes(Clyde,Oscar) (3) (Gray(Oscar)?Pink(Oscar) ) ?Likes(Oscar,Sam) 设求证的公式为: G: ?x ?y(Gray(x)? Pink(y)? Likes(x,y) ) 把其否定化为子句形式 (1) Pink(Sam) (2) Gray(Clyde) (3) Likes(Clyde,Oscar) (4) Gray(Oscar)?Pink(Oscar) (5) Likes(Oscar,Sam) (6) ? Gray(x)??Pink(y)?? Likes(x,y) 进行归结: (7)? Gray(x)?? Likes(x,Sam) ( 1) (6)归结{Sam/y} (8)? Gray(Oscar) (5) (7){Oscar/x} (9)Pink(Oscar) (4) (8) (10)? Gray(x)?? Likes(x,Oscar) (6) (9)归结{Oscar/y} (11)? Likes(Oscar,Sam) ( 2) (10)归结{Oscar/y} (12)Nil (3) (11)归结{Sam/y} 8 张某被盗,公安局派五个侦察员去调查,研究案情时,侦察员 A 说: “赵与钱中至少有一 人作案” ; 侦察员 B 说: “钱与孙至少有一人作案” ; 侦察员 C 说: “孙与李中至少有一人作案” ; 侦察员 D 说: “赵与孙中至少有一人与此案无关” ;侦察员 E 说: “钱与李中至少有一人与此 案无关” 。如果这五个侦察员说的都可信,试用消解原理求出谁是盗窃犯。 解:定义谓词用 P(x)表示 x 作案,a,b,c,d 分别代表赵、钱、孙、李,则五个侦察员 得话可用谓词公式表示为 (1) P(a)∨P(b) (2) P(b)∨P(c) (3) P(c)∨P(d) (4) ? P(a)∨? P(c) (5) ? P(b)∨? P(d) 要求的公式为 G: ?xP(x) (即存在 x,x 是罪犯) 将其化为否定形式再析取一个辅助谓词 PA(x) 得 (6)P(x)∨PA(x) 对上面式子进行归结得 (7) ? P(d)∨P(c) (2)(5)归结 (8)P(c) (3)(5)归结 (9)PA(c) (8)(6)归结,{c/x} (10)? P(c)∨P(d) (1)(4)归结 (11)P(b) (3)(5)归结 (12)PA(b) (8)(6)归结,{b/x} 所以,罪犯为钱和孙两个人。

9.归结策略: 删除策略 支持集策略 线性归结策略 单元归结策略 语义归结策略 祖先过滤型策略 10.见第 5 题 11. N(a) ¬S(a) r1{x/a} ¬P(x) F{a/x} ¬P(a) r2{x/a} Q(x) F{a/x} Q(a)^R(a) R(x)

¬P(a) V (Q(a)^R(a))


相关文章:
人工智能第二章知识表示方法x
人工智能第二章知识表示方法x - 人工智能第二章知识表示方法 2-1 状态空间法、问题归约法、谓词逻辑法和语义网络法的要点是什么?它们有何本质上的 联系及异同...
人工智能第二章
人工智能第一章 13页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出...(5) NIL 图 3.12 储蓄问题反演树 反演求解过程 1) 从反演树求取答案步骤 ...
人工智能[第二章知识表示方法]山东大学期末考试知识点复习
人工智能经典试题及答案 37页 1下载券人​工​智​能​[​第​二​章​知​识​表​示​方​法​]​山​东​大​学​期​...
人工智能导论:第二章 蒙特卡洛搜索
人工智能导论:第二章 蒙特卡洛搜索_计算机软件及应用_IT/计算机_专业资料。第 8 章 蒙特卡罗博弈方法计算机博弈理论的研究希望计算机能够像人一样、思维、判断和推理...
第二章人工智能程序设计
第二章 PROLOG 语言与人工智能程序设计 PROLOG 是一门人工智能语言, 是各种人工...2013年注会设计统考真题及答案 81份文档 笑话大全集 笑话大全爆笑版 幽默笑话大...
准全息系统论与智能计算机 第二章
第二章第二章人工智能的理论基础第一节、 第一节、人工智能综述 1、何为人工智能 2、人工智能的具体内容 3、人工智能的立足点 4、人工智能的主导思想 ...
福建农林大学2014马概复习题
实事求是 〔 单项选择题答案] 1.C 2.A 3.A 4...人工智能的出现对马克思主义哲学意识论的意义是( ) ...A 19 . D 4 第二章. 认识的本质及其发展规律一...
更多相关标签: