(完整版)人工智能例题大纲.docx

用谓词逻辑知识表示方法表示如下知识：
有人喜欢梅花，有人喜欢菊花，有人既喜欢梅花又喜欢菊花。
不是每个计算机系的学生都喜欢在计算机上编程序。
解：⑴
定义谓词
P(x)： x是人
L(x,y)： x 喜欢 y
其中，y的个体域(-l) = 1
按照ID3算法，需要选择一个能使S的期垫嫡为最小的一个属性对根节点进行扩展，因 此我们需要先计算S关于每个属性的条件爛：
H⑸x^dSil/ISD* H(St) + (|Sf|/|S|)* H(Sf)
其中,T和F为属性人的属性值,St和&分别为x产T或x产F时的例子集,|S|. | ST|和|Sf|分 别为例子集S、St和Sf的大小。
下面先计算S关于属性X】的条件矯：
在本题中，当xfT时，有：
St={1, 2, 3}
当Xi=F时，有：
Sf={4, 5, 6}
其中，St和Sf中的数字均为例子集S中例子的序号，且有|S|=6, |St| = |Sf|=3o 由St可知：
P(+)=2/3, P(-)=l/3
则有：
H(St)= - (P(+)log2 PH- P(-)log2 P(-))
=-((2/3)log2(2/3)- (l/3)log2(l/3)) ==
再由Sf可知：
Psf(+)=1/3, Psf(-)=2/3
贝I］有:
H(Sf)= - (PsF(+)log2 Pst(+) - PsF(-)log2 Psf(-))
=-((2/3)log2(2/3)- (l/3)log2(l/3)) =
将H(St)和H (Sf)代入条件爛公式,有：
H(S| xW|St|/|S|)H(St)+(|Sf|/|S|)H(Sf)
=(3/6) * + (3/6) *
=
下面再计算S关于属性x2的条件矯：
在本题中，当X2=l■时，有：
ST={1, 2, 5, 6}
当X2寸时，有：
Sf={3, 4}
其中,St和Sf中的数字均为例子集S中的各个例子的序号,且有|S|=6, | St |=4, | Sf |=2o 由St可知：
Pst (+) = 2/4
Pst(-) = 2/4
则有：
H(St)= - (Pst (+)log2 P st (+) - Pst (-)log2 P st (-))
=-((2/4)log2(2/4) - (2/4)log2(2/4))
=1
再由Sf可知：
Psf (+)=1/2
Psf (-)=1/2
则有：
H(SF)=-(P(+)log2 P(+) - P(-)log2 P(-))
=-((l/2)log2(l/2)- (l/2)log2(l/2))
=1
将H(St)和H (Sf)代入条件爛公式,有：
H(S| x2)=(|St|/|S|)H(St)+(|Sf|/|S|)H(Sf)
=(4/6) ♦ 1 + (2/6) * 1
=1
扩展吃后得到的完整决策树
可见，应该选择属性Xi对根节点进行扩展。用xj对S扩展后所得到的部分决策树如卞 图所示。
扩展旳后的部分决策树
8八数码难题 f(n)=d(n)+P(n) d(n)深度
P(n)与目标距离 显然满足
P(n)< h*(n) 即 f*=g*+h*
八数码难题h(n)=P(n)的搜索树
9修道士和野人问题
解：用m表示左#的修道士人数，c表示左岸的野人数，b表示左#的船数，用三 元组(m, c, b)表示问题的状态。
对A*算法，首先需要确定估价函数。设g(n)=d(n), h(n)=m+c-2b,则有 f(n)=g(n)+h(n)=d(n)+m+c-2b
其中，d(n)为节点的深度。通过分析可知h(n)wh*(n),满足A*算法的限制条件。
M-C问题的搜索过程如下图所示。
修道士和野人问题Lq
i=4
h=4 f=4
gl) T
h=5 f=6
(320)
(3「0) h=3 f=5 &ii
(3,2 一 h=3 f=6 ；
42flL
(,0)
Q9 | Roi
(031)
Qio] l02
(0X0) h=l El 1 漏
(021)~^*(0O0)
h=2
h=2
h=l
h=l
h=4 f=5
问题状态：(ngb) 估价函数：h(n)=m+c 2b
h=0 Qll
10设有如下一组知识:
rx： IF
Ei
THEN H
()
r2：
IF
e2
THEN
H
()
r3：
IF
e3
THEN
H
(