人工智能简略复习大纲.pptx
- 文档编号:15120111
- 上传时间:2023-07-01
- 格式:PPTX
- 页数:58
- 大小:4.37MB
人工智能简略复习大纲.pptx
《人工智能简略复习大纲.pptx》由会员分享,可在线阅读,更多相关《人工智能简略复习大纲.pptx(58页珍藏版)》请在冰点文库上搜索。
人工智能-复习大纲,马少平,朱小燕编著,课程简介,通过人工智能课程的学习,了解人工智能的发展概况、人工智能与人类智能之间的联系、人工智能的应用领域、机器学习、神经计算、遗传算法、专家系统等基本概念,掌握知识表示方式和推理、搜索推理、消解原理等人工智能原理的基本理论、方法及其应用技术,注重培养综合运用人工智能原理的知识解决问题的能力。
课程重点章节介绍,本教材共分7章,其中第1.21.4,第2章,3.23.4,4.14.4,6.16.6,7.4为重点章节。
本课程重点和难点内容简介,第0章人工智能的定义,人工智能三种主要学派及其主要观点,人工智能的应用领域,人工智能的定义,定义1智能思考机器能够像人一样进行一些与心智能力相关的思维活动。
定义2智能行动机器能够像人一样执行某些需要智能才能完成的功能。
目前人工智能的主要学派,符号主义认为人工智能源于数理逻辑。
连接主义认为人工智能源于仿生学,特别是人脑模型的研究。
行为主义认为人工智能源于控制论。
第1章搜索问题,图搜索的一般技术回溯策略;无信息图搜索技术,包括深度优先、宽度优先搜索;启发式图搜索技术,包括爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索、A*算法等的计算。
图搜索的一般过程,开始,把S放入OPEN表,OPEN表为空表?
把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗?
把n的后继节点放入OPEN表的末端,提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,是,是,否,否,图搜索技术的分类,按照在搜索过程中,是否使用了中间结果给出的提示信息,可将搜索策略分为盲目搜索(未使用启发性信息),和启发式搜索(使用了启发信息)两大类。
盲目搜索,搜索过程无须对OPEN表进行重排,如:
宽度优先搜索、深度优先搜索。
深度优先搜索,深度优先搜索优先扩展新产生的节点,如示意图。
宽度优先搜索,宽度优先搜索逐层进行,如示意图。
宽度优先搜索与深度优先搜索的主要区别,每次新生成节点时,宽度优先搜索总是将其插入OPEN表的末尾,而深度优先搜索总是将其插入到OPEN表的前头。
宽度优先搜索与深度优先搜索的其他区别:
只要问题有解,宽度优先搜索总是能找到,并且找到的总是搜索路径最短的解;而深度优先搜索却因为可能陷入一条“花园小径”,不一定能够找到解,并且找到的解也不一定是搜索路径最短的解。
启发式图搜索,搜索过程需要对OPEN表重排,如:
爬山法、分支界限法、动态规划法(均一代价法)、最佳优先搜索法、A*算法等。
爬山法,爬山法是一种局部搜索方法,模仿瞎子爬山的过程:
从立足处用明杖向前一试,觉得高些,就向前一步,如果前面不高,向左一试,高就向左一步,不高再试后面,高就退一步,不高再试右面,高就向右走一步,四面都不高,就原地不动.总之,高了就走一步,就这样一步一步地走,就走上了山顶。
这个向各方向的测试“步”,就是“爬山法”的估价函数h(n)。
登山法算法步骤:
设定初始节点n;如果n是目标,则成功退出;扩展n,得到其子节点集合;从该集合中选取h(n)为最小的节点n;将n设为n,返回第步。
分支界限法,分支界限法则以宽度优先或以最小耗费优先的方式,搜索满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。
缺点:
要存储很多分支结点的界限和对应的耗费矩阵,花费很多内存空间。
具有动态规划原理的分支界限法,具有动态规划原理的分支界限法,根据分支界限法得出的各种可能的局部解,根据最小耗散值原则,舍弃那些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一步都是最优解来保证全局是最优解。
这种方法,也可称为均一代价法或等代价法。
耗散值的概念及应用,搜索图中,在任意两节点弧线间移动付出的代价,叫弧线耗散值。
而一条路径的耗散值等于,连接这条路径各节点间所有弧线耗散值的总和。
分支界限法、动态规划法(均一代价法、等代价搜索法)中,均采用路径耗散值作为评价函数,即每次扩展优先选择具有最小路径耗散值的节点进行,记做f(n)=g*(n)。
最佳优先搜索算法,是“爬山法”的推广,但它是对OPEN表中所有节点的h(n)进行比较,按从小到大的顺序重排OPEN表,因此是一种全局寻优法。
其算法效率类似于深度优先搜索算法,但使用了当前节点与目标的估测距离h(n)函数,来确定下一步待扩展的节点,因此是一种启发式搜索方法。
A算法,最佳优先算法有时无法得到最优解,因为它的估价函数f的选取时,忽略了从初始节点到目前节点的代价值。
所以,可考虑每个节点n的估价函数f(n)分为两个分量:
从起始节点到节点n的代价g(n)以及从节点n到达目标节点代价的估算值h(n)。
f(n)=g(n)+h(n),f(n)节点n的估价函数;g(n)从初始节点S到n节点的实际代价;h(n)从n到目标节点Sg最佳路径的估计代价。
这里h(n)体现了搜索的启发信息,因为g(n)是已知的。
如果说详细点,g(n)代表了搜索的宽度优先趋势。
但是当h(n)g(n)时,可以省略g(n),而提高效率。
A算法的引入:
g(n)的计算方法:
g(n)就是在搜索树中从S到n这段路径的代价,这一代价可以由从n到S寻找指针时,把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。
h(n)的计算方法:
h(n)依赖于有关问题的领域的启发信息。
这种信息与当前节点到目标的差距有关,h(n)叫做启发函数。
A*算法的定义:
在图搜索的过程中,如果重排OPEN表是依据f*(n)=g*(n)+h*(n)进行的,则称该过程为A*算法。
其中,g*(n)实际代价函数g(n)的最优值,即g*(n)g(n)。
对右图所示的状态空间图进行:
1)深度优先搜索;2)宽度优先搜索;3)均一(等)代价搜索;4)最佳优先搜索;5)A*搜索。
其中A为起始节点,E为目标节点,各节点的启发值表示在括号内。
F,G,H,E,C,A,D,B,4,2,3,4,8,2,4,3,3,8,5,(15),(14),(10),
(2),(11),(9),(5),(0),1)深度优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,搜索出的路径为:
ABCDE,5,OPEN:
B,HCLOSED:
A,OPEN:
C,HCLOSED:
A,B,OPEN:
D,G,HCLOSED:
A,B,C,OPEN:
E,F,G,HCLOSED:
A,B,C,D,OPEN:
F,G,HCLOSED:
A,B,C,D,2)宽度优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,5,6,7,搜索到的路径为:
ABCDE,8,OPEN:
B,HCLOSED:
A,OPEN:
H,CCLOSED:
A,B,OPEN:
C,GCLOSED:
A,B,H,OPEN:
G,DCLOSED:
A,B,H,C,OPEN:
D,FCLOSED:
A,B,H,C,G,OPEN:
F,ECLOSED:
A,B,H,C,G,D,OPEN:
ECLOSED:
A,B,H,C,G,D,F,OPEN:
CLOSED:
A,B,H,C,G,D,F,3)均一(等)代价搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,5,6,7,搜索出的路径为:
AHGFDE,整条路径的代价和为15。
8,OPEN:
B(3),H(4)CLOSED:
A(0),OPEN:
H(4),C(7)CLOSED:
A(0),B(3),OPEN:
G(6),C(7)CLOSED:
A(0),B(3),H(4),OPEN:
C(7),F(10),D(14)CLOSED:
A(0),B(3),H(4),G(6),OPEN:
F(10),D(14)CLOSED:
A(0),B(3),H(4),G(6),C(7),OPEN:
D(1413)CLOSED:
A(0),B(3),H(4),G(6),C(7),F(10),OPEN:
E(15)CLOSED:
A(0),B(3),H(4),G(6),C(7),F(10),D(1413),OPEN:
CLOSED:
A(0),B(3),H(4),G(6),C(7),F(10),D(13),4)最佳优先搜索算法,F,G,H,E,A,B,1,2,3,4,C,D,搜索出的路径为:
AHGDE,整条路径的代价和为16。
OPEN:
H(11),B(14)CLOSED:
A(15),OPEN:
G(9),B(14)CLOSED:
A(15),H(11),OPEN:
D
(2),F(5),C(10),B(14)CLOSED:
A(15),H(11),G(9),OPEN:
E(0),F(5),C(10),B(14)CLOSED:
A(15),H(11),G(9),D
(2),5,OPEN:
F(5),C(10),B(14)CLOSED:
A(15),H(11),G(9),D
(2),5)A*算法,F,G,H,E,A,B,1,2,3,4,C,D,5,搜索出的路径为:
AHGDE,整条路径的代价和为15。
6,OPEN:
H(15),B(17)CLOSED:
A(15),OPEN:
G(15),B(17)CLOSED:
A(15),H(15),OPEN:
F(15),D(16),B(17),C(19)CLOSED:
A(15),H(15),G(15),OPEN:
D(1615),B(17),C(19)CLOSED:
A(15),H(15),G(15),F(15),OPEN:
E(15),B(17),C(19)CLOSED:
A(15),H(15),G(15),F(15),D(1615),OPEN:
B(17),C(19)CLOSED:
A(15),H(15),G(15),F(15),D(1615),第2章与或图搜索问题,与或图的定义,k-连接符的表示方法,与或图解图的耗散值计算方法,能解和不能解节点的定义,与或图的启发式搜索算法AO*的应用等;博弈树的极大极小搜索过程,、参数的定义,-剪枝法的定义及应用。
与或图表示的问题,在用某一中方法求解问题时,可能需要求解几个子问题,这些子问题必须全部求解,才能用该方法求解原始问题。
这些“子”问题间的关系,就是“与”的关系,此类问题可用与或图来表示。
k-连接符的定义,解图耗散值的计算,k(n,N)=Cn+k(n1,N)+k(ni,N)其中:
N为终节点集;Cn为连接符的耗散值,在单连接符为单位耗散的情况下,k-连接符的耗散值为k;n1,ni为节点n的子节点,k(ni,N)表示子节点ni的耗散值,可用启发值h(ni)代替。
能解节点,终节点是能解节点若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解。
若非终节点有“与”子节点时,当且仅当其子节点均能解时,该非终节点才能解。
不能解节点,没有后裔的非终节点是不能解节点。
若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解。
若非终节点有“与”子节点时,当至少有一个子节点不能解时,该非终节点才不能解。
AO*算法,评估函数采用解图的耗散值k(n,N),即每次扩展选择解图耗散值最小的节点进行。
搜索的两个过程:
图生成过程,即扩展节点从最优的局部图中选择一个节点扩展计算耗散值的过程对当前的局部图重新计算耗散值,AO*算法举例,其中:
h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设:
k连接符的耗散值为k,初始节点,n0,n1
(2),n4
(1),n5
(1),红色:
4黄色:
3,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色:
4黄色:
6,n1,n2(4),n3(4),5,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色:
5黄色:
6,2,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色:
5黄色:
6,2,1,极小极大搜索过程,模拟人类下棋的方法,尤其是初学者,走一步,看看对方的反应,思考应对的方法再走一步,。
所谓高手,就是能对几个,甚至几十个棋步后,有较准确的局面预测。
对目前的局部解图进行评价,选择评价值最好的子节点(对Max节点),或评价值最差的子节点(对Min节点),作为下一步的走法,即选择棋步的极大极小法。
极大极小法的评估函数,评估函数:
以我方为标准设定。
例如,在一字棋的情况下,Max方赢的评估值设为+,Max方输的评估值设为-,平局的评估值设为0,此外根据与Max方赢局相关的棋子数目,可以设为1,2,3,。
极小极大过程,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极大,极小,a,b,-剪枝法的引入,在极小极大法中,必须求出所有终端节点的评估值,当预先考虑的棋步比较多时,计算量会大大增加。
为了提高搜索的效率,引入了通过对评估值的上下限进行估计,从而减少需进行评估的节点范围的-剪枝法。
MAX节点的评估下限值,作为正方出现的MAX节点,取它的第一个MIN子节点的评估值。
当有其它子节点的评估值超过,则该MAX节点会取新值作为自己的评估值;如果没有,则该MAX节点的评估值就是。
总之,该MAX节点的评估值不会低于,这个就称为该MAX节点的评估下限值。
MIN节点的评估上限值,作为反方出现的MIN节点,取它的第一个MAX子节点的评估值。
当有其它子节点的评估值低于,则该MIN节点会取新值作为自己的评估值;如果没有,则该MIN节点的评估值就是。
总之,该MIN节点的评估值不会高过,这个就称为该MIN节点的评估上限值。
-剪枝,极大节点的下界为。
极小节点的上界为。
剪枝的条件:
后辈节点的值祖先节点的值时,剪枝后辈节点的值祖先节点的值时,剪枝简记为:
极小极大,剪枝极大极小,剪枝,8,6,-3,1,4,5,3,-3,5,0,-剪枝(续),3,-3,0,2,2,-3,0,-2,3,0,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-3,1,6,6,1,a,b,c,d,e,f,g,h,i,j,k,m,n,第3章谓词逻辑与归结原理,谓词基本概念,包括一阶谓词公式中的各参数、辖域、约束等概念的含义;谓词公式化skolem子句集,置换与合一的实现,消解反演的证明及计算;H域及原子集的定义,Herbrand封闭语义树的构造及Herbrand定理。
第4章知识表示,三种主要知识表示方法(产生式表示、语义网络和框架表示方法)。
第5章不确定性推理方法,知识的不确定性表示方法的定义,包括证据、规则、推理结论的不确定性等的含义;不确定性推理方法的分类。
第6章机器学习,机器学习的基本概念,包括其定义、任务,研究意义以及分类方法等;基于实例的归纳学习方法,包括Winston拱,变形空间法等;解释学习的基本步骤及与归纳学习的比较;决策树学习的应用及计算;神经网络的数学模型及分类,单层感知机的学习算法,BP算法的概念及推导等。
第7章高级搜索,遗传算法的基本定义、步骤,选择、交配及变异操作等操作的具体实现,二进制的编码问题。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 简略 复习 大纲
![提示](https://static.bingdoc.com/images/bang_tan.gif)