人工智能课程复习

人工智能课程复习1考试题型设置一、4道简答题，共20分；二、7道计算题，共70分；三、1道论述题，共10分。考试范围为章节3.4.6之前。书本范围为1—86页。考试题目来源于课本例题和课后习题。2问答部分1.人工智能的概念人工智能就是人造智能，主要研究用人工的方法和技术开发智能机器或智能系统，以模仿、延伸和扩展人的智能、生物智能、自然智能，实现机器的智能行为2.人工智能的研究领域博弈（GamePlaying）\自动定理证明（AutomaticTheoremProving）\专家系统（ExpertSystem）\模式识别(PatternRecognition)\机器学习（MachineLearning）\计算智能（ComputationalIntelligence）\自然语言处理（NaturalLanguageProcessing）\分布式人工智能(DistributedArtificialIntelligence)\机器人（Robot）33.盲目搜索盲目搜索，也就是无导向搜索。在搜索过程中，没有任何背景知识作指导不考虑任何及解有关的信息，随机的或按预定顺序机械地搜索，并判断是否为所求的解，直到找到解或是证明问题无解为止。盲目搜索效率太低，一般只适用于求解比较简单的问题。4.深度优先和宽度优先搜索的优缺点深度优先效率高但有可能进入无限分支，在问题有解的情况下而找不到系统的解，并且找到解也不能保证是最有解。如果问题有解，宽度优先搜索一定能够找到解，而且是最优解，但宽度优先搜索的效率较低。45.启发式搜索和启发函数启发式搜索就是利用启发信息进行制导的搜索。在启发式搜索中，常用启发函数来表示启发性信息，是用来估计搜索树节点及目标节点接近程度的一种函数。启发函数的定义一般可以参考：一个节点到目标节点的某种距离或差异的量度；一个节点处在最佳路径上的概率等。6.OPEN表和ClOSED表的作用OPEN表：动态数据结构，登记记录当前待考察的节点。CLOSED表：动态数据结构，记录考察过得节点。7.基于谓词逻辑的机器推理方法自然演绎推理，归结演绎推理，基于规则的演绎推理。5计算部分考核内容包括：1.状态空间图表示（1）描述状态（2）定义操作（3）写出状态空间的三元组（4）绘制状态空间图（5）在图中寻找答案62025/3/29人工智能7例2.2翻转钱币问题（1）

三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。初始状态Qs目标状态集合{Q0,Q7}7例2.2翻转钱币问题（2）引入一个三元组(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},{a,b,c}，{Q0Q7}>2025/3/29人工智能88例2.2翻转钱币问题（4）3.状态空间图问题的状态空间为：

2025/3/29人工智能9构造状态空间图：

aabababaabbbbcccbcccb9从状态空间图，可以找到初始Q5到Q7为3的7条路径，对应的操作序列分别为aab,aba,baa,bbb,bcc,cbc,ccb。找不到Q5到Q0为3的路径.10补充例

二阶梵塔问题（1）

一号杆有A、B两个金盘，A小于B。要求将A、B移至三号杆，每次只可移动一个盘子，任何时刻B不能在A上。（1）有关状态的知识：用二元组（SA，SB）表示状态，SA表示A所在杆号，SB表示B所在杆号。其中:SA

,SB{1,2,3}

,

则全部状态如下：

（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）初始状态为（1，1），终止状态为：（3，3）。2025/3/29人工智能1111AB123S0：（1，1）123S1：（1，2）123S2：（1，3）AA123S5：（2，3）123S4：（2，2）123S3：（2，1）123S8：（3，3）123S7：（3，2）123S6：（3，1）AAAAABABBBBB补充例

二阶梵塔问题（2）2025/3/29人工智能1212（2）有关操作的知识（规则）：A（i，j）表示金盘A从第I号杆移到j号杆，B（i，j）表示金盘B从第i号杆移到j号杆，其中：i,j{1,2,3}，但i

j，全部操作为：

A（1，2），A（1，3），A（2，1）

A（2，3），A（3，1），A（3，2）

B（1，2），B（1，3），B（2，1）

B（2，3），B（3，1），B（3，2）分析每个操作的条件和动作，得到下表：补充例

二阶梵塔问题（3）2025/3/29人工智能1313补充例

