人工智能技术导论总复习33528.pptx

《人工智能技术导论总复习33528.pptx》由会员分享，可在线阅读，更多相关《人工智能技术导论总复习33528.pptx（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1章章 人工智能概述人工智能概述什么是人工智能？人工智能的研究目什么是人工智能？人工智能的研究目标和意义？标和意义？人工智能的研究学派、人工智能的研究学派、途径与方法途径与方法人工智能的研究目标人工智能的研究目标人工智能的分支领域（基于应用领域）人工智能的分支领域（基于应用领域）人工智能基本技术人工智能基本技术第第3章章 图搜索技术图搜索技术状态图知识表示状态图知识表示状态图搜索状态图搜索穷举式搜索穷举式搜索启发式搜索启发式搜索加权状态图搜索加权状态图搜索与或图知识表示与或图知识表示与或图搜索与或图搜索启发式与或树搜索启发式与或树搜索博弈树搜索博弈树搜索极小极大分析法极小极大分析法-剪枝剪

2、枝状态图知识表示状态图知识表示状态空间（状态空间（State SpaceState Space）问题的状态空间是一个表示该问题全部的问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。可能状态及相互关系的图。一般用赋值有向图，包含一般用赋值有向图，包含S S：问题的可能有的初始状态的集合；：问题的可能有的初始状态的集合；F F：操作的集合；：操作的集合；G G：目标状态的集合。：目标状态的集合。状态空间常记为三元序列状态空间常记为三元序列SG状态空间中问题求解（状态空间中问题求解（1）在状态空间图中，问题求解过程转化为在图中寻找在状态空间图中，问题求解过程转化为在图中寻找从初始状态从初

3、始状态S0出发到达目标状态出发到达目标状态Sg的路径问题，也的路径问题，也就是寻找操作序列的问题。就是寻找操作序列的问题。状态空间的解为三元组状态空间的解为三元组S0：某个初始状态：某个初始状态Sg：某个目标状态：某个目标状态O：把：把Qs变换成变换成Qg的有限的操作序列的有限的操作序列O1,O2,On状态转换图状态转换图S1S3S2O1O2O3O4S0SgOn状态空间中问题求解（状态空间中问题求解（2）状态图搜索：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。状态图的解：搜索成功后，从目标结点反向沿搜索树按所作标记追溯一直到初始结点，所得到一条从初始结点到目标结点的路径就是

4、问题的一个解。状态图搜索（状态图搜索（1）穷举式搜索穷举式搜索广度优先广度优先深度优先深度优先有界深度优先有界深度优先启发式搜索启发式搜索全局择优（广度优先搜索全局择优（广度优先搜索+h(x)）局部择优（深度优先搜索局部择优（深度优先搜索+h(x)）状态图搜索（状态图搜索（2）加权状态图搜索加权状态图搜索分支界限（广度优先搜索分支界限（广度优先搜索+g(x)）最近择优最近择优/瞎子爬山（深度优先搜索瞎子爬山（深度优先搜索+g(x)）A算法（一般树式搜索算法算法（一般树式搜索算法+f(x)）A*算法（算法（h(x)=h*(x)）或图（状态图或图（状态图）知识表示知识表示搜索搜索穷举式搜索穷举式搜

5、索启发式搜索启发式搜索加权状态图搜索加权状态图搜索广度优先广度优先深度优先深度优先全局择优全局择优(最好优先最好优先)局部择优局部择优(瞎子爬山瞎子爬山)分支界限分支界限(最小代价优先最小代价优先)最近优先最近优先(瞎子爬山瞎子爬山)A A算法和算法和A A*算法算法与或图知识表示与或图知识表示一个复杂的问题一个复杂的问题P P常常可以归约为与之等价的一组子问题，当常常可以归约为与之等价的一组子问题，当这些问题这些问题全部可解全部可解时，问题可解；任何一个子问题无解时，都时，问题可解；任何一个子问题无解时，都将导致原问题将导致原问题P P无解。即一个问题与一组子问题的无解。即一个问题与一组子问

