人工智能课程复习.

人工智能课程复习南晓斐考试题型设置•一、4道简答题，共20分；•二、7道计算题，共70分；•三、1道论述题，共10分。•考试范围为章节3.4.6之前。书本范围为1—86页。•考试题目来源于课本例题和课后习题。问答部分•1.人工智能的概念–人工智能就是人造智能，主要研究用人工的方法和技术开发智能机器或智能系统，以模仿、延伸和扩展人的智能、生物智能、自然智能，实现机器的智能行为•2.人工智能的研究领域–博弈（GamePlaying）\自动定理证明（AutomaticTheoremProving）\专家系统（ExpertSystem）\模式识别(PatternRecognition)\机器学习（MachineLearning）\计算智能（ComputationalIntelligence）\自然语言处理（NaturalLanguageProcessing）\分布式人工智能(DistributedArtificialIntelligence)\机器人（Robot）•3.盲目搜索–盲目搜索，也就是无导向搜索。在搜索过程中，没有任何背景知识作指导不考虑任何与解有关的信息，随机的或按预定顺序机械地搜索，并判断是否为所求的解，直到找到解或是证明问题无解为止。盲目搜索效率太低，一般只适用于求解比较简单的问题。•4.深度优先和宽度优先搜索的优缺点–深度优先效率高但有可能进入无限分支，在问题有解的情况下而找不到系统的解，并且找到解也不能保证是最有解。如果问题有解，宽度优先搜索一定能够找到解，而且是最优解，但宽度优先搜索的效率较低。•5.启发式搜索和启发函数–启发式搜索就是利用启发信息进行制导的搜索。在启发式搜索中，常用启发函数来表示启发性信息，是用来估计搜索树节点与目标节点接近程度的一种函数。启发函数的定义一般可以参考：一个节点到目标节点的某种距离或差异的量度；一个节点处在最佳路径上的概率等。•6.OPEN表和ClOSED表的作用–OPEN表：动态数据结构，登记记录当前待考察的节点。–CLOSED表：动态数据结构，记录考察过得节点。•7.基于谓词逻辑的机器推理方法–自然演绎推理，归结演绎推理，基于规则的演绎推理。计算部分•考核内容包括：•1.状态空间图表示–（1）描述状态–（2）定义操作–（3）写出状态空间的三元组–（4）绘制状态空间图–（5）在图中寻找答案2020/1/7人工智能7例2.2翻转钱币问题（1）三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。初始状态Qs目标状态集合{Q0,Q7}例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}2020/1/7人工智能8例2.2翻转钱币问题（4）3.状态空间图问题的状态空间为：2020/1/7人工智能9构造状态空间图：507{}{}{}QabcQQ，，，，，cbbcQ1aQs=Q5bQ7=Qg2aQ3cQ2aQ6baQ4Q0=Qg1c(0,0,0)(1,0,0)(0,0,1)(1,0,1)(1,1,1)(0,1,1)(1,1,0)(0,1,0)aabababaabbbbcccbcccb•从状态空间图，可以找到初始Q5到Q7为3的7条路径，对应的操作序列分别为aab,aba,baa,bbb,bcc,cbc,ccb。找不到Q5到Q0为3的路径.补充例二阶梵塔问题（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）。2020/1/7人工智能11AB123S0：（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）2020/1/7人工智能12（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）2020/1/7人工智能13补充例二阶梵塔问题（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=22020/1/7人工智能14补充例二阶梵塔问题（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)2020/1/7人工智能15计算部分•2.启发式搜索和A*启发函数设计启发函数h(x)满足,对所有的节点x均有：h（x）h*（x）其中h*（x）是从节点x到目标节点的最小代价，这就称为A*算法。例2.8重排九宫问题2020/1/7人工智能1714832765S012384765Sg估价函数f（x）＝d（x）＋h（x）方法一：格局中将牌是否在家启发函数如何定义？h1（x）用x的格局与目标节点格局相比，不在家的将牌数目来衡量。h2(x)是x格局中每个将牌离家（Sg中的位置）的最短距离（不论路上是否放有其他将牌）的总和。方法二：将牌离家最短距离2556714283765142835761428376512384765Sg1扩展顺序f2(x)值13482765414832765148327654513482765134827655134862756636138247655134825767981432765734182765134782651348627571348627578847810138247655111284376514286375142837657881238476551281382476514832765312384765Sg1扩展顺序f3(x)值134827655148327651483276577134827651348276551348627577231382476551348257674138247655512384765568138247652020/1/7人工智能19148327655例2.9修道士和野人问题在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运三个人；（2）在任何岸边及船上野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。请定义A*启发函数。2020/1/7人工智能20例2.9修道士和野人问题解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述：S＝(m,c,b)m：左岸的修道士数c：左岸的野人数b：左岸的船数初始状态为：（5，5，1）终止状态为：（0，0，0）2020/1/7人工智能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。2020/1/7人工智能22计算部分•3.极大极小和－剪枝–注意最后在根节点标出最佳的一步走步S2S1ZYXWVUTRAS3SS6S5S4QPONMLKJIHGFEDCB231-2354-2-33-241045-32-24-30-21-32401202最佳求极大值求极大值求极小值求极小值2020/1/7人工智能24例2.19用α-β剪枝技术求博弈问题的最佳走步2931－1－1368－1203－574－26－18－7－103ABCEHJKPQDLDRTIFGMUNVS2≥2≤1≤－12≤222≥26≥60≥0≤0≤－50计算问题•4.应用归结原理和谓词逻辑的推理–（1）定义谓词–（2）化子句集–（3）应用归结原理推理证明2020/1/7人工智能252020/1/726子句集消去蕴含词和等值词使否定词仅作用于原子公式使量词间不含同名指导变元消去存在量词消去全称量词化公式为合取范式子句间无同名变元组成一个集合“¬”作用原子谓词没有量词(、)合取范式元素之间变元不同集合形式没有蕴含词、等值词蕴含等价式双重否定律、摩根定律、量词转换律存在指定、依赖关系全称指定分配律例3.6将谓词公式化为子句集2020/1/7人工智能27{yP(x,y)y[Q(x,y)R(x,y)]}x(1)消蕴含词：(2)缩小否定词作用范围：(3)变量改名：(4)消存在量词：(5)消全称量词：(6)化合取范式：(7)适当改名：(8)生成子句集：{P(x,f(x))Q(x,g(x)),P(y,f(y))R(y,g(y))}2020/1/728例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)(4)¬G(u)D(u)(5)G(a)(6)¬N(b)x(()(()()))DxBxFxx(()())FxNxx(()())GxDxx(()())GxNx应用归结原理，得：(7)D(a)（4）与（5）归结，{a/u}(8)F(a)（2）与（7）归结，{a/y}(9)¬F(b)（3）与（6）归结，{b/z}(10)Nil（8）与（9）归结,{a/b}•命题得证2020/1/729•例题：Tom、Jerry、Sam是三只大象，关于它们，已知如下事实：•（1）Tom是粉红色的；•（2）Jerry是灰色的且喜欢Sam；•（3）Sam是粉红色或者是灰色且喜欢Tom。•用归结反演方法证明一只灰色大象喜欢一只粉红色大象。•解首先定义如下谓词：•P(x)表示x是粉红色的大象。•G(x)表示x是灰色的大象。•L（x，y）表示喜欢y。•定义常量：Tom为A，Jerry为B,Sam为C。•已知条件可以表示成如下谓词公式：•（1）P（A）•（2）G（B）L（B，C）•（3）（G（C）P（C））L（C，A）•设求证的公式为：•G：xy（G（x）