首页 人工智能基础搜索技术讲义

人工智能基础搜索技术讲义

举报
开通vip

人工智能基础搜索技术讲义人工智能基础搜索技术3.1盲目搜索3.1.1图搜索策略例3.1从王某家族的四代中找王A的后代且其寿命为X的人A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51人工智能基础搜索技术3.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)的一般过程(1)建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表,其初始为空表。(3)LOOP:若OPEN表是空表,则失败退出。(...

人工智能基础搜索技术讲义
人工智能基础搜索技术3.1盲目搜索3.1.1图搜索策略例3.1从王某家族的四代中找王A的后代且其寿命为X的人A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51人工智能基础搜索技术3.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)的一般过程(1)建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表,其初始为空表。(3)LOOP:若OPEN表是空表,则失败退出。(4)选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。人工智能基础搜索技术3.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)的一般过程(6)扩展节点n,同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员,确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员,确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值,重排OPEN表。(9)GOLOOP。人工智能基础搜索技术3.1盲目搜索节点父辈节点3.1.1图搜索策略2.图搜索算法的几个重要名词(1)OPEN表与CLOSE表OPEN表CLOSED表编号节点父辈节点人工智能基础搜索技术3.1盲目搜索3.1.1图搜索策略3.搜索图与搜索树搜索过程框图开始初始化:S放入OPEN表,CLOES表置空,n=1OPEN表中的第一个结点n移至CLOSE表若n的后继未曾在搜索图G中出现,则将其放入OPEN表的末端,并提供返回结点n的指针,置n=n+1根据后继结点在搜索图G中的出现情况修改指针方向依某种准则重新排序OPEN表失败成功NYNOPEN为空表NULL?n=目标结点D吗?Y人工智能基础搜索技术3.1盲目搜索3.1.1图搜索策略4.图搜索方法分析:图搜索过程的第8步对OPEN表上的节点进行排序,以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索),也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时,这一过程就宣告成功结束。这时,能够重现从起始节点到目标节点的这条成功路径,其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时,过程就以失败告终(某些节点最终可能没有后继节点,所以OPEN表可能最后变成空表)。在失败终止的情况下,从起始节点出发,一定达不到目标节点。人工智能基础搜索技术3.1盲目搜索3.1.2宽度优先搜索定义3.1如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)人工智能基础搜索技术3.1盲目搜索3.1.2宽度优先搜索宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。(2)如果OPEN是个空表,则没有解,失败退出;否则继续。(3)把第一个节点(节点n)从OPEN表移出,并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点,则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第(2)步。人工智能基础搜索技术3.1盲目搜索3.1.2宽度优先搜索例3.2八数码问题操作规定:允许空格四周上、下、左、右的数码块移入空格中,不许斜方向移动,不许返回先辈结点。初始布局S和目标状态D如下图所示:人工智能基础搜索技术3.1盲目搜索3.1.2宽度优先搜索例3.2八数码问题人工智能基础搜索技术3.1盲目搜索3.1.3深度优先搜索深度优先算法步骤:(1)初始结点S放到未扩展节点OPEN中;(2)若OPEN为空,则搜索失败,问题无解;(3)弹出OPEN表中最顶端结点放到CLOSE表中,并给出顺序编号n;(4)若n为目标结点D,则搜索成功,问题有解;(5)若n无子结点,转(2);(6)扩展n结点,将其所有子结点配上返回n的指针,并按次序压入OPEN堆栈,转(2)。人工智能基础搜索技术3.1盲目搜索3.1.3深度优先搜索人工智能基础搜索技术3.1盲目搜索3.1.3深度优先搜索有界深度优先搜索:引入搜索深度限制值d,使深度优先搜索过程具有完备性。设定搜索深度限制d=5,问题同深度优先算法中的八数码问题(2)。人工智能基础搜索技术3.1盲目搜索3.1.3深度优先搜索人工智能基础搜索技术3.1盲目搜索3.1.3深度优先搜索有界深度优先算法步骤:(1)初始结点S放入堆栈OPEN中;(2)若OPEN为空,则搜索失败,问题无解;(3)弹出OPEN中栈顶结点n,放入CLOSE表中,并给出顺序编号n;(4)若n为目标结点D,则搜索成功,问题有解;(5)若n的深度d(n)=d,则转(2);(6)若n无子结点,即不可扩展,转(2);(7)扩展结点n,将其所有子结点配上返回n的指针,并压入OPEN堆栈,转(2)。人工智能基础搜索技术3.1盲目搜索3.1.4等代价搜索宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题,这种推广了的宽度优先搜索算法叫做等代价搜索算法。等代价搜索中的几个记号起始节点记为S;从节点i到它的后继节点j的连接弧线代价记为c(i,j);起始节点S到任一节点i的路径代价记为g(i)。如果所有的连接弧线具有相等的代价,那么等代价算法就简化为宽度优先搜索算法。人工智能基础搜索技术3.2启发式搜索盲目搜索的不足:效率低,耗费空间与时间。启发式搜索:利用问题域特性的信息(启发信息)进行搜索。3.2.1启发式搜索策略启发式信息按用途分为三种:(1)用于确定要扩展的下一个节点,避免盲目扩展。(2)在扩展一个节点的过程中,用于确定要生成哪一个或哪几个后继节点,避免盲目生成所有可能节点。(3)用于确定某些应该从搜索树中抛弃或修剪得节点。人工智能基础搜索技术3.2启发式搜索有序搜索(orderedsearch):利用第一种启发信息,总是选择“最有希望”的节点作为下一个被扩展的节点。估价 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数(evaluationfunction):估算节点“希望”的量度,这种量度叫做估价函数。建立估价函数的一般方法:试图确定一个处在最佳路径上的节点的概率;提出任意节点与目标集之间的距离量度或差别量度;或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 f(n)——表示节点n的估价函数值 人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索(best-firstsearch),而其算法就叫做有序搜索算法或最佳优先算法。人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索有序状态空间搜索算法:(1)把起始节点S放到OPEN表中,计算f(S)并把其值与节点S联系起来。(2)如果OPEN是个空表,则失败退出,无解。(3)从OPEN表中选择一个f值最小的节点i。结果有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i。(4)把节点i从OPEN表中移出,并把它放入CLOSED的扩展节点表中。  人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索 (5)如果i是个目标节点,则成功退出,求得一个解。 (6)扩展节点i,生成其全部后继节点。对于i的每一个后继节点j:(a)计算f(j)。(b)如果j既不在OPEN表中,又不在CLOSED表中,则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针,以便一旦找到目标节点时记住一个解答路径。(c)如果j已在OPEN表上或CLOSED表上,则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小,则 人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索  (i)以此新值取代旧值。  (ii)从j指向i,而不是指向它的父辈节点。  (iii)如果节点j在CLOSED表中,则把它移回OPEN表。 (7)转向(2),即GOTO(2)。人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索  开始把S放入OPEN表OPEN为空表?失败选取OPEN表中f值最小的节点i,放入CLOSED表i=Sg?成功是是扩展i得后继节点j,计算f(j),提供返回i的指针,利用f(j)对OPEN表重新排序调整父子关系及指针人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索   宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索,选择f(i)作为节点i的深度。对于等代价搜索,f(i)是从起始节点至节点i这段路径的代价。  有序搜索的有效性直接取决于f的选择,如果选择的f不合适,有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度,那么f的选择将涉及两个方面的内容:一方面是一个时间和空间之间的折衷 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ;另一方面是保证有一个最优的解或任意解。人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索例3.4:八数码难题,采用了简单的估价函数f(n)=d(n)+W(n)其中:d(n)是搜索树中节点n的深度;W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此,起始节点棋局的f值等于0+4=4。28316475人工智能基础搜索技术3.2启发式搜索3.2.2有序搜索28316475283164752831476528316475283147652318476528314765832147652837146523184765233184765123847651238476512378465人工智能基础搜索技术3.2启发式搜索3.2.3A*算法  A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。1.A*算法的估价函数k(ni,nj):表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点,函数k没有定义)。k(n,ti):从节点n到某个具体的目标节点ti,某一条最小代价路径的代价。h*(n):表示整个目标节点集合{ti}上所有k(n,ti)中最小的一个,因此,h*(n)就是从n到目标节点最小代价路径的代价,而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n,函数h*没有定义)。人工智能基础搜索技术3.2启发式搜索3.2.3A*算法  定义g*为g*(n)=k(S,n)从已知起始节点S到任意节点n的一条最佳路径代价。  定义函数f*,f*(n)=g*(n)+h*(n)使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和。  人工智能基础搜索技术3.2启发式搜索3.2.3A*算法希望估价函数f是f*的一个估计,此估计可由下式给出:f(n)=g(n)+h(n)其中:g是g*的估计;h是h*的估计。对于g(n):一个明显的选择就是搜索树中从S到n这段路径的代价,这一代价可以由从n到S寻找指针时,把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)≥g*(n)。h(n):对h*(n)的估计,依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。把h叫做启发函数。人工智能基础搜索技术3.2启发式搜索3.2.3A*算法2.A算法和A*算法的定义定义3.3在GRAPHSEARCH过程中,如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的,则称该过程为A算法。定义3.4在A算法中,如果对所有的x存在h(x)≤h*(x),则称h(x)为h*(x)的下界,它表示某种偏于保守的估计。定义3.5采用h*(x)的下界h(x)为启发函数的A算法,称为A*算法。当h=0时,A*算法就变为有序搜索算法。A算法和A*搜索算法的目标有所不同:A搜索算法虽然希望能找到问题的最优解,但主要追求的是求解效率;而A*搜索算法直接目标就在于要找到问题的最优解及其解的路径,即便搜索效率有所降低也在所不惜。人工智能基础搜索技术3.2启发式搜索3.2.3A*算法开始把S放入OPEN表,记f=hOPEN为空表?失败选取OPEN表中未设置过的具有最小f值的节点BESTNODE,放入CLOSED表BESTNODE=Sg?成功是是扩展BESTNODE,产生后继节点SUVVESSOR建立从SUCCESSOR返回BESTNODE的指针计算g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR)SUCCESSOR∈OPEN?否是人工智能基础搜索技术3.2启发式搜索3.2.3A*算法把SECCESSOR放入OPEN表,加入BESTNODE的后裔表g(SUCCESSOR)
本文档为【人工智能基础搜索技术讲义】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_179289
暂无简介~
格式:ppt
大小:824KB
软件:PowerPoint
页数:78
分类:建筑/施工
上传时间:2018-09-18
浏览量:10