6、题的与等价与等价。一个复杂的问题一个复杂的问题P P常常可以分别归约为与之等价的一组子问题，常常可以分别归约为与之等价的一组子问题，其中其中任何一个子问题可解任何一个子问题可解时，问题可解；全部子问题无解时，时，问题可解；全部子问题无解时，原问题原问题P P无解。即一个问题与一组子问题的无解。即一个问题与一组子问题的或等价或等价。与或图知识表示是一个三元组（与或图知识表示是一个三元组（Q Q0 0,F,Q,F,Qn n）Q Q0 0：表示初始问题：表示初始问题F F：表示问题变换规则集：表示问题变换规则集Q Qn n：表示本原问题集：表示本原问题集与或图知识表示（1）与或图的几个概念与或图的几

7、个概念直接可解的问题称为直接可解的问题称为本原问题本原问题。本原问题对应的节点称为本原问题对应的节点称为终止节点终止节点。无子节点的节点称为无子节点的节点称为端节点端节点。子节点为与关系，则该节点为子节点为与关系，则该节点为与节点与节点。子节点为或关系，则该节点为子节点为或关系，则该节点为或节点或节点。与或图一般表示问题的变换过程，就是从原问题出与或图一般表示问题的变换过程，就是从原问题出发，运用某些规则不断的进行问题的分解（得到与发，运用某些规则不断的进行问题的分解（得到与分支）和变换（得到或分支），而得到一个与或图，分支）和变换（得到或分支），而得到一个与或图，与或图的节点一般代表问题，整

8、个图就表示问题空与或图的节点一般代表问题，整个图就表示问题空间。间。与或图搜索（与或图搜索（1）与或图与或图知识表示知识表示搜索搜索盲目式搜索盲目式搜索启发式搜索启发式搜索博弈树搜索博弈树搜索穷举式搜索穷举式搜索盲目碰撞搜索盲目碰撞搜索广度优先广度优先深度优先深度优先与或图搜索（与或图搜索（2）与或树搜索与或树搜索可解性判定可解性判定广度优先、有界深度优先广度优先、有界深度优先与与或或图图搜搜索索：与与或或图图中中搜搜索索不不像像在在或或图图（状状态态图图）中中只只是是寻寻找找目目标标节节点点，而而是是边边扩扩展展节节点点边边进进行行逻逻辑辑判判断断，以以确确定定初初始始结结点点是是否否可可解

9、解。一一旦旦确确定定初初始始节节点点的的可可解解性性，搜搜索索停停止止。根根据据返返回回指指针针可可从从搜搜索索树树中得到一个解图（树）。中得到一个解图（树）。与或图的解与或图的解：是由：是由可解节点可解节点形成的一个子图（树），形成的一个子图（树），这个子图（树）的根为初始节点，叶为终止节点。这个子图（树）的根为初始节点，叶为终止节点。与或图搜索（与或图搜索（3）有序搜索有序搜索解树（树根）代价的计算方法解树（树根）代价的计算方法和代价法和代价法最大代价法最大代价法有序搜索过程有序搜索过程启发式与或树搜索解树代价的计算方法令：g(x)表示节点x的代价，c(x,yi)表示节点x到其子节点yi的

