人工智能例题大纲.docx
《人工智能例题大纲.docx》由会员分享，可在线阅读，更多相关《人工智能例题大纲.docx（25页珍藏版）》请在冰点文库上搜索。
人工智能例题大纲
1。
用谓词逻辑知识表示方法表示如下知识：
（1）有人喜欢梅花，有人喜欢菊花，有人既喜欢梅花又喜欢菊花。
（2）不是每个计算机系的学生都喜欢在计算机上编程序。
解：
（1）
定义谓词
P（x）:
x是人
L（x，y）：
x喜欢y
其中，y的个体域是{梅花,菊花}。
将知识用谓词表示为：
（∃x）（P（x）→L（x,梅花）∨L（x,菊花）∨L（x,梅花）∧L（x,菊花））
解：
（2）
定义谓词
S（x）：
x是计算机系学生
L（x,pragramming）:
x喜欢编程序
U（x，computer）：
x使用计算机
将知识用谓词表示为:
¬（∀x）（S（x）→L（x,pragramming）∧U（x,computer））
2。
请用语义网络表示如下知识：
高老师从3月到7月给计算机系的学生讲“计算机网络”课。
解：
3。
判断以下子句集是否为不可满足
｛P（x）∨Q（x）∨R（x），﹁P（y）∨R（y），﹁Q（a），﹁R（b）}
解:
采用归结反演，存在如下归结树，故该子句集为不可满足。
4、证明G是F的逻辑结论
F：
（∃x）（∃y）（P（f（x））∧（Q（f（y）））
G:
P（f（a））∧P（y）∧Q（y）
证：
先转化成子句集
对F,进行存在固化，有
P（f（v））∧（Q（f（w）））
得以下两个子句
P（f（v）），Q（f（w））
对﹁G，有
﹁P（f（a））∨﹁P（y）∨﹁Q（y）
先进行内部合一，设合一{f（a）/y},则有因子
﹁P（f（a））∨﹁Q（f（a））
再对上述子句集进行归结演绎推理.其归结树如下图所示,即存在一个到空子句的归结过程。
因此G为真。
5设有如下结构的移动将牌游戏：
其中，B表示黑色将牌，W表是白色将牌,E表示空格。
游戏的规定走法是：
（1）任意一个将牌可移入相邻的空格，规定其代价为1;
（2）任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。
游戏要达到的目标什是把所有W都移到B的左边.对这个问题，请定义一个启发函数h（n），并给出用这个启发函数产生的搜索树。
你能否判别这个启发函数是否满足下界要求？
在求出的搜索树中，对所有节点是否满足单调限制？
解：
设h（x）=每个W左边的B的个数，f（x）=d（x）+3*h（x），其搜索树如下：
6设有如下一组推理规则：
r1：
IFE1THENE2（0。
6）
r2:
IFE2ANDE3THENE4（0.7）
r3:
IFE4THENH（0。
8）
r4:
IFE5THENH（0。
9）
且已知CF（E1）=0.5，CF（E3）=0.6，CF（E5）=0。
7.求CF（H）=？
解：
（1）先由r1求CF（E2）
CF（E2）=0。
6×max{0，CF（E1）}
=0。
6×max｛0,0.5}=0。
3
（2）再由r2求CF（E4）
CF（E4）=0.7×max｛0,min｛CF（E2）,CF（E3）}｝
=0.7×max{0,min｛0。
3,0。
6｝｝=0.21
（3）再由r3求CF1（H）
CF1（H）=0。
8×max{0，CF（E4）｝
=0.8×max{0,0.21）｝=0.168
（4）再由r4求CF2（H）
CF2（H）=0.9×max{0，CF（E5）}
=0。
9×max｛0,0.7）}=0.63
（5）最后对CF1（H）和CF2（H）进行合成,求出CF（H）
CF（H）=CF1（H）+CF2（H）-CF1（H）×CF2（H）
=0。
692
7设训练例子集如下表所示：
请用ID3算法完成其学习过程.
解：
设根节点为S，尽管它包含了所有的训练例子，但却没有包含任何分类信息，因此具有最大的信息熵。
即:
H（S）=-（P（+）log2P（+）—P（—）log2P（—））
式中
P（+）=3/6，P（—）=3/6
即有
H（S）=—（（3/6）*log（3/6）-（3/6）＊log（3/6））
=-0.5＊（-1）—0.5*（-1）=1
按照ID3算法,需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵：
H（S｜xi）=（｜ST｜/｜S|）*H（ST）+（｜SF|/｜S｜）*H（SF）
其中，T和F为属性xi的属性值，ST和SF分别为xi=T或xi=F时的例子集，|S｜、｜ST｜和｜SF｜分别为例子集S、ST和SF的大小。
下面先计算S关于属性x1的条件熵：
在本题中,当x1=T时,有：
ST=｛1,2，3｝
当x1=F时,有：
SF=｛4，5，6}
其中，ST和SF中的数字均为例子集S中例子的序号，且有|S｜=6，|ST|=｜SF|=3.
由ST可知：
P（+）=2/3，P（—）=1/3
则有:
H（ST）=-（P（+）log2P（+）—P（—）log2P（-））
=-（（2/3）log2（2/3）—（1/3）log2（1/3））==0。
9183
再由SF可知：
PSF（+）=1/3，PSF（-）=2/3
则有：
H（SF）=-（PSF（+）log2PST（+）—PSF（—）log2PSF（—））
=-（（2/3）log2（2/3）-（1/3）log2（1/3））=0.9183
将H（ST）和H（SF）代入条件熵公式，有:
H（S|x1）=（｜ST｜/｜S|）H（ST）+（｜SF｜/|S|）H（SF）
=（3/6）﹡0.9183+（3/6）﹡0.9183
=0.9183
下面再计算S关于属性x2的条件熵：
在本题中，当x2=T时，有：
ST={1,2,5，6}
当x2=F时，有：
SF={3，4｝
其中，ST和SF中的数字均为例子集S中的各个例子的序号,且有|S｜=6，|ST｜=4，｜SF｜=2。
由ST可知：
PST（+）=2/4
PST（—）=2/4
则有:
H（ST）=-（PST（+）log2PST（+）-PST（-）log2PST（-））
=—（（2/4）log2（2/4）—（2/4）log2（2/4））
=1
再由SF可知:
PSF（+）=1/2
PSF（-）=1/2
则有：
H（SF）=-（P（+）log2P（+）-P（—）log2P（—））
=—（（1/2）log2（1/2）—（1/2）log2（1/2））
=1
将H（ST）和H（SF）代入条件熵公式，有：
H（S|x2）=（|ST|/|S｜）H（ST）+（｜SF｜/｜S｜）H（SF）
=（4/6）﹡1+（2/6）﹡1
=1
可见，应该选择属性x1对根节点进行扩展.用x1对S扩展后所得到的部分决策树如下图所示。
8八数码难题
f（n）=d（n）+P（n）
d（n）深度
P（n）与目标距离
显然满足
P（n）≤h*（n）
即f＊=g*+h＊
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）≤h*（n），满足A＊算法的限制条件.
M—C问题的搜索过程如下图所示。
10设有如下一组知识:
r1：
IFE1THENH（0。
9）
r2：
IFE2THENH（0.6）
r3：
IFE3THENH（—0.5）
r4：
IFE4AND（E5ORE6）THENE1（0.8）
已知：
CF（E2）=0.8，CF（E3）=0.6，CF（E4）=0.5，CF（E5）=0。
6，CF（E6）=0。
8
求:
CF（H）=？
解：
由r4得到:
CF（E1）=0。
8×max｛0,CF（E4AND（E5ORE6））}
=0.8×max{0,min｛CF（E4），CF（E5ORE6）}}
=0。
8×max｛0，min{CF（E4）,max{CF（E5）,CF（E6）｝}}
=0.8×max{0,min{CF（E4），max｛0.6，0.8}｝}
=0。
8×max{0，min{0。
5,0。
8}｝
=0。
8×max｛0,0.5}=0。
4
由r1得到：
CF1（H）=CF（H,E1）×max｛0，CF（E1）}
=0。
9×max{0,0.4｝=0.36
由r2得到:
CF2（H）=CF（H,E2）×max｛0，CF（E2）}
=0。
6×max｛0，0.8}=0。
48
由r3得到：
CF3（H）=CF（H,E3）×max｛0，CF（E3）｝
=—0。
5×max{0,0。
6｝=—0.3
根据结论不精确性的合成算法,CF1（H）和CF2（H）同号,有：
CF12（H）和CF3（H）异号，有：
即综合可信度为CF（H）=0。
53
11设有如下知识：
r1：
IFE1（0.6）ANDE2（0。
4）THENE5（0.8）
r2：
IFE3（0.5）ANDE4（0.3）ANDE5（0。
2）THENH（0。
9）
已知：
CF（E1）=0.9,CF（E2）=0。
8,CF（E3）=0.7，CF（E4）=0。
6
求：
CF（H）=？
解：
CF（E1ANDE2）=0.9*0.6+0。
8＊0。
4=0。
86
CF（E5）=0。
86＊0.8=0。
69
CF（E3ANDE4ANDE5）
=0。
7*0。
5+0。
6＊0.3+0.69＊0。
2=0。
67
CF（H）=0。
67＊0。
9=0。
60
12设有如下规则：
r1:
IFE1ANDE2THENA={a1，a2｝CF=｛0。
3，0.5}
r2：
IFE3THENH={h1，h2｝CF={0。
4,0。
2｝
r3：
IFATHENH={h1，h2｝CF=｛0。
1，0.5}
已知用户对初始证据给出的确定性为：
CER（E1）=0。
8CER（E2）=0。
6
CER（E3）=0。
9
并假Ω定中的元素个数∣Ω∣=10
求：
CER（H）=？
解：
由给定知识形成的推理网络如下图所示:
（1）求CER（A）
由r1：
CER（E1ANDE2）
=min{CER（E1）,CER（E2）}
=min{0。
8，0。
6}=0.6
m（｛a1｝,{a2｝）={0。
6×0。
3，0。
6×0.5｝={0。
18,0。
3｝
Bel（A）=m（{a1｝）+m（｛a2}）=0.18+0.3=0.48
Pl（A）=1-Bel（﹁A）=1-0=1
f（A）=Bel（A）+｜A｜/｜Ω|•[Pl（A）—Bel（A）]
=0。
48+2/10*[1—0。
48］
=0.584
故
CER（A）=MD（A/E’）×f（A）=0.584
（2）求CER（H）
由r2得
m1（{h1｝，{h2｝）={CER（E3）×0.4,CER（E3）×0.2}
={0.9×0.4,0.9×0.2｝
={0。
36，0。
18}
m1（Ω）=1—[m1（{h1}）+m1（｛h2｝）]
=1-［0。
36+0.18］=0。
46
由r3得
m2（{h1｝,｛h2｝）={CER（A）×0。
1,CER（A）×0。
5}
=｛0.58×0。
1，0.58×0。
5}
={0.06，0。
29｝
m2（Ω）=1-[m2（｛h1}）+m2（｛h2｝）］
=1-［0。
06+0.29］=0。
65
求正交和m=m1⊕m2
K=m1（Ω）×m2（Ω）
+m1（｛h1｝）×m2（｛h1｝）+m1（{h1｝）×m2（Ω）+m1（Ω）×m2（{h1}）
+m1（｛h2}）×m2（{h2}）+m1（{h2｝）×m2（Ω）+m1（Ω）×m2（｛h2｝）
=0。
46×0。
65
+0。
36×0.06+0.36×0.65+0。
46×0。
06
+0.18×0.29+0.18×0。
65+0.46×0.29
=0。
30+（0.02+0。
23+0。
03）+（0。
05+0。
12+0。
13）
=0。
88
同理可得：
故有：
m（Ω）=1-[m（｛h1｝）+m（{h2}）］
=1—［0。
32+0。
34]=0。
34
再根据m可得
Bel（H）=m（｛h1}）+m（｛h2}）=0.32+0.34=0.66
Pl（H）=m（Ω）+Bel（H）=0。
34+0。
66=1
CER（H）=MD（H/E’）×f（H）=0.73
13用ID3算法完成下述学生选课的例子
假设将决策y分为以下3类：
y1:
必修AI
y2:
选修AI
y3：
不修AI
做出这些决策的依据有以下3个属性：
x1：
学历层次 x1=1研究生，x1=2本科
x2：
专业类别 x2=1电信类，x2=2机电类
x3：
学习基础 x3=1修过AI,x3=2未修AI
表6。
1给出了一个关于选课决策的训练例子集S.
该训练例子集S的大小为8.ID3算法就是依据这些训练例子,以S为根节点,按照信息熵下降最大的原则来构造决策树的.
解：
首先对根节点，其信息熵为：
其中，３为可选的决策方案数，且有
P（y1）=1/8，P（y2）=2/8,P（y3）=5/8
即有：
H（S）=—（1/8）log2（1/8）—（2/8）log2（2/8）-（5/8）log2（5/8）=1.2988
按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵：
其中，t为属性xi的属性值，St为xi=t时的例子集，｜S｜和|St|分别是例子集S和St的大小。
下面先计算S关于属性x1的条件熵：
在表6-1中，x1的属性值可以为1或2.当x1=1时，t=1时，有：
S1={1，2，3，4｝
当x1=2时，t=2时，有：
S2={5，6,7，8}
其中，S1和S2中的数字均为例子集S中的各个例子的序号,且有|S｜=8，｜S1｜=｜S2｜=4。
由S1可知：
Ps1（y1）=1/4，Ps1（y2）=1/4，Ps1（y3）=2/4
则有:
H（S1）=—Ps1（y1）log2Ps1（y1）—Ps1（y2）log2Ps1（y2）—Ps1（y3）log2Ps1（y3）
=—（1/4）log2（1/4）-（1/4）log2（1/4）-（2/4）log2（2/4）=1.5
再由S2可知：
Ps2（y1）=0/4,Ps2（y2）=1/4，Ps2（y3）=3/4
则有:
H（S2）=–Ps2（y2）log2Ps2（y2）-Ps2（y3）log2Ps2（y3）
=—（1/4）log2（1/4）-（3/4）log2（3/4）=0。
8113
将H（S1）和H（S2）代入条件熵公式，有：
H（S/x1）=（｜S1｜/|S|）H（S1）+（|S2|/｜S｜）H（S2）
=（4/8）﹡1。
5+（4/8）﹡0.8113=1。
1557
同样道理，可以求得：
H（S/x2）=1.1557
H（S/x3）=0.75
可见，应该选择属性x3对根节点进行扩展。
用x3对S扩展后所得到的得到部分决策树如图6。
5所示。
在该树中，节点“x3=1,y3"为决策方案y3.由于y3已是具体的决策方案，故该节点的信息熵为0,已经为叶节点.
节点“x3=2，x1,x2？
”的含义是需要进一步考虑学历和专业这两个属性,它是一个中间节点，还需要继续扩展。
至于其扩展方法与上面的过程类似.
通过计算可知，该节点对属性x1和x2，其条件熵均为1.由于它对属性x1和x2的条件熵相同，因此可以先选择x1，也可以先选择x2。
依此进行下去，若先选择x1可得到如图6.6所示的最终的决策树；若先选择x2可得到如图7.7所示的最终的决策树.
14（归结反演）
已知：
“张和李是同班同学，如果x和y是同班同学,则x的教室也是y的教室，现在张在302教室上课。
”
问：
“现在李在哪个教室上课？
”
解：
首先定义谓词：
C（x，y）x和y是同班同学；
At（x，u）x在u教室上课。
把已知前提用谓词公式表示如下：
C（zhang，li）
（∀x）（∀y）（∀u）（C（x，y）∧At（x,u）→At（y,u））
At（zhang,302）
把目标的否定用谓词公式表示如下:
﹁（∃v）At（li,v）
把上述公式化为子句集：
C（zhang,li）
﹁C（x，y）∨﹁At（x，u）∨At（y，u）
At（zhang，302）
把目标的否定化成子句式，并用重言式
﹁At（li,v）∨At（li，v）
代替之。
把此重言式加入前提子句集中,得到一个新的子句集，对这个新的子句集,应用归结原理求出其证明树.
其求解过程如下图所示。
该证明树的根子句就是所求的答案,即“李明在302教室”.
公式:
A估价函数
用来估计节点重要性，定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。
一般形式:
f（n）=g（n）+h（n）
其中，g（n）是从初始节点S0到节点n的实际代价；h（n）是从节点n到目标节点Sg的最优路径的估计代价。
BA＊算法是对A算法的估价函数f（n）=g（n）+h（n）加上某些限制后得到的一种启发式搜索算法
假设f＊（n）是从初始节点S0出发，约束经过节点n到达目标节点Sg的最小代价，估价函数f（n）是对f＊（n）的估计值。
记
f*（n）=g＊（n）+h*（n）
其中，g*（n）是从S0出发到达n的最小代价,h＊（n）是n到Sg的最小代价
如果对A算法（全局择优）中的g（n）和h（n）分别提出如下限制：
第一，g（n）是对最小代价g＊（n）的估计,且g（n）>0;
第二，h（n）是最小代价h＊（n）的下界，即对任意节点n均有h（n）≤h＊（n）。
则称满足上述两条限制的A算法为A*算法.
C不确定性知识的表示形式：
在C-F模型中,知识是用产生式规则表示的,其一般形式为：
IFETHENH（CF（H,E））
其中,E是知识的前提条件；H是知识的结论；CF（H，E）是知识的可信度。
D组合证据
合取：
E=E1ANDE2AND…En时，若已知CF（E1），CF（E2）,…，则
CF（E）=min{CF（E1）,CF（E2）,…,CF（En）｝
析取：
E=E1ORE2OR…En时，若已知CF（E1），CF（E2），…，则
CF（E）=max{CF（E1）,CF（E2），…，CF（En）｝
E不确定性的更新公式
CF（H）=CF（H,E）×max｛0,CF（E）｝
若CF（E）〈0，则
CF（H）=0
即该模型没考虑E为假对H的影响.
若CF（E）=1，则
CF（H）=CF（H，E）
F设有知识:
IFE1THENH（CF（H，E1））
IFE2THENH（CF（H，E2））
则结论H的综合可信度可分以下两步计算：
（1）分别对每条知识求出其CF（H）。
即
CF1（H）=CF（H，E1）×max｛0，CF（E1）｝
CF2（H）=CF（H，E2）×max｛0，CF（E2）｝
（2）用如下公式求E1与E2对H的综合可信度
G带加权因子的可信度推理
在这种不确定性推理中，证据的不确定性仍然用可信度因子表示，组合证据的可信度可通过计算得到。
对于前提条件
E=E1（ω1）ANDE2（ω2）AND……ANDEn（ωn）
所对应的组合证据,其可信度由下式计算：
CF（E）=CF（E1）*ω1+CF（E2）＊ω2+……+CF（En）*ωn
如果不满足归一条件，则可信度由下式计算：
CF（E）=（CF（E1）＊ω1+CF（E2）*ω2+……+CF（En）*ωn）/（ω1+ω2+…ωn）
H证据理论
设函数m：
2Ω→［0，1]，且满足
则称m是2Ω上的概率分配函数，m（A）称为A的基本概率数。
I概率分配函数的合成
设m1和m2是2Ω上的基本概率分配函数,它们的正交和
定义为
其中
J信任函数（下限函数）
对任何命题A
Ω,其信任函数为
K似然函数（上限函数）
对任何命题A
Ω，其似然函数为
似然函数也称为上限函数,表示对A的非假信任度。
可以看出，对任何命题A
Ω、A
Ω都有
Pl（A）—Bel（A）=Pl（B）-Bel（B）=m（Ω）
L类概率函数
设Ω为有限域，对任何命题A
Ω，命题A的类概率函数为
M证据的匹配度表示
设A是规则条件部分的命题，E'是外部输入的证据和已证实的命题，在证据E’的条件下,命题A与证据E’的匹配程度为
N证据的确定性表示
条件部分命题A的确定性为
CER（A）=MD（A/E'）×f（A）
其中f（A）为类概率函数。
由于f（A）∈［0,1],因此CER（A）∈［0,1]
O组合证据的不确定性表示
当组合证据是多个证据的合取时
E=E1ANDE2AND…ANDEn
则
CER（E）=min｛CER（E1），CER（E2）,…，CER（En）｝
当组合证据是多个证据的析取时
E=E1ORE2OR…OREn
则
CER（E）=max｛CER（E1），CER（E2）,….CER（En）
P结论的确定性
设有知识IFETHENH=｛h1，h2,…，hn}CF={c1,c2,…,cn}
则求结论H的确定性CER（H）的方法如下：
如果有两条或多条知识支持同一结论H，例：
IFE1THENH=｛h1，h2，…，hn｝CF=｛c11，c12，…,c1n}
IFE2THENH={h1，h2，…，hn}CF={c21,c22,…，c2n｝
则按正交和求CER（H），即先求出：
m1=m1（｛
升级会员 