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

《人工智能考点(矿大版-内容绝对给力).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、矿大《人工智能》知识点总结————（考试重点）状态空间搜索的基本思想：就是通过搜索引擎寻找一个操作算子的调用序列，是问题从初始状态变迁到目标状态之一，而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的解答路径。搜索引擎可以设计为任意的实现搜索算法的控制系统。深度与宽度优先的本质不同优先搜索宽度优先搜索:根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。深度优先搜索：在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索适用场合深度优先——当一个问题有多个解

2、答或多条解答路径，且只须找到其中一个时；往往应对搜索深度加以限制。宽度优先——确保搜索到最短的解答路径实现启发式搜索应考虑的关键因素：（1）搜索算法的可采纳性（在存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索法总能找到最短（代价最小）的解答路径，则称该状态空间中的搜索算法具有可采纳性，也叫最优性。）（2）启发式函数h(n)的强弱及其影响搜索算法AO*与A*的比较1AO*应用于与或图搜索，且搜索的是解图；而A*则应用于一般图即或图的搜索，且搜索的是解答路径。2AO*选择估算代价最小的局部解图加以优先扩展；而A*选择估算代价最小的路径加以优先扩展。3因为（2）表示的区别，AO*不

3、需要考虑评价函数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、导出空子句或不能继续归结为止。学习系统至少应该有环境、知识库、学习环节和执行环节4个基本部分。每部分作用：环境向系统的学习单元提供某些信息，学习单元利用这些信息修改知识库，增进执行单元的效能；执行单元根据知识库完成任务，同时把获得的信息反馈给学习单元。特化泛化正反例作用差异泛化策略：(1)采用自底向上的搜索假设空间的方式；(2)从第一个正例表示的最特化的假设开始；(3)系统依靠正例生成泛化的假设；(4)反例用来剪裁过于泛化的假设；(5)解描述——泛化程度最低；特化策略：(1)采用自顶向下的搜索假设空间的方式；(2)从最泛化的假设开始；(3)系统依靠反例生成特化的假设；(4)正例用来剪裁过于

5、特化的假设；(5)解描述——特化程度最低；决策树算法ID3思想：ID3算法是一种自顶向下增长树的贪婪算法，在每个节点选取性能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都已经被使用过。优点：分类和测试速度快，特别适合于大数据库的分类问题。缺点：决策树的知识表示不如规则那样易于理解；两颗决策树进行比较，以判断它们是否等价的问题是子图匹配问题，是NP完全的；不能处理未知属性值的情况；对噪声问题没有好的处理方法。盲目搜索：只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解

6、。启发式搜索：是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。评估函数：评估函数f(x)的定义为从初始节点S0出发，约束性地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。其一般形式为f(x)=g(x)+h(x)，其中g(x)表示从初始节点S0到节点x的实际代价，h(x)表示从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)被称为启发式函数。问题归约：是人求解问题常用的策略，即把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。只有当这些子问题全部解

7、决时，问题才算解决，问题的解答就由子问题的解答联合构成。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(Certaint