人工智能复习大纲

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