10、代价(即边xyi的代价)，yi是x的子节点.则 (1)若x是终止节点，g(x)0；(2)若x是或节点 (3)若x是与节点，则有两种计算公式。和代价法 最大代价法 (4)对非终止的端节点x，g(x)x xy y1 1y y2 2c(x,yc(x,y1 1)c(x,yc(x,y2 2)x xy y1 1y y2 2c(x,yc(x,y1 1)c(x,yc(x,y2 2)启发式与或树搜索启发式与或树搜索a1a2a3a4a5a6b1b2b4b3b5S4456245732443例：如下图所示的与或树，例：如下图所示的与或树，a4,a5,a6,b3,b5是终止结点，求其解树是终止结点，求其解树启发式与或树

11、搜索启发式与或树搜索左左解解树树节点节点a6a5a4a3a2a1S和代价和代价000462125最大代价最大代价000441014右右解解树树节点节点b5b4b3b2b1S和代价和代价030151923最大代价最大代价030101418补充示例：如下图所示的与或树，其解树和节点相应代价如下补充示例：如下图所示的与或树，其解树和节点相应代价如下博弈树搜索博弈树搜索极小极大分析法极小极大分析法 剪枝技术剪枝技术极小极大分析法（极小极大分析法（1）极小极大分析法的基本思想极小极大分析法的基本思想设博弈的双方中一方为设博弈的双方中一方为A，另一方为，另一方为B。然后为。然后为其中的一方其中的一方(始终

12、站在始终站在A的立场上的立场上)寻找一个最优寻找一个最优行动方案。行动方案。为了找到当前的最优行动方案，需要对各个可能为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较。的方案所产生的后果进行比较。为计算得分，需要根据问题的特性信息定义一个为计算得分，需要根据问题的特性信息定义一个估价函数估价函数f(p)(p是端节点是端节点)，用来估算当前博弈树，用来估算当前博弈树端节点的得分。这时估算出来的得分为静态估值。端节点的得分。这时估算出来的得分为静态估值。极小极大分析法（极小极大分析法（2）当端节点的估值计算出来后，再推算出父当端节点的估值计算出来后，再推算出父节点的得分，推算的

13、方法是：节点的得分，推算的方法是：对对“或或”节点，选其子节点中一个最大的得分节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；择的方案中选一个对自己最有利的方案；对对“与与”节点，选其子节点中一个最小的得分节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。况。这样计算出的父节点的得分称为倒推值。如果一个行动方案能获得较大的倒推值，如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。则

14、它就是当前最好的行动方案。极小极大分析示例倒推值的计算 2 2-1-12 2-2-23 34 4-5-51 13 32 22 23 34 43 33 32 23 3 剪枝技术剪枝技术对对于于一一个个与与节节点点MINMIN,若若能能估估计计出出其其倒倒推推值值的的上上确确界界,并并且且这这个个值值不不大大于于MINMIN的的父父节节点点(一一定定是是或或节节点点)的的估估计计倒倒推推值值的的下下确确界界,即即,则则就就不不必必再再扩扩展展该该MINMIN节节点点的的其其余余子子节节点点了了(因因为为这这些些节节点点的的估估值值对对MINMIN父父节节点点的的倒倒推推值值已已无无任任何何影影响了

15、响了)。这一过程称为。这一过程称为剪枝剪枝。对对于于一一个个或或节节点点MAXMAX,若若能能估估计计出出其其倒倒推推值值的的下下确确界界,并并且且这这个个值值不不小小于于MAXMAX的的父父节节点点(一一定定是是与与节节点点)的的估估计计倒倒推推值值的的上上确确界界,即即,则则就就不不必必再再扩扩展展该该MAXMAX节节点点的的其其余余子子节节点点了了(因因为为这这些些节节点点的的估估值值对对MAXMAX父父节节点点的的倒倒推推值值已已无无任任何何影影响了响了)。这一过程称为。这一过程称为剪枝剪枝。剪枝技术剪枝技术(1)(1)2931 1 1 368 1 203 5 74 2 6 1 8 7

16、1 0 3ABCEHJKPQDLDRTIFGMUNVS2 2221 11 12 22 22 22 22 26 6660 0000 05 50 06 60 0第第4章章基于遗传算法的随机优化搜索基于遗传算法的随机优化搜索遗传算法的基本概念遗传算法的基本概念遗传算法和图搜索在优化搜索和问题遗传算法和图搜索在优化搜索和问题求解方面的对比求解方面的对比第第5章基于谓词逻辑的机器推理章基于谓词逻辑的机器推理相关定义及概念相关定义及概念化子句集的过程化子句集的过程命题逻辑的归结原理命题逻辑的归结原理替换与合一替换与合一谓词逻辑中的归结原理谓词逻辑中的归结原理应用归结原理求取问题答案应用归结原理求取问题答案

17、归结策略归结策略化子句集的过程化子句集的过程1、消去蕴含词和等值词。、消去蕴含词和等值词。2、使否定词仅作用于原子公式。、使否定词仅作用于原子公式。3、适当改名使量词间不含同名指导变元。、适当改名使量词间不含同名指导变元。4、消去存在量词。、消去存在量词。5、消去全称量词。、消去全称量词。6、化公式为合取范式。、化公式为合取范式。7、适当改名，使子句间无同名变元。、适当改名，使子句间无同名变元。8、消去合取词，以子句为元素组成一个集合、消去合取词，以子句为元素组成一个集合S。命题逻辑的归结原理命题逻辑的归结原理设设C1，C2是命题逻辑中的两个子句是命题逻辑中的两个子句 C1中有文字中有文字L1

18、，C2中有文字中有文字L2，且，且L1与与L2互补，互补，从从C1、C2中分别删除中分别删除L1、L2，再将剩余部分析取起来，记构成的新子句为再将剩余部分析取起来，记构成的新子句为C1 2，则，则C1 2为为C1、C2的归结式。的归结式。替换与合一替换与合一一个替换（一个替换（Substitution）是形如）是形如 t1/x1,t2/x2,tn/xn的有限集合的有限集合设设是原子公式集是原子公式集S的一个合一，如果的一个合一，如果对对S的任何一个合一的任何一个合一都存在一个替换都存在一个替换，使得，使得 则称则称为为S的最一般合一的最一般合一(Most General Unifier),简称

19、简称MGU。谓词逻辑中的归结原理谓词逻辑中的归结原理C1，C2为无相同变元的子句；为无相同变元的子句；L1，L2为其中的两个文字，为其中的两个文字，L1和和L2有最一般合一有最一般合一；C1，C2的二元归结式（二元消解式）的二元归结式（二元消解式）为：为：C1 L1）（C2 L2）应用归结原理求取问题答案应用归结原理求取问题答案（1 1）先为待求解的问题找一个合适的）先为待求解的问题找一个合适的求证目标谓词求证目标谓词；（2 2）再对目标否定子句增配（）再对目标否定子句增配（以析取形式以析取形式）一个）一个辅助辅助谓词谓词，该谓词的，该谓词的变元变元必须与对应必须与对应目标谓词目标谓词中的中的

20、变元变元完全完全一致一致；（3 3）进行归结；）进行归结；（4 4）当归结是刚好）当归结是刚好只剩下辅助谓词只剩下辅助谓词时，辅助谓词中原时，辅助谓词中原变元位置上的变元位置上的项项就是就是所求所求的结果。的结果。归结策略归结策略删除策略删除策略支持集策略支持集策略线性归结策略线性归结策略输入归结策略输入归结策略单元归结策略单元归结策略祖先过滤型策略祖先过滤型策略第第6章章 产生式系统产生式系统产生式系统的组成产生式系统的组成产生式系统的运行过程产生式系统的运行过程产生式系统有哪几种推理方式？各自产生式系统有哪几种推理方式？各自有什么特点有什么特点.产生式系统的控制策略与常用算法产生式系统的控

21、制策略与常用算法（正向，反向）（正向，反向）第第7章章 知识表示知识表示框架框架语义网络语义网络类和对象类和对象第第8章章 不确定性知识的表示和推理不确定性知识的表示和推理确定性理论确定性理论主观贝叶斯方法主观贝叶斯方法证据理论证据理论贝叶斯网络贝叶斯网络模糊逻辑模糊逻辑第第9章章 机器学习机器学习机器学习的原理机器学习的原理机器学习分类机器学习分类机器学习的方法机器学习的方法符号学习：决策树学习（符号学习：决策树学习（ID3算法）算法）连接学习：权值修正学习（连接学习：权值修正学习（BP算法）算法）第第12章章 专家系统专家系统什么是专家系统？有哪些特征？什么是专家系统？有哪些特征？专家系统的结构？每部分功能是什么专家系统的结构？每部分功能是什么？专家系统的应用与发展？专家系统的应用与发展？考试相关考试相关考试题型考试题型简答题（简答题（25%）应用题（应用题（65%）其他（其他（10%）成绩计算成绩计算卷面成绩卷面成绩*80%+平时成绩平时成绩*20%内容分布内容分布第第1章：章：5%第第3章：章：26%第第4章：章：5%第第5章：章：22%第第6章：章：5%第第7章：章：5%第第8章：章：12%第第9章：章：5%第第12章：章：5%其他：其他：10%