人工智能复习考试

AI：20世纪70年代以来被称为三大科学技术成就之一，21世纪三大尖端技术之一；是一门研究如何使计算机系统显示智能行为的学科，即研究如何让计算机完成那些过去只有人才能做的富有智能的工作。 Nilsson（知识）Winston（功能）Feigenbaum（系统）。研究目标：近期:使计算机更聪明、更有用.主要研究依赖于用计算机去模拟人类某些智能行为的基本理论、基本技术和基本方法；远期:探讨智能的基本机理，研究如何利用自动机去模拟人的某些思维过程和智能行为，最终构造智能机器，使其高效率地解决问题。发展概况：研究领域：技术。1956达特茅斯产生；表处理语言LISP、PROLOG系统。发展概况：研究领域：技术。自然语言理解、知识表示、自动推理、机器学习、计算机视觉、机器人博弈方面。1991博弈方面。1991年8月悉尼举行的第12届国际人工智能联合会议上深蓝”的深蓝”以2:4输掉了第一次的比赛，但在一年后的第二次比赛中IBM的DeeThought2以1:1战平澳大利亚象棋冠军约翰森。卡斯珀罗夫和人机大战，虽然，以3.5:2.5击败世界棋王，可见，在博弈方面，人工智能取得了很出色的成绩。三个流派：符号智能、计算智能、群体智能。产生式表示形式：前提结论、事实。基本结构：综合数据库、产生式规则、控制系统。特点：综合数据库：依据推理情况内容动态变化，存放初始状态、已知事实、推理的中间结果及结论等。规则库：存放一系列规则，有相对固定的格式，规则独立，具有高度模块化。用于描述状态的转换关系、前提与结论间的因果关系等。控制系统：如何应用规则，与问题无关，可分匹配、选择（冲突解决）和应用（操作）三步。关系:综合数据库是基础，产生式规则是进行推理的依据，控制系统是中枢。控制策略分类：不可撤回方式：利用问题给出的局部知识来决定如何选取规则，不必考虑撤回已用过的规则；试探方式：回溯方式，建立一个回溯点和图搜索方式，状态变化过程用图结构记录下来。产生式系统的类型：正向、逆向、双向产生式系统；可交换的产生式；可分解的产生式系统。爬山法停滞三种情况:局部极大点、平顶、山脊。搜索策略的任务:确定选择规则的方式。

