人工智能技术导论总复习

第1章人工智能概述•什么是人工智能？人工智能的研究目标和意义？•人工智能的研究学派、途径与方法•人工智能的研究目标•人工智能的分支领域（基于应用领域）•人工智能基本技术第3章图搜索技术•状态图知识表示•状态图搜索–穷举式搜索–启发式搜索–加权状态图搜索•与或图知识表示•与或图搜索–启发式与或树搜索•博弈树搜索–极小极大分析法–α-β剪枝状态图知识表示•状态空间（StateSpace）–问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。–一般用赋值有向图，包含•S：问题的可能有的初始状态的集合；•F：操作的集合；•G：目标状态的集合。•状态空间常记为三元序列S，F，G状态空间中问题求解（1）•在状态空间图中，问题求解过程转化为在图中寻找从初始状态S0出发到达目标状态Sg的路径问题，也就是寻找操作序列的问题。•状态空间的解为三元组S0,O,Sg–S0：某个初始状态–Sg：某个目标状态–O：把Qs变换成Qg的有限的操作序列{O1,O2,…,On}–状态转换图S1S3S2…O1O2O3O4S0SgOn状态空间中问题求解（2）•状态图搜索：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。•状态图的解：搜索成功后，从目标结点反向沿搜索树按所作标记追溯一直到初始结点，所得到一条从初始结点到目标结点的路径就是问题的一个解。状态图搜索（1）•穷举式搜索–广度优先–深度优先–有界深度优先•启发式搜索–全局择优（广度优先搜索+h(x)）–局部择优（深度优先搜索+h(x)）状态图搜索（2）•加权状态图搜索–分支界限（广度优先搜索+g(x)）–最近择优/瞎子爬山（深度优先搜索+g(x)）•A算法（一般树式搜索算法+f(x)）•A*算法（h(x)=h*(x)）或图（状态图）知识表示搜索穷举式搜索启发式搜索加权状态图搜索广度优先深度优先全局择优(最好优先)局部择优(瞎子爬山)分支界限(最小代价优先)最近优先(瞎子爬山)A算法和A*算法与或图知识表示•一个复杂的问题P常常可以归约为与之等价的一组子问题，当这些问题全部可解时，问题可解；任何一个子问题无解时，都将导致原问题P无解。即一个问题与一组子问题的与等价。•一个复杂的问题P常常可以分别归约为与之等价的一组子问题，其中任何一个子问题可解时，问题可解；全部子问题无解时，原问题P无解。即一个问题与一组子问题的或等价。•与或图知识表示是一个三元组（Q0,F,Qn）–Q0：表示初始问题–F：表示问题变换规则集–Qn：表示本原问题集与或图知识表示（1）•与或图的几个概念–直接可解的问题称为本原问题。–本原问题对应的节点称为终止节点。–无子节点的节点称为端节点。–子节点为与关系，则该节点为与节点。–子节点为或关系，则该节点为或节点。•与或图一般表示问题的变换过程，就是从原问题出发，运用某些规则不断的进行问题的分解（得到与分支）和变换（得到或分支），而得到一个与或图，与或图的节点一般代表问题，整个图就表示问题空间。与或图搜索（1）与或图知识表示搜索盲目式搜索启发式搜索博弈树搜索穷举式搜索盲目碰撞搜索广度优先深度优先与或图搜索（2）•与或树搜索–可解性判定–广度优先、有界深度优先•与或图搜索：与或图中搜索不像在或图（状态图）中只是寻找目标节点，而是边扩展节点边进行逻辑判断，以确定初始结点是否可解。一旦确定初始节点的可解性，搜索停止。根据返回指针可从搜索树中得到一个解图（树）。•与或图的解：是由可解节点形成的一个子图（树），这个子图（树）的根为初始节点，叶为终止节点。与或图搜索（3）•有序搜索–解树（树根）代价的计算方法•和代价法•最大代价法–有序搜索过程启发式与或树搜索•解树代价的计算方法令：g(x)表示节点x的代价，c(x,yi)表示节点x到其子节点yi的代价(即边xyi的代价)，yi是x的子节点.则(1)若x是终止节点，g(x)＝0；(2)若x是或节点(3)若x是与节点，则有两种计算公式。①和代价法②最大代价法(4)对非终止的端节点x，g(x)＝∞niiiygyxcxg1)}(),({)()}(),({max)(1iiniygyxcxg)}(),({min)(1iiniygyxcxgxy1y2c(x,y1)c(x,y2)xy1y2c(x,y1)c(x,y2)启发式与或树搜索a1a2a3a4a5a6b1b2b4b3b5S4456245732443例：如下图所示的与或树，a4,a5,a6,b3,b5是终止结点，求其解树启发式与或树搜索左解树节点a6a5a4a3a2a1S和代价000462125最大代价000441014右解树节点b5b4b3b2b1S和代价030151923最大代价030101418补充示例：如下图所示的与或树，其解树和节点相应代价如下博弈树搜索•极小极大分析法•α－ß剪枝技术极小极大分析法（1）•极小极大分析法的基本思想–设博弈的双方中一方为A，另一方为B。然后为其中的一方(始终站在A的立场上)寻找一个最优行动方案。–为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较。–为计算得分，需要根据问题的特性信息定义一个估价函数f(p)(p是端节点)，用来估算当前博弈树端节点的得分。这时估算出来的得分为静态估值。方有利对势均力敌方有利对B00A0)(pf方必胜方必胜BA)(pf极小极大分析法（2）–当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：•对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；•对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。–如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。极小极大分析示例倒推值的计算2-12-234-51322343323α－ß剪枝技术–对于一个与节点MIN,若能估计出其倒推值的上确界β,并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β,则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。–对于一个或节点MAX,若能估计出其倒推值的下确界α,并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β,即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为β剪枝。α－ß剪枝技术(1)2931－1－1368－1203－574－26－18－7－103ABCEHJKPQDLDRTIFGMUNVS2≥2≤1≤－12≤222≥26≥60≥0≤0≤－5060第4章基于遗传算法的随机优化搜索•遗传算法的基本概念•遗传算法和图搜索在优化搜索和问题求解方面的对比第5章基于谓词逻辑的机器推理•相关定义及概念•化子句集的过程•命题逻辑的归结原理•替换与合一•谓词逻辑中的归结原理•应用归结原理求取问题答案•归结策略化子句集的过程•1、消去蕴含词和等值词。•2、使否定词仅作用于原子公式。•3、适当改名使量词间不含同名指导变元。•4、消去存在量词。•5、消去全称量词。•6、化公式为合取范式。•7、适当改名，使子句间无同名变元。•8、消去合取词，以子句为元素组成一个集合S。命题逻辑的归结原理•设C1，C2是命题逻辑中的两个子句C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1、C2中分别删除L1、L2，再将剩余部分析取起来，记构成的新子句为C12，则C12为C1、C2的归结式。替换与合一•一个替换（Substitution）是形如{t1/x1,t2/x2,…,tn/xn}的有限集合•设σ是原子公式集S的一个合一，如果对S的任何一个合一θ都存在一个替换λ，使得θ＝σ•λ则称σ为S的最一般合一(MostGeneralUnifier),简称MGU。谓词逻辑中的归结原理•C1，C2为无相同变元的子句；L1，L2为其中的两个文字，L1和¬L2有最一般合一σ；C1，C2的二元归结式（二元消解式）为：C1σ－{L1σ}）∪（C2σ－{L2σ}）应用归结原理求取问题答案（1）先为待求解的问题找一个合适的求证目标谓词；（2）再对目标否定子句增配（以析取形式）一个辅助谓词，该谓词的变元必须与对应目标谓词中的变元完全一致；（3）进行归结；（4）当归结是刚好只剩下辅助谓词时，辅助谓词中原变元位置上的项就是所求的结果。归结策略•删除策略•支持集策略•线性归结策略•输入归结策略•单元归结策略•祖先过滤型策略第6章产生式系统•产生式系统的组成•产生式系统的运行过程•产生式系统有哪几种推理方式？各自有什么特点.•产生式系统的控制策略与常用算法（正向，反向）第7章知识表示•框架•语义网络•类和对象第8章不确定性知识的表示和推理•确定性理论•主观贝叶斯方法•证据理论•贝叶斯网络•模糊逻辑第9章机器学习•机器学习的原理•机器学习分类•机器学习的方法•符号学习：决策树学习（ID3算法）•连接学习：权值修正学习（BP算法）第12章专家系统•什么是专家系统？有哪些特征？•专家系统的结构？每部分功能是什么？•专家系统的应用与发展？考试相关•考试题型–简答题（25%）–应用题（65%）–其他（10%）•成绩计算–卷面成绩*80%+平时成绩*20%内容分布•第1章：5%•第3章：26%•第4章：5%•第5章：22%•第6章：5%•第7章：5%•第8章：12%•第9章：5%•第12章：5%•其他：10%