人工智能复习大纲.doc

8何为状态图和与或图？图搜索与问题求解有什么关系？状态图是描述寻找目标或路径问题的有向图，即描述一个实体基于事件反应的动态行为，显示了该实体如何根据当前所处的状态对不同的时间做出反应的。与或图是一种系统地将问题分解为互相独立的小问题，然后分而解决的方法。与或图中有两种代表性的节点：“与节点”和“或节点”，“与节点”指所有的后续节点都有解时它才有解；“或节点”指各个后续节点均完全独立，只要其中有一个有解它就有解。关系：问题求解就是在一个图中寻找一个从初始节点到目标节点的路径问题，图搜索模拟的实际是人脑分析问题，解决问题的过程，它基于领域知识的问题求解过程。11. 什么是与或树？什么是可解节点？ 什么是解树？ 答：一棵树中的弧线表示所连树枝为“与”关系,不带弧线的树枝为或 关系。这棵树中既有与关系又有或关系，因此被称为与或树。 满足下列条件的节点为可解节点。 终止节点是可解节点；一个与节点可解，当且仅当其子节点全都可解；一个或节点可解，只要其子节点至少有一个可解。解树实际上是由可解节点形成的一棵子树,这棵子树的根为初始节点，叶为终止节点，且这棵子树一定是与树14. 请阐述状态空间的一般搜索过程。OPEN表与CLOSED表的作用是什么？ 答：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。 OPEN表用于存放刚生成的节点，对于不同的搜索策略，节点在OPEN表中的排序是不同的。 CLOSED表用于存放将要扩展或者已扩展的节点。15. 广度优先搜索与深度优先搜索各有什么特点？ 答：广度优先搜索就是始终先在同一级节点中考查,只有当同一级节点考查完之后,才考查下一级节点。或者说,是以初始节点为根节点，向下逐级扩展搜索树。所以,广度优先策略的搜索树是自顶向下一层一层逐渐生成的。 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进,直到不能再前进（到达叶子节点或受到深度限制） 时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝(即深度无限)，则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解(最短路径)。 广度优先搜索与深度优先搜索都属于盲目搜索。3.8 判断下列公式是否为可合一，若可合一，则求出其最一般合一。(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b)(4) P(f(y), y, x), P(x, f(a), f(b) (5) P(x, y), P(y, x)解：(1) 可合一，其最一般和一为：=a/x, b/y。(2) 可合一，其最一般和一为：=y/f(x), b/z。(3) 可合一，其最一般和一为：= f(b)/y, b/x。(4) 不可合一。(5) 可合一，其最一般和一为：= y/x。第1章 ：绪论1. 人工智能的主要学派：a) 符号主义学派（Sysmbolicism），又称为逻辑主义学派，心理学派，计算机学派。符号主义认为知识是智能的基础，人工智能的核心问题是知识的表示与知识推理。（功能模拟）b) 联结主义学派（Connectionism）：又称为仿生学派，生理学派。用人工神经网络模仿人类智能。（结构模拟）c) 行为主义学派（Actionism）：又称为进化主义学派，控制论学派。认为智能取决于感知，表现为行动。（行为模拟）2. 人工智能的研究和应用领域（10个）a) 定理证明b) 专家系统c) 机器学习d) 自然语言理解e) 智能检索f) 机器学习g) 自动程序设计h) 组合调度问题i) 模式识别j) 机器视觉第2章 ：知识表示法1. 一阶谓词逻辑表示法2.1.1：一阶谓词逻辑1. 命题：它的取值为真或假2. 谓词3. 谓词公式4. 谓词公式的解释：对于每一个解释，谓词公式都可以求出一个真值5. 谓词公式的永真性，可满足性，不可满足性永真性：如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的。可满足性：对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T。不可满足性：如果谓词公式P对于个体域D的任何一个解释都取得真值为F。6. 谓词公式的等价性。设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真值，则称公式P和Q在D上是等价的。如果D是任意的个体域，则称P和Q是等价的。记为PQ公式：2.1.2：一阶谓词表示方法1. 一阶谓词表示方法例题：2. 一阶谓词表示方法的优点。自然性，准确性，严密性，容易实现。3. 一阶谓词表示方法的缺点不能表示不确定性的知识，组合爆炸，效率低。2. 产生式表示方法2.2.2：产生式系统的分类1. 可交换的产生式系统2. 可分解的产生式系统3. 可恢复的产生式系统产生式表示法的特点第3章 ：搜索方法3.1问题求解过程的形式表示3.1.1状态空间表示法3.1.2与/或图表示法3.2状态空间的搜索方法盲目搜索算法1. 无代价的宽度优先搜索：在搜索树的生成过程中，只有对搜索树中同一层的所有节点都考察完之后，才对下一层的节点进行考察。2. 无代价的深度优先搜索：在搜索树的生成过程中，对open表中同一层的节点只选择表中一个节点进行考察和扩展，只有当这个节点是不可扩展的，才选择同层的兄弟节点进行考察和扩展。3. 宽度优先和深度优先的区别a) 宽度优先搜索生成的子节点放入open表的表尾，深度优先搜索生成的子节点放入open表的表首。b) 如果问题有解，那么宽度优先搜索总能找到最优解。宽度优先搜索时完备的，深度优先搜索是非完备的。c) 如果搜索最大深度设置合理，那么深度优先搜索能找到一条解路径，但不一定是最优解。深度优先搜索的时空开销小于宽度优先。例子：提示：无代价深度优先搜索的open表是将新扩展生成的子节点按节点序号从小到大排序后放入open表首有代价深度优先搜索的open表是将新扩展的子节点按照价值从小到大放入open表首有代价宽度优先搜索的open表中所有节点按代价从小到大排序2. 启发式搜索算法例子：3.3与或图的搜索方法：启发式搜索算法的解树的代价例子：第4章 ：逻辑推理4.1推理的基本概念推理的控制策略1. 推理方向a) 正向推理：从用户提供的初始已知事实出发，在知识库KD中找到当前可用的知识，构成可用知识集KS，然后按照某种冲突消解策略从KS中选中一条知识进行推理，并将推出的新事实加入到数据库DB中作为下一次推理的已知事实，在此之后再在知识库中选取可用知识进行推理，如此反复进行这一过程，知道求的要求的解或知识库中再无可用的知识为止。b) 逆向推理：首先选择一个假设目标，然后寻找支持该假设的依据，若所需的证据都能找到，则说明假设是成立的，若无论如何都找不到，则说明不成立，此时需要选定新的假设。c) 混合推理2. 冲突消解策略目前已有多种消解策略，其基本思想都是对知识进行排序1） 按针对性排序2） 按匹配度排序3） 根据领域问题的特点排序4.1.3模式匹配及其变量代换4.2归结演绎推理4.2.1谓词公式化为子句集的方法4.2.2归结原理4.2.3归结反演4.3基于归结反演的问题求解4.4归结反演的改进策略1） 删除策略2） 限制策略第5章 ：专家系统1.专家系统的概念：专家系统是一种模拟人类专家解决领域问题的计算机软件系统。2.专家系统的结构与开发方法a) 知识库：以某种存储结构存储领域专家的知识b) 全局数据库：（黑板）用于存储求解问题的初始数据和推理过程中得到的中间数据，以及最终的推理结论。c) 推理机：根据全局数据库的当前内容，从知识库中选择匹配成功的可用规则，并通过执行可用的规则修改数据库中说的内容，直至推理出来问题的结论。d) 解释器：用于向用户解释专家系统的行为。e) 用户接口：系统与用户进行对话的界面。f) 知识获取：把知识转换为知识内部表示模式存储到知识库。第6章 ：模糊推理1. 模糊集合的定义与运算（大题）2. 模糊知识表示与模糊匹配（概念）a) 模糊知识表示模糊