二阶梵塔问题（4）操作符条件动作A（1，2）SA=1SA=2A（1，3）SA=1SA=3A（2，1）SA=2SA=1A（2，3）SA=2SA=3A（3，1）SA=3SA=1A（3，2）SA=3SA=2B（1，2）SB=1，SA

1,2或SA=3SB=2B（1，3）SB=1，SA

1,3或SA=2SB=3B（2，1）SB=2，SA

1,2或SA=3SB=1B（2，3）SB=2，SA

2,3或SA=1SB=3B（3，1）SB=3，SA

1,3或SA=2SB=1B（3，2）SB=3，SA

2,3或SA=1SB=22025/3/29人工智能1414补充例

二阶梵塔问题（5）（3）状态空间图1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)2025/3/29人工智能1515计算部分2. 启发式搜索和A*启发函数设计

启发函数h(x)满足,对所有的节点x均有：

h（x）

h*

（x）

其中h*

（x）是从节点x到目标节点的最小代价，这就称为A*算法。16例2.8重排九宫问题2025/3/29人工智能1714832765S012384765Sg

估价函数f（x）＝d（x）＋h（x）方法一：

格局中将牌是否在家启发函数如何定义？h1（x）用x的格局及目标节点格局相比，不在家的将牌数目来衡量。h2(x)是x格局中每个将牌离家（Sg中的位置）的最短距离（不论路上是否放有其他将牌）的总和。方法二：

将牌离家最短距离17255671428376514

283

5761428376512384765Sg1扩展顺序f2(x)值134827654

148

3

27651483

276545134

8

276513482765513486

275663613824765513482576798

143

27657

341

8

27651347

8

26513486

275713486

27578847810138247655111284376514286375142

83765788123847655128

138247651

483276531812384765Sg1扩展顺序f3(x)值134827655

148

3

27651483

276577134

8

276513482765513486

27577231382476551348257674138247655512384765568

138247652025/3/29人工智能191

4832765519例2.9修道士和野人问题

在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运三个人；（2）在任何岸边及船上野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。请定义A*启发函数。2025/3/29人工智能2020例2.9修道士和野人问题解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述：

S＝(m,c,b)

m：左岸的修道士数

c：左岸的野人数

b：左岸的船数初始状态为：（5，5，1）

终止状态为：（0，0，0）

2025/3/29人工智能21提示：不考虑限制条件的运送次数一定小于有限制条件的运送次数。21例2.9修道士和野人问题先考虑船在左岸的情况：如果不考虑限制条件，至少需要

[（M+C-3）/2]*2+1化简后为：

[（M+C-3）/2]*2+1=M+C-2再考虑船在右岸的情况：同样不考虑限制条件。船在右岸，需要一个人将船运往左岸，因此，对于状态（M，C，0），需要的摆渡数，相当于船在左岸的（M+1，C，1）或（M，C+1，1）再加1次。所以需要的最少摆渡数为：M+C+1-2+1=M+C综合条件，需要的最少摆渡数为M+C-2B。2025/3/29人工智能2222计算部分3.极大极小和

－

剪枝注意最后在根节点标出最佳的一步走步232025/3/29人工智能24例2.19用α-β剪枝技术求博弈问题的最佳走步2931－1－1368－1203－574－26－18－7－103ABCEHJKPQDLDRTIFGMUNVS2≥2≤1≤

－12≤222≥26≥60≥0≤0≤－5024计算问题4.应用归结原理和谓词逻辑的推理（1）定义谓词（2）化子句集（3）应用归结原理推理证明2025/3/29人工智能2525子句集消去蕴含词和等值词使否定词仅作用于原子公式使量词间不含同名指导变元消去存在量词消去全称量词化公式为合取范式子句间无同名变元组成一个集合“¬”作用原子谓词没有量词(

、

)合取范式元素之间变元不同集合形式没有蕴含词、等值词蕴含等价式双重否定律、摩根定律、量词转换律存在指定、依赖关系全称指定分配律3/29/202526例3.6将谓词公式化为子句集2025/3/29人工智能27(1)消蕴含词：(2)缩小否定词作用范围：(3)变量改名：(4)消存在量词：(5)消全称量词：(6)化合取范式：(7)适当改名：(8)生成子句集：27例3.15求证G是F1F2和F3的逻辑结果

F1：

F2

：

F3：

G：证：求F1

F2

F3

¬G子句集：

(1)¬D(x)B(x)(2)¬D(y)F(y)(3)¬F(z)N(z)