1、人工智能Artificial Intelligence期末知识点整理题型:一、 选择题(15 题,每题 2 分,共 30 分)主要考查基本概念二、 问答题(7 题,每题 10 分,共 70 分)主要考算法具体应用于一个小问题必考:与或树的宽度、深度优先搜索算法(必考)博弈树的极大极小搜索过程(必考)知识点整理:第一部分 课程综述1、 人工智能英语:Artificial Intelligence2、 人工智能(学科):是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期目标在于研究用机器来模仿和执行人脑的某些智能功能,并开发相关的理论和技术。3、 课程所讲内容: 问题求解 经典人工智能
2、(符号主义)所研究的内容 谓词逻辑与推理 计算智能(神经计算) 计算智能(连接主义)4、 主要学派 符号主义:又称逻辑主义、心理学派或计算机学派-物理符号系统假设和有限合理性原理。 连接主义:又称仿生学派、生理学派-神经网络。 行为主义:又称计算主义、控制论学派-控制论及感知-动作型控制系统。5、 每一部分的内容安排原则:问题(知识)的表达-表达相应的求解技术-求解软件实现的平台或者环境-平台6、 每部分概述 空间求解部分知识表达 搜索技术状态空间法 宽度优先、深度优先等代价优先搜索、有序搜索算法与或树的宽度、深度优先搜索技术问题规约法博弈问题(也有状态空间法)和极大极小过程实现平台 建议使用
3、常用的高级语言(C/C+等) 谓词逻辑与推理部分表达方法:谓词逻辑求解方法:消解原理、消解反演算法实现平台:Visual-Prolog 语言 人工神经网络数据采集与表示方法:用一个向量及其性质(类别或函数值)来描述每一个样本。求解方法:针对不同的问题,选择一个神经网络模型,并用训练样本集确定网络的权值。实现平台:Matlab 或其他高级语言。第二部分 问题求解1、2、 状态空间法与图的搜索技术 状态空间法表示问题的关键:状态与操作符状态:为了描述某一类不同事物间的差别引入的一组最少变量的有序集合算符(操作符):使问题从一个状态变换到另一状态的手段 求解问题:寻找从初始状态到目标状态的某一个操作
4、符序列状态空间法的求解过程:用有向图来表示对应关系:状态结点操作符有向弧 状态空间法的解:从初始状态到目标状态的操作符序列 图中的解:从起始节点到目标节点的一条路径 求解思路:边扩展节点边找解的搜索思想 图的搜索技术分为 盲目搜索技术(宽度、深度、代价优先搜索技术) 宽度优先:先扩展出来的节点优先(OPEN 为队列) ,后继节点有目标节点结束例子!思路:按照操作符顺序,从第一个开始,先从宽度开始,拓展一层,从左到右排好(先-后) ,然后,从先拓展出来的结点(即最左边的)开始进行拓展,注意已经拓展过的结点不拓展,所以 4 不行,走不通的结点也是不行,如 3。注意要一次用完所有的操作符,即找到目标
5、结点也要继续拓展完这个结点的。 深度优先:后者扩展出来的节点优先(OPEN 为堆栈) ,且有深度限制,后继节点有目标节点结束例子!思路:按照操作符顺序,从第一个开始,运用操作符,拓展第一层,拓展的结点按照从右到左的顺序存放(后-先) ,然后,从后拓展出来的结点(即最左边的)开始进行拓展,接着往深处搜索直到深度界限,回溯。同样注意已经拓展过的结点不拓展,注意要一次用完所有的操作符,即找到目标结点也要继续拓展完这个结点的。 代价优先(等代价):到起始节点代价小的节点优先( OPEN 为线性表) ,具有最小代价的节点是目标节点时结束例子!思路:按照操作符顺序,从第一个开始,拓展第一层,拓展的结点按照
6、从左到右的顺序存放(先-后) ,然后,计算出各个点的代价,选择代价最小的拓展。可以拓展拓展过的结点,注意要全部走完才能判断出出口。 启发式搜索技术(有序搜索算法) 有序搜索算法:估价函数值小的节点优先,有解的结束条件:具有最小估价函数值的节点是目标节点例子!思路:按照操作符顺序,从第一个开始,拓展第一层,拓展的结点按照从左到右的顺序存放(先-后) ,然后,计算出各个点的估计函数值,选择值最小的拓展。同样注意已经拓展过的结点不拓展。差别:选取待扩展节点的规则不同,并可以 OPEN 表的不同数据结构来体现算法有解的终止条件不同3、 问题归约法、与或树搜索技术 问题归约法表示问题的关键:原始问题描述
7、、本原问题描述、操作符 操作符:将问题转换或分解为子问题的手段 本原问题:一组可以直接得出答案的简单问题 问题归约法的求解过程:用与或图来表示 判断节点是否可解的方法: 终叶节点是可解节点 无后继节点的非终叶节点是不可解节点 用倒推的方法来逐步判断其他节点是否可解 与或图有解的条件是:起始节点(根节点)可解(通过倒推来判断) 与或图的解图:由最少可解节点所构成的子图,这些可解节点能够使问题的起始节点可解 与或树:与或图的特例,除了根节点外,任何一个节点只有一个父节点 与或树的搜索技术: 宽度优先:先扩展出来的节点优先(OPEN 表是队列)例子!思路:到可解结点后倒退回去! 深度优先:后扩展出来
8、的节点优先(OPEN 表是堆栈) ,且有深度限制。注意与宽度的操作符的顺序不一样!这里讲后拓展的放在左边。 图、与或树的宽度、深度优先搜索算法之间的差别: 图搜索技术是找到目标节点或无法扩展而结束算法 与或树搜索技术是找到终叶节点后通过倒推来判断起始节点是否可解而结束算法4、 博弈问题的表达、博弈树的搜索技术 双人博弈问题的特殊之处: 棋局:相当于状态空间法中的状态 走棋:相当于问题归约法的节点扩展(生成或节点、与节点) 博弈树是一棵特殊的与或树,其节点对应棋局(相当于状态) ,与节点、或节点隔层交替出现 博弈树搜索的极大极小过程分成: 宽度优先扩展节点(深度必为偶数) ,并计算最底层端节点的静态估计函数值