人工智能技术导论总复习

《人工智能技术导论总复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章人工智能概述什么是人工智能？人工智能的研究目标和意义？人工智能的研究学派、途径与方法人工智能的研究目标人工智能的分支领域（基于应用领域）人工智能基本技术第3章图搜索技术状态图知识表示状态图搜索穷举式搜索启发式搜索加权状态图搜索与或图知识表示与或图搜索启发式与或树搜索博弈树搜索极小极大分析法α-β剪枝状态图知识表示状态空间（StateSpace）问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。一般用赋值有向图，包含S：问题的可能有的初始状态的集合；F：操作的集合；G：目标状态的集

2、合。状态空间常记为三元序列状态空间中问题求解（1）在状态空间图中，问题求解过程转化为在图中寻找从初始状态S0出发到达目标状态Sg的路径问题，也就是寻找操作序列的问题。状态空间的解为三元组S0：某个初始状态Sg：某个目标状态O：把Qs变换成Qg的有限的操作序列{O1,O2,…,On}状态转换图S1S3S2…O1O2O3O4S0SgOn状态空间中问题求解（2）状态图搜索：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。状态图的解：搜索成功后，从目标结点

3、反向沿搜索树按所作标记追溯一直到初始结点，所得到一条从初始结点到目标结点的路径就是问题的一个解。状态图搜索（1）穷举式搜索广度优先深度优先有界深度优先启发式搜索全局择优（广度优先搜索+h(x)）局部择优（深度优先搜索+h(x)）状态图搜索（2）加权状态图搜索分支界限（广度优先搜索+g(x)）最近择优/瞎子爬山（深度优先搜索+g(x)）A算法（一般树式搜索算法+f(x)）A*算法（h(x)<=h*(x)）与或图知识表示一个复杂的问题P常常可以归约为与之等价的一组子问题，当这些问题全部可解时，问题可

4、解；任何一个子问题无解时，都将导致原问题P无解。即一个问题与一组子问题的与等价。一个复杂的问题P常常可以分别归约为与之等价的一组子问题，其中任何一个子问题可解时，问题可解；全部子问题无解时，原问题P无解。即一个问题与一组子问题的或等价。与或图知识表示是一个三元组（Q0,F,Qn）Q0：表示初始问题F：表示问题变换规则集Qn：表示本原问题集与或图知识表示（1）与或图的几个概念直接可解的问题称为本原问题。本原问题对应的节点称为终止节点。无子节点的节点称为端节点。子节点为与关系，则该节点为与节点。子节

5、点为或关系，则该节点为或节点。与或图一般表示问题的变换过程，就是从原问题出发，运用某些规则不断的进行问题的分解（得到与分支）和变换（得到或分支），而得到一个与或图，与或图的节点一般代表问题，整个图就表示问题空间。与或图搜索（1）与或图搜索（2）与或树搜索可解性判定广度优先、有界深度优先与或图搜索：与或图中搜索不像在或图（状态图）中只是寻找目标节点，而是边扩展节点边进行逻辑判断，以确定初始结点是否可解。一旦确定初始节点的可解性，搜索停止。根据返回指针可从搜索树中得到一个解图（树）。与或图的解：是由

6、可解节点形成的一个子图（树），这个子图（树）的根为初始节点，叶为终止节点。与或图搜索（3）有序搜索解树（树根）代价的计算方法和代价法最大代价法有序搜索过程启发式与或树搜索解树代价的计算方法令：g(x)表示节点x的代价，c(x,yi)表示节点x到其子节点yi的代价(即边xyi的代价)，yi是x的子节点.则(1)若x是终止节点，g(x)＝0；(2)若x是或节点(3)若x是与节点，则有两种计算公式。①和代价法②最大代价法(4)对非终止的端节点x，g(x)＝∞xy1y2c(x,y1)c(x,y2)xy1

7、y2c(x,y1)c(x,y2)启发式与或树搜索a1a2a3a4a5a6b1b2b4b3b5S4456245732443例：如下图所示的与或树，a4,a5,a6,b3,b5是终止结点，求其解树启发式与或树搜索左解树节点a6a5a4a3a2a1S和代价000462125最大代价000441014右解树节点b5b4b3b2b1S和代价030151923最大代价030101418补充示例：如下图所示的与或树，其解树和节点相应代价如下博弈树搜索极小极大分析法α－ß剪枝技术极小极大分析法（1）极小极大分析

8、法的基本思想设博弈的双方中一方为A，另一方为B。然后为其中的一方(始终站在A的立场上)寻找一个最优行动方案。为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较。为计算得分，需要根据问题的特性信息定义一个估价函数f(p)(p是端节点)，用来估算当前博弈树端节点的得分。这时估算出来的得分为静态估值。极小极大分析法（2）当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最