两种基本方式：盲目搜索(无信息引导：按固定的步骤;启发式搜索(有：考虑领域的知识。状态空间：求任一解路：回溯、爬山、宽度、深度、限定范围搜索、好的优先搜索.求最佳解路：大英博物馆法、分支限界法、动态规划法、最佳图搜索法A*.问题归约：求与或图：AO*、极大极小法、aP剪支法、启发式剪支法搜索：通过搜索某部分状态空间,以求得由规则序列组成的一个解答的过程，它对应于将一个隐式图中包含目的节点的一部分状态变为显式图的过程。,当遇到“死胡同”就查看该节点是否还有其他的子节点未被扩展，如如果找到目标，就成功退出搜索，返回解的路径。,当遇到“死胡同”就查看该节点是否还有其他的子节点未被扩展，如如果找到目标，就成功退出搜索，返回解的路径。呈现出递归的图搜索策略：分3种情况考虑未出现过的{mi}={mj}U{mk}U{ml}；mj为Open图搜索策略：分3种情况考虑未出现过的Closed中的子节点。有解时，一定能找到解。可能找不到解。mk表示已出现在Open中的子节点，ml表示已出现在宽度优先：按生成次序加入到Open表后端，先进先出；深度优先：按生成次序加入到OpenClosed中的子节点。有解时，一定能找到解。可能找不到解。A算法：控制策略，OPEN中的节点按f值从小到大排序；结论，A是好优先搜索策略。A*:在算法A中，当h(n)Wh*(n)。完备性：如果问题有解，贝U算法一定能找到解；可采纳性：如果问题有解，则算法一定能找到最佳解；最优性：设A1和A2为某问题求解的两个A*算法，若对所有非目标节点均有h1(n)<h2(n)wh*(n)贝U算法A1展开的节点数目至少和A2一样多。结论：A*算法结束前，OPEN表中必存在f(n)wf*(S)的节点(n是在最佳路径上的节点)；OPEN表上任一具有f(n)wf*(S)的节点n,最终都将被A*选作扩展的节点；A*选作扩展的任一节点，有f(n)wf*(S)。止/步分问题归约法:止/步分与或图搜索：目的在于标明起始节点是有解的；搜索不是去寻找到目标节点的一条路径，而是寻找一个解图。AO*与A*算法的区别：评价函数只考虑h（n:理由:算法有自下而上的修正费用的的操作,实际上局部解图费用值的估计是在起始节点S比较，计算g既无必要也不可能；不能优先扩展具有最小费用的节点：理由：K-连接符连接的有关子节点对父节点的可解性及费用值的估计都会产生影响;仅适用于无环图 ,否则耗散值递归计算不收敛:方法:当新生成的节点已在图中时,判断是否为正被扩展节点的先辈节点；控制策略不同:没有OPEN表和CLOSED表,只用生成的解图结构G,h（n是最佳解图的费用估计.博弈树的极大极小搜索法：预先考虑双方对弈若干步之后的局势，从当前侯选的走步中选一个相对好的走步来走，即在有限搜索深度范围内进行求解。极大极小搜索缺陷:把生成树和棋局估值两个过程完全分离，即先生成全部的搜索树，然后再进行端节点估值和倒推值计算，这导致效率降低。-搜索：若两个过程同时进行，再依一定的条件判断，有可能尽早剪掉一些无用的分支，那么就可能减少搜索量。极大值层的倒推值下界值永不下降;极小值层的倒推值上界值永不上升。剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值，即（先辈层》（后继层），则可终止该MIN层中这个MIN节点以下的搜索，并设置这个MIN节点的最终的倒推值为.（位置：MIN层的剪枝剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即 （后继层＞先辈层），则可终止该MAX层中这个MAX节点以下的搜索，并设置这个MAX节点的最终倒推值为.（位置：MAX层的剪枝遗传算法：物竞天择、适者生存，Holland;选择、交配、变异3个主要操作。蚁群算法：模仿蚂蚁群体在觅食过程中所体现出的智能行为而提出的。优点 :良好的鲁棒性、正反馈、及分布式并行计算等;缺点:迭代次数过多,易陷入局部最优,精度欠佳.前束范式：若一个谓词公式P的所有量词均非否定地出现在P的前部，且量词辖域是整个公式，称P为前束范式.如F（Q1x1…（QnxnM;（Qi:2值,M:析取式SKOLEM范式:消去前束范式中的所有量词后所得到的谓词公式,也称SKOLEM标准型。:若变量不受全称量词的约束（左边无,可用任意常量代替该变量;否则,用以其为因变量的函数代替该存在量词.,函数形式（几元函数依赖于受几个全称量词约束。:省略.合成置换:有时需对表达式进行多次置换，如用s1、s2依次进行置换（即（Es1）s2）,这时可以把两个置换合成为一个置换（记为s1s2）

知识类型：叙述型知识、过程型知识、控制型知识。知识模型的变换：同构变换：使问题更明确，便于求解；同构问题的解答等价于原始问题的解答。同态变换：使问题更加简化，易于求解。语义网络：是一种采用网络形式表示人类知识的方法；形式：带标识的有向图；优点：自然性，联想性，效率较高；缺点：不严格，不便于表达判断性的和深层知识.框架定义：人们无法把过去的经验都一一存储在脑子里，而只能以一个通用的数据结构的形式存储以往的经验。这样的数据结构，称为框架。区别 ：语义网络注重表示对象间的关系，而框架更注重对象的内部结构.归结反演存在的问题：归结方法不自然、效率低、可能会丢失控制信息* … fi}比丿*1 = N条件概率：设A和B是某随机试验中的两个事件，如果在事件B发生的条件下考虑事件A发生的概率，就称它为事件A的条件概率，记P(A|B)。若P(B)>0，则RB)-X A)/'1 全概率公式:21叭少)2A)£旳)晌Bayes公式:Bayes公式:摩根律：~(A