人工智能课件第3章搜索策略.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《人工智能课件第3章搜索策略.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 课件 搜索 策略
- 资源描述:
-
1、2022-11-161第3章 搜索策略n问题求解系统划分为两大类n知识贫乏系统 n依靠搜索技术解决问题 n知识贫乏、缺乏针对性n效率低 n知识丰富系统 n依靠推理技术解决问题n基于丰富知识的推理技术,直截了当 n效率高 2022-11-162 n对于给定的问题,智能系统的行为一般是找对于给定的问题,智能系统的行为一般是找到能够达到所希望目标的动作序列,并使其所到能够达到所希望目标的动作序列,并使其所付出的付出的代价最小、性能最好代价最小、性能最好。n基于给定的问题,问题求解的第一步是目标基于给定的问题,问题求解的第一步是目标的表示。的表示。n搜索就是找到智能系统的动作序列的过程。搜索就是找到智
2、能系统的动作序列的过程。2022-11-163n和通常的搜索空间不同,人工智能中大多数问题和通常的搜索空间不同,人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。的状态空间在问题求解之前不是全部知道的。在人工智能中,搜索问题一般包括两个重在人工智能中,搜索问题一般包括两个重要的问题:要的问题:v搜索什么搜索什么搜索什么通常指的就是目标。搜索什么通常指的就是目标。v在哪里搜索在哪里搜索在哪里搜索就是在哪里搜索就是“搜索空间搜索空间”。搜索空间通常。搜索空间通常是指一系列状态的汇集,因此称为状态空间。是指一系列状态的汇集,因此称为状态空间。2022-11-164n所以,人工智能中的搜索可
3、以分成两个所以,人工智能中的搜索可以分成两个阶段:阶段:n状态空间的生成阶段状态空间的生成阶段n在该状态空间中对所求问题状态的搜索在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分搜索可以根据是否使用启发式信息分为为v盲目搜索盲目搜索v启发式搜索启发式搜索 2022-11-165n盲目搜索盲目搜索 只是可以区分出哪个只是可以区分出哪个是目标状态。是目标状态。一般是按预定的搜索一般是按预定的搜索策略进行搜索。策略进行搜索。没有考虑到问题本身没有考虑到问题本身的特性,这种搜索具有的特性,这种搜索具有很大的盲目性,效率不很大的盲目性,效率不高,不便于复杂问题的高,不便于复杂问题的求解
4、。求解。o启发式搜索启发式搜索是在搜索过程中加入了与问题有关的启发式信息,用于指导搜索朝着最有希望的方向前进,加速问题的求解并找到最优解。2022-11-166n根据问题的表示方式分为根据问题的表示方式分为n状态空间搜索状态空间搜索n与或树搜索与或树搜索状态空间状态空间搜索是用搜索是用状态空间状态空间法来求解法来求解问题所进问题所进行的搜索行的搜索与与/或树搜或树搜索是指用问索是指用问题规约方法题规约方法来求解问题来求解问题时所进行的时所进行的搜索。搜索。2022-11-167n考虑一个问题的状态空考虑一个问题的状态空间为一棵树的形式。间为一棵树的形式。n宽度优先搜索宽度优先搜索n深度优先搜索
5、深度优先搜索如果根节点首先如果根节点首先扩展,然后是扩扩展,然后是扩展根节点生成的展根节点生成的所有节点,然后所有节点,然后是这些节点的后是这些节点的后继,如此反复下继,如此反复下去。去。在树的最深一层的节在树的最深一层的节点中扩展一个节点。点中扩展一个节点。只有当搜索遇到一个只有当搜索遇到一个死亡节点(非目标节死亡节点(非目标节点并且是无法扩展的点并且是无法扩展的节点)的时候,才返节点)的时候,才返回上一层选择其他的回上一层选择其他的节点搜索。节点搜索。2022-11-168n无论是宽度优先搜索还是深度优先搜索,无论是宽度优先搜索还是深度优先搜索,遍历节点的顺序一般都是固定的,即一遍历节点的
6、顺序一般都是固定的,即一旦搜索空间给定,节点遍历的顺序就固旦搜索空间给定,节点遍历的顺序就固定了。这种类型的遍历称为定了。这种类型的遍历称为“确定性确定性”的,也就是盲目搜索。的,也就是盲目搜索。n对于启发式搜索,在计算每个节点的参对于启发式搜索,在计算每个节点的参数之前无法确定先选择哪个节点扩展,数之前无法确定先选择哪个节点扩展,这种搜索一般也称为非确定的。这种搜索一般也称为非确定的。2022-11-169n完备性:完备性:n如果存在一个解答,该策略是否保证能够找如果存在一个解答,该策略是否保证能够找到?到?n时间复杂性:时间复杂性:n需要多长时间可以找到解答?需要多长时间可以找到解答?n空
7、间复杂性:空间复杂性:n执行搜索需要多少存储空间?执行搜索需要多少存储空间?n最优性:最优性:n如果存在不同的几个解答,该策略是否可以如果存在不同的几个解答,该策略是否可以发现最高质量的解答?发现最高质量的解答?搜索策略评价标准搜索策略评价标准:2022-11-1610有许多智力问题有许多智力问题(如梵塔问题、旅行商问题、八皇如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等后问题、农夫过河问题等)和实际问题(如路径规和实际问题(如路径规划、机器人行动规划等)都可以归结为划、机器人行动规划等)都可以归结为状态空间搜状态空间搜索索。用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题
8、的系统均定义一个状态状态空间空间,并通过适当的,并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。2022-11-1611n显式图与隐式图显式图与隐式图 n显式图显式图n把问题有关的全部状态空间图,即相应的全部有关知识(叙述性知识、过程性知识和控制性知识),都直接存入知识库 n隐式图隐式图n只存储与问题求解有关的部分知识(即部分状态空间)。这种存储方式称为隐式存储。2022-11-1612n图搜索的基本思想图搜索的基本思想 n图搜索图搜索-一种在图中寻找路径的方法一种在图中寻找路径的方法 n从图中的初始节点开始,至目标节点为止。n初始节点和目标节点分别代表产生式系统
9、的初始数据库和满足终止条件的数据库。n方法:把问题的初始状态作为当前状态,选择适用的算符对其进行操作,生成一组子状态,检查目标状态是否在其中出现。若出现,则搜索成功,找到了问题的解;若不出现,则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程,直到目标状态出现或者不再有可供操作的状态及算符时为止。2022-11-1613 n三个钱币可能出现的状态有8种组合:Q0=(0,0,0),Q1=(0,0,1),Q2=(0,1,0),Q3=(0,1,1),Q4=(1,0,0),Q5=(1,0,1),Q6=(1,1,0),Q7=(1,1,1)。2022-11-1614三枚钱币问题的状态空
10、间图三枚钱币问题的状态空间图 2022-11-1615nS问题求解(即搜索)过程中所有可能到达的合法状态构成的集合;nO操作算子的集合,操作算子的执行会导致问题状态的变迁;n状态用于记载问题求解(即搜索)过程中某一时刻问题现状的快照;n抽象为矢量形式 Q=q0,q1,qnTn每个元素qi称为状态分量 n给定每个状态分量qi的值就得到一个具体的状态 Qk=q0k,q1k,qnkT2022-11-1616状态状态表示状态的变迁表示状态的变迁操作算子操作算子问题的状态空间问题的状态空间是一个表示该问题的全部可能状态是一个表示该问题的全部可能状态及其变迁的及其变迁的有向图有向图。n节点n状态n有向弧n
11、状态的变迁 n弧上的标签n导致状态变迁的操作算子 用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题的系统均定义一个状态状态空间空间,并通过适当的,并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。2022-11-1617:n1)船上人数不得超过载重限量,设为K个人;n2)任何时刻(包括两岸、船上)野人数目不得超过传教士;n3)允许在河的某一岸或者在船上只有野人而没有传教士;2022-11-16182022-11-1619可能到达的合法状态:442=32 n(0,0,1),(0,3,0),(3,0,1),(3,3,0)2022-11-1620(2)状态
12、空间表示的经典例子“传教士和野人问题”n定义2类操作算子:nL(x,y)指示从左岸到右岸的划船操作 nR(x,y)指示从右岸到左岸的划船操作nx+y K=2(船的载重限制);nx和y取值的可能组合只有5个n10,20,11,01,02 n(允许在船上只有野人而没有传教士)n共有10个操作算子2022-11-16212022-11-1622 2022-11-1623 2022-11-1624 例例:在一个在一个33的方格棋盘上放置着的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些八个数码,每个数码占一格,且有一个空格。这些数码可在棋盘上移动,其移动规则
13、是:与空格相邻数码可在棋盘上移动,其移动规则是:与空格相邻的数码方可移入空格。的数码方可移入空格。现在的现在的问题问题是:对于指定的是:对于指定的初始棋局初始棋局和和目标棋局目标棋局,给出给出数码的移动序列数码的移动序列。该问题称为。该问题称为八数码问题八数码问题。2831476581324765初始棋局初始棋局目标棋局目标棋局移动数码移动数码2022-11-16252 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6
14、4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 52022-11-1626n或图(一般图)或图(一般图)n一个状态可以有多个可供选择的操作算子;n操作算子间的选择是一种“或”的关系;n这样的有向图称为或图。2022-11-1627n或图(一般图)或图(一般图)n一个状态可以有多个可供选择的
15、操作算子;n操作算子间的选择是一种“或”的关系,这样的有向图称为或图。n状态空间一般都表示为或图(一般图)n搜索图在搜索解答路径的过程中画出搜索时涉及到的节点和弧线,构成所谓的搜索图。状态空间搜索状态空间搜索一般图搜索一般图搜索2022-11-1628n符号说明:ns-初始状态节点nG-搜索图nOPEN-存放待扩展节点的表nCLOSE-存放已被扩展的节点的表nMOVE-FIRST(OPEN)-取OPEN表首的节点作为当前要被扩展的节点n,同时将节点n移至CLOSE表n一般图搜索算法划分为二个阶段:n1、初始化 n2、搜索循环 一般图搜索算法2022-11-1629n算法划分为二个阶段:n1、初
16、始化 n建立只包含初始状态节点s的搜索图G:=snOPEN:=snCLOSE:=n2、搜索循环nMOVE-FIRST(OPEN)-取出OPEN表首的节点n作为扩展的节点,同时将其移到close表 n扩展出n的子节点,插入搜索图G和OPEN表 n适当的标记和修改指针n排序OPEN表n通过循环地执行该算法,搜索图G会因不断有新节点加入而逐步长大,直到搜索到目标节点。一般图搜索算法2022-11-1630初始布局初始布局目标布局目标布局移动数码移动数码2022-11-16315864273012022-11-16325864273012022-11-1633586427301586427031586
17、4073215864273102022-11-16345864273015864270315864073215864273102022-11-16355864273015864270315864073215864273102022-11-16365864273015864270315864073215864273105064873215864703215860473212022-11-16375864273015864270315864073215864273105064873215864703215860473212022-11-1638586427301586427031586407321
18、5864273105064873215864703215860473215864273102022-11-16395864273015864270315864073215864273105064873215864703215860473215604873210564873212022-11-16405864273015864270315864073215864273105064873215864703215860473215604873210564873212022-11-1641586427301586427031586407321586427310506487321586470321586
19、0473215604873210564873212022-11-16425864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-11-16435864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-11-1644586427301586427031586407321586427310506487321586470321586047
20、3215604873210564873215674803212022-11-16455864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-11-16465864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-11-1647586427301586427031
21、5864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-11-16485864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-11-1649586427301586427031586407321586427310506487321586470321586047321560487321056487
22、3215674803215674813205674083212022-11-1650n节点n扩展后的子节点分为3类:n(i)全新节点n(ii)已出现在OPEN表中的节点n(iii)已出现的CLOSE表中的节点n指针标记和修改的方法:n(i)类节点:加入OPEN表,建立从子节点到父节点n的指针n(ii)类节点、(iii)类节点n比较经由老父节点、新父节点n到达初始状态节点的路径代价 n经由节点n的代价比较小,则移动子节点指向老父节点的指针,改为指向新父节点nn(iii)类节点还得从CLOSE表中移出,重新加入OPEN表。搜索过程中的指针修改2022-11-1651Sn4ninjn1n2n3n31
23、n32n节点ni是当前扩展的节点;n扩展出4个后续节点;nn1、n2是新节点,只需建立指向父节点的指针,并加入OPEN表;2022-11-1652Sn4ninjn1n2n3n31n32nn4已经存在于OPEN表,并且已有父节点njnn4经nj的路径代价大n取消n4指向nj的指针n改为建立n4指向新父节点ni的指针nn3已经存在于CLOSE表,并且已有父节点njn需要做和n4同样的比较和指针修改工作。并且要重新加入open表。2022-11-1653 n一般图搜索算法中,提高搜索效率的关键在于一般图搜索算法中,提高搜索效率的关键在于优化优化OPEN表中节点的排序方式表中节点的排序方式。n若每次排
24、在表首的节点都在最终搜索到的若每次排在表首的节点都在最终搜索到的解答路径上,则算法不会扩展任何多余的解答路径上,则算法不会扩展任何多余的节点就可快速结束搜索。节点就可快速结束搜索。n一种简单的排序策略就是按预先确定的顺一种简单的排序策略就是按预先确定的顺序或序或随机地随机地排序新加入到排序新加入到OPEN表中的节表中的节点,常用的方式是点,常用的方式是深度优先深度优先和和宽度优先宽度优先。2022-11-1654 nOPEN表中节点简单的排序方式:n宽度优先扩展当前节点后生成的子节点总是置于OPEN表的后端,即OPEN表作为队列,先进先出,使搜索优先向横向方向发展。2022-11-1655宽度
25、优先宽度优先实例实例2 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标目标82 3 41 8 7 6 54910111213141516172022-11-1656宽度优先搜索 如果搜索是以接近起始节点
展开阅读全文