人工智能期末整理复习资料.docx

人工智能Artificial Intelligence期末知识点整理题型：一、 选择题（15题，每题2分，共30分）主要考查基本概念二、 问答题（7题，每题10分，共70分）主要考算法具体应用于一个小问题必考：与或树的宽度、深度优先搜索算法（必考）博弈树的极大极小搜索过程（必考）知识点整理：第一部分课程综述1、 人工智能英语：Artificial Intelligence2、 人工智能（学科）：是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期目标在于研究用机器来模仿和执行人脑的某些智能功能，并开发相关的理论和技术。3、 课程所讲内容： 问题求解经典人工智能（符号主义）所研究的内容 谓词逻辑与推理 计算智能(神经计算) 计算智能（连接主义）4、 主要学派 符号主义：又称逻辑主义、心理学派或计算机学派-物理符号系统假设和有限合理性原理。 连接主义：又称仿生学派、生理学派-神经网络。 行为主义：又称计算主义、控制论学派-控制论及感知-动作型控制系统。5、 每一部分的内容安排原则：问题（知识）的表达-表达相应的求解技术-求解软件实现的平台或者环境-平台6、 每部分概述 空间求解部分知识表达搜索技术状态空间法宽度优先、深度优先等代价优先搜索、有序搜索算法问题规约法与或树的宽度、深度优先搜索技术博弈问题（也有状态空间法）和极大极小过程实现平台建议使用常用的高级语言（C/C+等） 谓词逻辑与推理部分表达方法：谓词逻辑求解方法：消解原理、消解反演算法实现平台：Visual-Prolog语言 人工神经网络数据采集与表示方法：用一个向量及其性质（类别或函数值）来描述每一个样本。求解方法：针对不同的问题，选择一个神经网络模型，并用训练样本集确定网络的权值。实现平台：Matlab或其他高级语言。第二部分问题求解1、2、 状态空间法与图的搜索技术 状态空间法表示问题的关键：状态与操作符状态：为了描述某一类不同事物间的差别引入的一组最少变量的有序集合算符（操作符）：使问题从一个状态变换到另一状态的手段 求解问题：寻找从初始状态到目标状态的某一个操作符序列状态空间法的求解过程：用有向图来表示对应关系：状态结点操作符有向弧 状态空间法的解：从初始状态到目标状态的操作符序列 图中的解：从起始节点到目标节点的一条路径 求解思路：边扩展节点边找解的搜索思想 图的搜索技术分为n 盲目搜索技术（宽度、深度、代价优先搜索技术）u 宽度优先：先扩展出来的节点优先（OPEN 为队列），后继节点有目标节点结束例子！思路：按照操作符顺序，从第一个开始，先从宽度开始，拓展一层，从左到右排好（先-后），然后，从先拓展出来的结点（即最左边的）开始进行拓展，注意已经拓展过的结点不拓展，所以4不行，走不通的结点也是不行，如3。注意要一次用完所有的操作符，即找到目标结点也要继续拓展完这个结点的。u 深度优先：后者扩展出来的节点优先（OPEN 为堆栈） ，且有深度限制，后继节点有目标节点结束例子！思路：按照操作符顺序，从第一个开始，运用操作符，拓展第一层，拓展的结点按照从右到左的顺序存放（后-先），然后，从后拓展出来的结点（即最左边的）开始进行拓展，接着往深处搜索直到深度界限，回溯。同样注意已经拓展过的结点不拓展，注意要一次用完所有的操作符，即找到目标结点也要继续拓展完这个结点的。u 代价优先（等代价）：到起始节点代价小的节点优先（ OPEN 为线性表），具有最小代价的节点是目标节点时结束例子！思路：按照操作符顺序，从第一个开始，拓展第一层，拓展的结点按照从左到右的顺序存放（先-后），然后，计算出各个点的代价，选择代价最小的拓展。可以拓展拓展过的结点，注意要全部走完才能判断出出口。n 启发式搜索技术（有序搜索算法）u 有序搜索算法：估价函数值小的节点优先，有解的结束条件：具有最小估价函数值的节点是目标节点例子！思路：按照操作符顺序，从第一个开始，拓展第一层，拓展的结点按照从左到右的顺序存放（先-后），然后，计算出各个点的估计函数值，选择值最小的拓展。同样注意已经拓展过的结点不拓展。差别：选取待扩展节点的规则不同，并可以OPEN表的不同数据结构来体现算法有解的终止条件不同3、 问题归约法、与或树搜索技术 问题归约法表示问题的关键：原始问题描述、本原问题描述、操作符n 操作符：将问题转换或分解为子问题的手段n 本原问题：一组可以直接得出答案的简单问题 问题归约法的求解过程：用与或图来表示 判断节点是否可解的方法：n 终叶节点是可解节点n 无后继节点的非终叶节点是不可解节点n 用倒推的方法来逐步判断其他节点是否可解 与或图有解的条件是：起始节点（根节点）可解（通过倒推来判断） 与或图的解图：由最少可解节点所构成的子图，这些可解节点能够使问题的起始节点可解 与或树：与或图的特例，除了根节点外，任何一个节点只有一个父节点 与或树的搜索技术： n 宽度优先：先扩展出来的节点优先（OPEN表是队列）例子！思路：到可解结点后倒退回去！n 深度优先：后扩展出来的节点优先（OPEN表是堆栈），且有深度限制。注意与宽度的操作符的顺序不一样！这里讲后拓展的放在左边。 图、与或树的宽度、深度优先搜索算法之间的差别：n 图搜索技术是找到目标节点或无法扩展而结束算法n 与或树搜索技术是找到终叶节点后通过倒推来判断起始节点是否可解而结束算法4、 博弈问题的表达、博弈树的搜索技术 双人博弈问题的特殊之处：n 棋局：相当于状态空间法中的状态n 走棋：相当于问题归约法的节点扩展（生成或节点、与节点） 博弈树是一棵特殊的与或树，其节点对应棋局（相当于状态），与节点、或节点隔层交替出现 博弈树搜索的极大极小过程分成：n 宽度优先扩展节点（深度必为偶数），并计算最底层端节点的静态估计函数值n 用倒推的方法（自己下的棋取大者，对手下的棋取小者）计算出其余各层节点的静态估计函数值，最后决定走哪一步棋（全填0-计算共有几条成功路线全填x-计算共有几条成功路线-相减得值）例子！（只需要走一层，看两步即可）第三部分谓词逻辑与推理1、 谓词逻辑法数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑。谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言。人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）。2、 模式匹配-置换和合一说明：1、合一算法是消解原理的基础。2、合一算法中的公式集就是从谓词合适公式化成的子句集。例子！3、 谓词公式化成子句集（九步）4、 消解演绎与消解反演例子！看作业！5、 消解推理规则6、 一些定义 原子公式：原子命题（0元谓词）和谓词 基本式：原子公式或原子公式的非 正基本式：不带“非号”的原子公式 负基本式：带“非号”的原子公式 Horn子句：最多只含有一个正基本式的子句（只含一个正基本式或者不含正基本式） Horn子句集：每一个子句均为Horn子句的子句集7、 Prolog语言 概念：Prolog语言是以一阶谓词逻辑的Horn 子句集为语法，以Robinson的消解原理为工具，加上深度优先的控制策略而形成的人工智能通用程序设计语言。 Visual Prolog 程序的基本结构：domains（域段，说明变量类型，无句号、可以缺省）predicates. （谓词段，说明谓词，无句号）clauses. （子句段，程序主体，必须有句号）goal （目标段，表达目标或问题，必须有句号）例子！5、编写Prolog程序，并上机调试通过：已知三个前提F1:：王(Wang)先生是小李(Li)的老师F2：小李与小张(Zhang)是同班同学F3：如果x与y是同班同学，则x的老师就是y的老师。问题：小张的老师是谁？ 例子！第四部分人工神经网络1、 神经元的动作或工作原理： 求加权和 与阈值比较 用激活函数得到输出激活函数有：阶跃函数：(-, + )0,+1符号函数：(-, + )-1,+1线性函数：Sigmoid函数：(-, + )(0,+1)或者(-1,+1)2、 神经网络模型 反向传播神经网络（多层感知器反向传播训练算法）(BP) BP网络n 针对分类与回归问题，如何确定网络结构n 反向传播算法的基本思想n 公式推导的关键技术BP网络的结构 BP网络的结构3、 解决模式分类问题时，确定网络结构的原则 输入层的神经元个数：输入样本的维数（有阈值数，加1） 中间层的层数及其神经元个数：使用者确定 输出层的神经元个数：类别数（多类取多个，两类取一个） 激活函数：所