人工智能考点(矿大版-内容绝对给力)

矿大《人工智能》知识点总结————（考试重点）状态空间搜索的基本思想：就是通过搜索引擎寻找一个操作算子的调用序列，是问题从初始状态变迁到目标状态之一，而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的解答路径。搜索引擎可以设计为任意的实现搜索算法的控制系统。深度与宽度优先的本质不同优先搜索宽度优先搜索:根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。深度优先搜索：在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索适用场合深度优先——当一个问题有多个解答或多条解答路径，且只须找到其中一个时；往往应对搜索深度加以限制。宽度优先——确保搜索到最短的解答路径实现启发式搜索应考虑的关键因素：（1）搜索算法的可采纳性（在存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索法总能找到最短（代价最小）的解答路径，则称该状态空间中的搜索算法具有可采纳性，也叫最优性。）（2）启发式函数h(n)的强弱及其影响搜索算法AO*与A*的比较1AO*应用于与或图搜索，且搜索的是解图；而A*则应用于一般图即或图的搜索，且搜索的是解答路径。2AO*选择估算代价最小的局部解图加以优先扩展；而A*选择估算代价最小的路径加以优先扩展。3因为（2）表示的区别，AO*不需要考虑评价函数f(n)的分量g(n)，只需对新扩展出的节点n计算h(n)，以用于修正fi(n0);而A*则需同时计算分量g(n)和h(n)，以评价节点n是否在代价最小的路径上。4同样是因为（2）表示的区别，AO*应用LGS存放候选的带扩展局部解图，并依据fi(n0)值排序；而A*则应用OPEN表和CLOSE表分别存放带扩展节点和以扩展节点，并依据f(n)值排序。归结原理基本思想：首先把待证明的结论否定，并加入子句集，得到一个扩充的子句集S’。然后设法检验子句集S’是否含有空子句，若含有空子句，则表明S’是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。学习系统至少应该有环境、知识库、学习环节和执行环节4个基本部分。每部分作用：环境向系统的学习单元提供某些信息，学习单元利用这些信息修改知识库，增进执行单元的效能；执行单元根据知识库完成任务，同时把获得的信息反馈给学习单元。特化泛化正反例作用差异泛化策略：(1)采用自底向上的搜索假设空间的方式；(2)从第一个正例表示的最特化的假设开始；(3)系统依靠正例生成泛化的假设；(4)反例用来剪裁过于泛化的假设；(5)解描述——泛化程度最低；特化策略：(1)采用自顶向下的搜索假设空间的方式；(2)从最泛化的假设开始；(3)系统依靠反例生成特化的假设；(4)正例用来剪裁过于特化的假设；(5)解描述——特化程度最低；决策树算法ID3思想：ID3算法是一种自顶向下增长树的贪婪算法，在每个节点选取性能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都已经被使用过。优点：分类和测试速度快，特别适合于大数据库的分类问题。缺点：决策树的知识表示不如规则那样易于理解；两颗决策树进行比较，以判断它们是否等价的问题是子图匹配问题，是NP完全的；不能处理未知属性值的情况；对噪声问题没有好的处理方法。盲目搜索：只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。启发式搜索：是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。评估函数：评估函数f(x)的定义为从初始节点S0出发，约束性地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。其一般形式为f(x)=g(x)+h(x)，其中g(x)表示从初始节点S0到节点x的实际代价，h(x)表示从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)被称为启发式函数。问题归约：是人求解问题常用的策略，即把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。只有当这些子问题全部解决时，问题才算解决，问题的解答就由子问题的解答联合构成。1.置换是形如{t1/x1，t2/x2，···，tn/xn}的一个有限集。其中xi是变量，ti是不同于xi的项（常量、变量、函数），且xi≠xj（i≠j），i，j=1,2，···n。2.设有公式集{E1，E2,···En}和置换θ,使得E1θ=E2θ=···=Enθ，便称E1，E2，En是可合的，且θ被称为合一置换。可信度：可信度方法采用可信度CF(CertaintyFactor)作为不确定性的测度，通过对CF(H,E)的计算，探讨证据E对假设H的定量支持程度，因此，该方法也称为C-F模型。在C-F模型中，可信度最初定义为信任与不信任的差，即CF(H,E)=MB(H,E)-MD(H,E)，其中，CF是由证据E得到假设H的可信度，也称为确定性因子。MB(MeasureBelief,MB)称为信任增长度，它表示因为与前提条件E匹配的证据的出现，使结论H为真的信任的增长程度。MD(MeasureDisbelief,MD)称为不信任增长度，它表示因为与前提条件E匹配的证据的出现，对结论H的不信任的增长程度。人工智能的发展阶段:(1)孕育期(2)摇篮期(3)形成期-达特茅斯会议(4)发展期-基于知识的系统(5)实用期-神经网络的复兴(6)稳步增长期人工智能的研究方法:符号主义、连接主义、行为主义产生式系统的组成：规则库、综合数据库和推理机推理机步骤：匹配、冲突解决、操作产生式规则分类：①前提-结论型②条件-动作型产生式系统推理方式：正向推理、反向推理、双向推理语义网络推理过程：继承推理、匹配推理框架名、槽名、侧面名分清提高一般图搜索效率的关键：在于优化OPEN表中节点的排序方式，若每次排在表首的节点都在最终搜索到的解答路径上，则算法不会扩展任何多余的节点就可快速结束搜索。搜索最优策略的比较：宽带优先搜索、深度优先搜索，有界深度优先搜索、迭代加深搜索都可以用于生成和测试算法。宽度优先搜索需要指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性关系。迭代加深搜索对一颗深度受控的数采用深度优先的搜索，它结合了宽度优先和深度优先搜索的优点。和宽度优先搜索一样，它是最优的，也是完备的，但对空间要求和深度优先搜索一样比较适中。爬山法是实现启发式搜索的最简单的方法，只能向上，不准后退，从而简化了搜索算法，爬山法对于单一极值问题（登单一山峰）十分有效而又简便,对于具有多极值的问题无能为力——会错登上次高峰而失败：不能到达最高峰。MIN和MAX的基本思想：(1)当轮到MIN走步的节点时（取与时），MAX应考虑最坏的情况（即f(p)取极小值）。(2)当轮到MAX走步的节点时（取或时），MAX应考虑最好的情况（即f(p)取极大值）。(3)评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值。所以这种方法称为极大极小过程。α-β过程：如果能边生成博弈树，边进行估值的计算，则可能不必生成规定深度内的所有节点，以减少搜索的次数，这就是α-β过程。α-β过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此来提高算法的效率。合式公式的性质十种常用性质(1)双重否定：(P)P(2)蕴涵式转化：P→QP∨QP↔Q(P∧Q)∨(P∧Q)(3)狄.摩根定律：(P∨Q)P∧Q(P∧Q)P∨Q(4)分配律P∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)(5)交换律P∧QQ∧PP∨QQ∨P(6)结合律(P∧Q)∧RP∧(Q∧R)(P∨Q)∨RP∨(Q∨R)(7)逆否律P→QQ→P(8)量词否定(x)P(x)(x)(P(x))(x)P(x)(x)(P(x))(9)量词分配(x)[P(x)∧Q(x)](x)P(x)∧(x)Q(x)(x)[P(x)∨Q(x)](x)P(x)∨(x)Q(x)(10)约束变量的虚元化约束变量名的变换不影响合式公式的真值(x)P(x)(y)P(y)(x)P(x)(y)P(y))()|()()|(BpAiBpAipBAip)|()|(HEpHEpLS)|()|(HEpHEpLN)()|(HOLSEHO)()|(HOLNEHOCF(H,E)=MB(H,E)-MD(H,E)其他情况)(1)()](),/(max[1)(1),(HpHpHpEHpHpEHMB其他情况)()](),/(min[)(0)(1),(HpHpEHpHpHpEHMD)()|(,)()|()(0)()|(,0)()|(,)(1)()|(0),(HPEHPHPEHPHPMDHPEHPHPEHPHPHPEHPMBEHCFCF(H)=CF(H,E)×max{0,CF(E)}