2022年最新人工智能期末复习.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年最新人工智能期末复习.pdf》由会员分享,可在线阅读,更多相关《2022年最新人工智能期末复习.pdf(18页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精品文档精品文档1.人工智能(学科):Artificial Intelligence 是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期目标在于研究用机器来模仿和执行人脑的某些智能功能,并开发相关的理论和技术。在人工智能中,重点关注两个方面的内容:问题的表示(知识的表示) :即要找到问题的一种合适的表示方法在人工智能中,我们要涉及到:状态空间法、问题归约法、谓词逻辑法、样本向量法问题的求解:从问题表示方法出发,找到一个合理的办法来求解在人工智能中,常有的方法有:搜索法、推理法、计算方法2. 状态空间法 :从某一个初始状态开始,每次施加一个操作符,递增地建立操作符序列,直到达到目标状
2、态为止人工智能中,一种最基本的求解方法就是试探搜索法,即,通过在某个可能的解空间(例如,所有可能的走法) 中寻找一个解。 这种基于解空间的问题表示和求解方法就是状态空间法 ,其基础是状态和算符(算子)状态空间法表示问题的关键:状态与操作符状态: 为了描述某一类不同事物间的差别而引入的一组最少变量的有序集合算符(操作符):使问题从一个状态变换到另一状态的手段用状态空间法表达出原始问题后,欲解问题变成为: 寻找从初始状态到目标状态的某一个操作符序列状态空间法的求解过程:用有向图来表示图是由节点(不一定是有限个的节点)的集合构成的注意:在图论中,图的定义中还包括边的集合无向图:一对节点可能互为后裔,
3、边用线段来表示有向图:一对节点用弧线连接起来,并且从一个节点指向另一个节点对应关系:精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页,共 18 页 - - - - - - - - - - 精品文档精品文档当用有向图来表示状态空间法时,对应关系:图中的一个节点对应于某一个状态图中的一个有向弧对应于某一个算符状态空间法的解: 从初始状态到目标状态的操作符序列图中的解: 从起始节点到目标节点的一条路径问题: 寻找从初始状态到目标状态的某个操作符序列转化为寻找图中初始节点(对应初始状态)到目标节点(对应于目
4、标状态)的一条路径求解思路: 边扩展节点边找解的搜索思想问题的状态空间:一个表示问题全部可能状态及其关系的图,它包含了三个集合:所有可能的问题初始状态集合S 操作符集合 F 目标状态集合 G 状态空间记作三元状态(S, F, G )3. 代价 g(n) :从起始节点S 到某一节点n 的路径的实际代价估值函数f (n) :从起始节点 S、通过节点 n、到达目标节点 G的最小代价的一个估计值f ( n ) = g ( n ) + h ( n ) 利用图论的技术,我们要解决两个问题:第一、 找出初始节点到目标节点的一条路径。 对应于寻找初始状态到目标状态的操作符序列(能够解决问题)第二、找出初始节点
5、到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列(更好地解决问题)4. 图的搜索技术分:盲目搜索技术(宽度、深度、代价优先搜索技术)启发式搜索技术(有序搜索算法)差别: 选取待扩展节点的规则不同,并且可以OPEN表的不同数据结构来体现算法有解的终止条件不同图搜索中的两个重要记号(符号) :OPEN 表:存放待扩展的节点CLOSED 表:存放已扩展的节点注意:在与或树搜索中也要用到这两张表精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页,共 18 页
6、 - - - - - - - - - - 精品文档精品文档盲目搜索技术盲目搜索是指无问题先验信息的搜索技术特点: OPEN表中节点的排列是人为规定的;一般只适合于求解比较简单的一些问题宽度优先: 先扩展出来的节点优先( OPEN 为队列) ,后继节点有目标节点结束OPEN 表是存放待扩展的节点,从数据结构上来说,它是一个先进先出的队列CLOSED 表是存放已被扩展过的节点(包括有后继节点的非端节点和无后继节点的端节点),可以看成只进不出的队列深度优先: 后者扩展出来的节点优先(OPEN 为堆栈),且有深度限制,后继节点有目标节点结束OPEN表是一个堆栈,后进先出代价优先(等代价) :到起始节点
7、代价小的节点优先(OPEN 为线性表),具有最小代价的节点是目标节点时结束三种盲目搜索技术的比较主要差别:在于挑选要扩展节点的规则不同宽度优先搜索技术:先扩展出来的节点随后先扩展,OPEN表是队列深度优先搜索技术:后扩展出来的节点随后先扩展,OPEN表是堆栈等代价搜索技术:选取OPEN表中代价最小的节点先扩展,OPEN表是线性表(以局部代价的递增顺序排列)精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页,共 18 页 - - - - - - - - - - 精品文档精品文档宽度和深度优先搜索的缺点:
8、扩展节点的顺序是人为规定的, 要扩展节点的数目可能非常大,占用大量的计算时间和内存空间,使得搜索效率低等代价搜索技术的缺点选取已经搜索到的代价最小的节点来扩展,但是没有考虑目标状态, 不知道离目标状态还有多远,还需要付出多大的代价启发式搜索技术有序算法: 估价函数值小的节点优先有解的结束条件:具有最小估价函数值的节点是目标节点启发式搜索方法:利用启发信息的搜索方法有序搜索:在搜索过程总是选择“最有希望”的节点作为下一个被扩展节点的搜索技术在搜索过程中, OPEN表中节点按照其估价函数值以递增顺序排列,选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点,这种搜索方法称为有序搜索精品资
9、料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页,共 18 页 - - - - - - - - - - 精品文档精品文档估价函数:用来估算节点“希望 ”程度的函数估价函数的基本特性:一般情况下,估计函数值越大,希望程度就越低根据搜索过程、问题的启发信息来定义的,对搜索效率会产生较大的影响节点 n 的估价函数f ( n ) 定义为从初始节点、经过n 、到达目标节点的路径的最小代价的估计值,即f ( n ) = g ( n ) + h ( n ) g ( n ) 是从初始节点到达当前节点n 的实际代价h (
10、n ) 是从节点n 到目标节点的最佳路径的估计代价h ( n ) 体现出搜索过程中采用的启发式信息(背景知识),称之为启发函数g ( n ) 所占的比重越大,越趋向于宽度优先或等代价搜索;反之,h ( n ) 的比重越大,表示启发性能就越强例:八数码问题的估价函数f ( n )= g ( n ) + h ( n ) g ( n ) 定义为搜索树中n 的深度h ( n ) 可以定义成不同形式 (节点 n 的状态与目标状态之间数字不在位的个数(错放棋子的个数,不算空格)精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - -
11、 -第 5 页,共 18 页 - - - - - - - - - - 精品文档精品文档5.问题归约法、与或树搜索技术问题归约法:从已知问题的描述出发, 通过一系列变换或分解将问题最终变为一个子问题集合,这些子问题的解可以直接得到,从而解决初始问题问题归约法表示问题的关键:原始问题描述、本原问题描述、操作符操作符: 将问题转换或分解为子问题的手段本原问题: 一组可以直接得出答案的简单问题问题归约法可以用一个三元组(S, O, P )来表示,其中:S :原始问题,即要解决的问题P:本原问题集,其中的每一个问题是不用证明的或自然成立的,例如公理、已知事实等O:操作算子集,用于将问题化为子问题问题归约
12、法的基本思路是:应用一系列算符将原始问题的描述变换或分解成为子问题的描述问题的描述可以采用各种数据结构,如表、树、矢量、数组等与或图的特例:所有节点都是或节点,这时就是一般的图,即状态空间法用到的图除了起始节点外,所有节点只有一个父节点,此时称为与或树,问题归约法的求解过程:用与或图来表示“或节点”有解的条件是:只要有一个后继节点可解“或节点”无解的条件是:所有后继节点无解“与节点”有解的条件是:所有后继节点有解“与节点”无解的条件是:只要有一个后继节点无解判断节点是否可解的方法:终叶节点是可解节点无后继节点的非终叶节点是不可解节点精品资料 - - - 欢迎下载 - - - - - - - -
13、 - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页,共 18 页 - - - - - - - - - - 精品文档精品文档用倒推的方法来逐步判断其他节点是否可解与或图有解的条件是: 起始节点(根节点)可解(通过倒推来判断)与或图的解图: 由最少可解节点所构成的子图,这些可解节点能够使问题的起始节点可解与或树: 与或图的特例,除了根节点外,任何一个节点只有一个父节点与或图:除了起始节点,每一个节点允许有多个父节点与或树的搜索技术:宽度优先:先扩展出来的节点优先(OPEN表是队列)深度优先:后扩展出来的节点优先(OPEN表是堆栈),且有深度限制图、与或树的宽度、深度
14、优先搜索算法之间的差别:图搜索技术是找到目标节点或无法扩展而结束算法与或树搜索技术是找到终叶节点后通过倒推来判断起始节点是否可解而结束算法6.博弈问题的表达、博弈树的搜索技术双人博弈问题的特殊之处:棋局:相当于状态空间法中的状态走棋:相当于问题归约法的节点扩展(生成或节点(自己)、与节点(别人)博弈树 是一棵特殊的与或树,其节点对应棋局(相当于状态),与节点、或节点隔层交替出现博弈的特点: 双方的智能活动, 任何一方都不能单独控制博弈过程,而是由双方轮流实施其控制对策的过程博弈问题(求解过程)的表示:用博弈树来表示,它是一种特殊的与或树。节点代表博弈的格局(即棋局),相当于状态空间中的状态,反
15、映了博弈的信息,并且与节点、或节点隔层交替出现博弈树搜索的极大极小过程分成:宽度优先扩展节点(深度必为偶数) ,并计算最底层端节点的静态估计函数值用倒推的方法 (自己下的棋取大者, 对手下的棋取小者) 计算出其余各层节点的静态估计函数值,最后决定走哪一步棋7.谓词逻辑与推理数理逻辑(符号逻辑) 是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑数理逻辑的主要分支:精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页,共 18 页 - - - -
16、 - - - - - - 精品文档精品文档逻辑演算 (包括命题演算和谓词演算 ) 模型论证明论递归论公理化集合论数理逻辑和计算机科学有许多重合之处,两者都属于模拟人类认知机理的科学谓词逻辑是数理逻辑的基本形式,是基于谓词分析的一种形式化(数学)语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明(限于本课程)命题逻辑是研究命题及命题之间关系的符号逻辑系统。在命题逻辑中,表示单一意义的命题,称之为原子命题。原子命题通过“联结词”构成 复合命题。五个联结词: “” 表示“非”复合命题 P为真,当且仅当 P为假。 “” 表示 “合取”复合命题“ PQ”为真,当且仅当P和 Q都为真。 “”
17、 表示 “析取”复合命题“ PQ”为真,当且仅当P、Q两者之一为真。 “ ” 表示 “ 蕴含”复合命题“ PQ ” 为假,当且仅当P为真且 Q 为假。 “ ” 表示 “ 等价”复合命题“ PQ ” 为真,当且仅当P、Q 同时为真、或者同时为假。命题变元:用符号 P、Q等表示的不具有固定、 具体含义的命题。 它可以表示具有 “真” 、 “假”含义的各种命题。命题变元可以利用联结词构成所谓的合适公式。合适公式的定义若 P为原子命题,则 P为合适公式,称为原子公式。若 P是合适公式,则 P也是一个合适公式。若 P和 Q 是合适公式,则 PQ、 PQ 、PQ 、PQ都是合适公式。经过有限次使用规则1、
18、2、3,得到的由原子公式、联结词和园括号所组成的符号串,也是合适公式。对于合适公式,规定下列运算优先级:精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页,共 18 页 - - - - - - - - - - 精品文档精品文档逻辑联结词的运算优先次序为:、 同级联结词按出现顺序优先运算谓词演算1、语法与语义谓词逻辑的基本组成部分谓词变量函数常量园括号、方括号、花括号和逗号例“机器人( Robot)在第一个房间( Room1)内” ,可以表示为:INROOM (ROBOT ,r1)其中INROOM是谓词
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022 最新 人工智能 期末 复习
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内