人工智能原理PrinciplesofArtificialIntelligence.ppt
《人工智能原理PrinciplesofArtificialIntelligence.ppt》由会员分享,可在线阅读,更多相关《人工智能原理PrinciplesofArtificialIntelligence.ppt(96页珍藏版)》请在三一文库上搜索。
1、人工智能原理 Principles of Artificial Intelligence,王文杰 信息学院 W,搜索技术 (一),主要内容,概述 状态空间的搜索 状态空间的一般搜索过程 盲目搜索 启发式搜索 约束满足问题 博弈,概述(1),问题求解 AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程. 问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学 1974年,Nilsson归纳出的AI研究的基本问题 知识的模型化和表示 常识性推理、演绎和问题解决 启发式搜索 人工智能系统和语言 本章讨论的表示主要包括: 状态空间表示 问题空间表示,搜索
2、(2),什么是搜索 根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索 包括两个方面: - 找到从初始事实到问题最终答案的一条推理路径 - 找到的这条路径在时间和空间上复杂度最小 搜索分两大类: 盲目搜索:也称为无信息搜索,即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略 启发式搜索: 在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解,状态空间表示法(1),状态空间表示法:用来表示问题及其搜索过程的一种方法 状态 状态是描述问题求解过程中任一时刻状况的数据结构.
3、,A,B,C,D,(2, 3,7 ,0 , 5, 2, 4, 8, 6),状态空间表示法(2),一般一个搜索问题由四个部分组成: 初始状态集合:定义了agent所处的环境; 操作符集合:把一个问题从一个状态变换为另一个状态的动作; 目标检测函数:agent用来确定一个状态是不是目标; 路径费用函数:对每条路径赋予一定费用的函数。 初始状态集合和操作符集合定义了问题的搜索空间,吸尘器问题,states? 灰尘和吸尘器的位置 ,共有2228 actions? Left, Right, Suck goal test? 所有位置都没有灰尘 path cost? 每一步消耗为1,八数码问题,states
4、? 数字的位置 ,共有9!/2=181440 actions? 空格的上下左右移动 goal test? 给定的目标状态 path cost? 每一步消耗为1,状态空间表示法(3),二阶梵塔问题 设有三个钢针,在一号钢针上穿有A,B两个金片,A小于B,A位于B的上面.要求把这两个金片全部移到另一个钢针上,而且规定每次只能移动一片,任何时刻都不能使B位于A的上面 设用Sk=(Sk0,Sk1)表示问题的状态,SK0表示金片A所在的钢针号,SK1表示金片B所在的钢针号,全部可能的状态为: S0=(1,1), S1=(1,2), S2=(1,3) S3=(2,1), S4=(2,2), S5=(2,3
5、) S6=(3,1), S7=(3,2), S8=(3,3) 问题初始状态集合S=S0, 目标状态集合G=S4,S8. 算符:A( i,j):表示把金片A从第i号针移到第j号针上 B(i,j):表示把B从第i号针移到第j号针上 共12个算符: A(1,2), A(1,3), A(2,1) ,A(2,3), A(3,1),A(3,2) B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2),状态空间表示法(4),用状态空间表示,首先必须定义状态的描述形式,把问题的一切状态都表示出来,其次定义算符,完成状态的转换 问题的求解过程就是一个把算符不断地作用于状态的
6、过程.如果在使用某个算符后得到的状态就是目标状态,就得到了问题的解.这个解就是从初始状态到目标状态所用算符构成的序列. 算符的一次使用,就使问题由一种状态转变为另一种状态.可能有多个算符序列都可使问题从初始状态变到目标状态,这就得到了多个解. 对任何一个状态,可使用的算符可能不止一个,这样由一个状态所生成的后继状态可能有多个.如何选择下一步的操作,由搜索策略决定.,回溯搜索控制策略( 1),例:四皇后问题,( ),( ),Q,(1,1),( ),Q,Q,(1,1),(1,1) (2,3),( ),Q,(1,1),(1,1) (2,3),( ),Q,Q,(1,1),(1,1) (2,3),(1,
7、1) (2,4),( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),( ),Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),( ),(1,1),(
8、1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),Q,(1,2) (2,4) (3,1),回溯搜索控制策略( 2),对于n皇后问题可用于对搜索算法进行测试 对这类问题的形式化描述主要有两类: 增量形式化:包括了增加状态描述的算符,从空状态开始;这意味着每次行动添加一个皇后到状态中去 完全状态形式化:把8个皇后都放在棋盘上,然后移动它们。,现实问题,旅行商问题 超大规模集成电
9、路的布局问题 机器人导航问题 .,度量问题求解的性能,一般搜索策略可以通过下面四个准则来评价: 完备性:如果存在一个解答,该策略是否保证能够找到? 时间复杂性:需要多长时间可以找到解答? 空间复杂性:执行搜索需要多少存储空间? 最优性:如果存在不同的几个解答,该策略是否可以发现最高质量的解答? 搜索策略反映了状态空间或问题空间扩展的方法,也决定了状态或问题的访问顺序。 在AI领域,状态空间图由初始状态和算子隐含地表示,经常是无限的,它的复杂度根据下面三个值来表达: 分支因子b:任何节点的后继的最大个数 最浅的目标节点的深度d 状态空间中任何路径的最大长度m,与/或树表示法(1),基本概念 与/
10、或树是用于表示问题及其求解过程的又一种形式化方法. 复杂问题的简化方法 分解:把一个问题分解到不需再分解或不能再分解为止,然后对每个子问题进行求解,然后把各子问题的解复合起来,就得到原问题的解. 等价变换:利用同构或同态的等价变换,把复杂问题转换成若干个较为容易求解的新问题.若新问题中有一个可求解,则就得到了原问题的解.,与/或树表示法(2),三阶梵塔问题 设有A,B,C三个金片以及三个钢针,三个金片按自上而下从小到大的顺序穿在1号钢针上,要求把它们全部移到3号钢针上,而且每次只能移到一个金片,任何时候都不能把大的金片压在小的金片上面. 用与/或树表示:问题分解 (1)为了把三个金片全部移到3
11、号针上,必须先把C移到3号针上 (2)为了移到C,必须把A和B移到2号针上 (3)当C移到3针后,就可把A和B移到3针上,完成问题求解 得到三个子问题 (1)把A和B移到2号针的双金片问题 (2)把C移到3号针的单金片问题 (3)把A和B移到3号针的双金片问题,状态空间搜索过程要点(1),求解一个能够满足目标条件的问题可以表达为搜索一个图以找到一个满足目标状态描述的节点问题。 搜索过程的要点如下: 起始节点:对应于初始状态描述 后继节点:把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点,称为该节点的后继节点 指针:从每个后继节点返回指向其父辈节点 检查各后继节点看是否为目标节点.
12、 搜索过程扩展后继节点的次序 如果搜索是以接近起始节点的程度(由节点之间连结弧线的数目来衡量)依次扩展节点,称为广(宽)度优先搜索 如果搜索时首先扩展最新产生的节点,称为深度优先搜索,状态空间搜索过程要点(2),调整指针 扩展一个节点 生成出该节点的所有后继节点。 弧的费用 有一条弧连接ni和nj两个节点, 用C(ni, nj)表示从ni到nj的费用(耗散值)。 路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。,状态空间的一般搜索过程(1),主要数据结构 OPEN表:存放刚生成的节点,是还未扩展的节点.一般是端节点.
13、CLOSED表:存放将要扩展或已扩展的节点.或者是已被扩展但还没有在搜索树中生成后继节点的端节点,或者是非端节点,状态空间的一般搜索过程(2),(1)把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G (2)检查OPEN表是否为空,若为空则问题无解,退出 (3)把OPEN表的第一个节点取出放入CLOSED表,记该节点为n (4)考察n是否为目标节点.如是,则问题得解,退出 (5)扩展节点n,生成一组子节点.把其中不是节点n先辈的那些节点记作集合M,并把这些子节点作为节点n的子节点加入G中 (6)针对M中子节点的不同情况,分别进行处理 对于那些未曾在G中出现过的M成员设置一个指向父节
14、点(即n)的指针,并把它们放入OPEN表 对于那些先前已在G中出现过的M成员,确定是否需要修改它指向父节点的指针 对于那些先前已在G中出现并且已经扩展了的M成员,确定是否需要修改其后继节点指向父节点的指针 (7)按某种搜索策略对OPEN表中的节点进行排序 (8)转第(2)步,例子,2,S,1,3,2,10,11,OPEN表中的节点修改指针,2,S,1,3,2,8,9,10,11,CLOSE表中的节点修改指针,2,S,1,3,2,8,9,10,11,CLOSE表中的节点(8)的后裔(10)修改指针,状态空间的一般搜索过程(3),这是一个通用的搜索过程,后面讨论的状态空间各种搜索策略都是其特例.各
15、种搜索策略的主要区别就是对OPEN表中节点排序准则不同 算法结束后,将生成一个图G,称为搜索图。同时由于每个节点都有一个指针指向父节点,这些指针指向的节点构成G的一个支撑树,称为搜索树。 从目标节点开始,将指针指向的状态回串起来,即找到一条解路径.,盲目搜索,盲目 搜索策略只使用问题定义中的信息 宽度优先搜索 代价一致搜索 深度优先搜索 深度有限搜索 迭代加深搜索,广度优先搜索(1),搜索过程如下: (1)把初始节点S0放入OPEN表 (2)如果OPEN表为空,则问题无解,退出 (3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表 (4)考查节点n是否为目标节点.若是,则求得了
16、问题的解,退出 (5)若节点n不可扩展,则转第(2)步 (6)扩展节点n,将其子节点放入OPEN表的尾部,并为每一个子节点都配置指向父节点的指针,转第(2)步 扩展最浅的未扩展的节点 实现: FIFO队列,2 3 1 8 4 7 6 5,1,2,5,6,7,3,目标,8,4,广度优先搜索(2),Complete? Yes (如果 b 是有限的) Time? 1+b+b2+b3+ +bd + b(bd-1) = O(bd+1) Space? O(bd+1) Optimal? Yes (如果每步代价为1) 空间是大问题(和时间相比) 特点 缺点 当目标节点距离初始节点较远时会产生许多无用的节点,搜
17、索效率低 优点 只要问题有解,则总可以得到解,而且是最短路径的解,深度优先搜索(1),搜索过程如下: (1)把初始节点S0放入OPEN表 (2)如果OPEN表为空,则问题无解,退出 (3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表 (4)考查节点n是否为目标节点.若是,则求得了问题的解,退出 (5)若节点n不可扩展,则转第(2)步 (6)扩展节点n,将其子节点放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步 扩展最深的未扩展节点 实现: LIFO队列,2 3 1 8 4 7 6 5,2,3,4,5,6,7,8,9,a,b,c,d,目标,深度优先搜索
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 原理 PrinciplesofArtificialIntelligence
链接地址:https://www.31doc.com/p-2584185.html