《人工智能:计算Agent基础》——3.5 无信息搜索策略-阿里云开发者社区

开发者社区> 华章计算机> 正文

《人工智能:计算Agent基础》——3.5 无信息搜索策略

简介:
+关注继续查看

本节书摘来自华章计算机《人工智能:计算Agent基础》一书中的第3章,第3.5节,作者:(加)David L.Poole,Alan K.Mackworth 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.5 无信息搜索策略

一个问题给定了图和目标,但并没有给出从边界中选择哪条路径。这是搜索策略的任务,一个搜索策略指定如何从边界中选择路径。通过改变在边界中选择路径的实现方法从而可以得出不同的搜索策略。79
这部分介绍了三种不考虑目标节点位置的所谓无信息搜索策略(uninformed search strategy)。直觉上,这些算法不关心它们要到哪里去,直到找到目标节点并报告成功。
3.5.1 深度优先搜索
第一个策略是深度优先搜索(depth-first search)策略。在深度优先搜索中,边界的动作像一个先进后出的堆栈(stack)。这些元素被逐次地压入栈中。在边界中被选择并撤销的节点肯定是最后一个入栈的元素。
【例3-6】 考虑图3-5中的树形图,假设初始节点是树的根(在顶部的节点),节点从左到右排序,所以最左边的邻居最后被压入栈 在深度优先搜索中,节点扩展的方向并不依赖于目标节点的位置。图3-5中,我们将首批扩展的16个节点用数字标记出来了。阴影节点表示这16步检索完成后,边界路径上的最终节点。


23581e2618a5b584bf366d043ead2577ddc4a71d

注意最开始的6个节点是如何在单一的路径上扩展的。第6个节点没有邻居,因此,下一个要扩展的节点是距离它最近的且有尚未扩展的子节点的父节点的子节点。
利用堆栈来实现边界会导致使用深度优先的方式得到路径——在查找一条路径到头之后再尝试另一个分支路径。这种方法叫做回溯(backtracking):在每一个节点,算法会先选择每个节点上第一条可选择的路径搜索下去,当执行完第一个选择的整个路径它会回溯到下一个80可选的路径。一些路径可能是无限的,比如当图中有环或者有无限多节点时,这样深度优先搜索也许永远不会停止。
这种算法没有明确规定将邻居压入堆栈的顺序,并用堆栈代表了边界。算法的效率就跟这个顺序相关。
【例3-7】 考虑图3-2中的从房间o103出发的深度优先搜索,唯一的目标节点是r123。在这个例子里,边界表示为一个路径列表,栈顶作为列表的开始部分。
最初,边界包含平凡路径〈o103〉。
下一步,边界包含了后面的路径:[〈o103,ts〉,〈o103,b3〉,〈o103,o109〉]。
接下来,会选择路径〈o103,ts〉,因为它位于栈顶。这条路径就从边界中删除并用一段弧扩展它后再替换它,这样边界就变为:[〈o103,ts,mail〉,〈o103,b3〉,〈o103,o109〉]。
接下来,第一条路径〈o103,ts,mail〉也就被删除并被用一段新弧扩展后的一个路径集所替代,但由于mail节点没有邻居,所以该集合是空的。因此边界变为:[〈o103,b3〉,〈o103,o109〉]。
在这个阶段,路径〈o103,b3〉在堆栈的顶部。注意一个事实,当深度搜索已经遍历了所有的从ts出发的路径(这里只有一条),它就要回溯到堆栈的下一个元素。接下来,选择〈o103,b3〉,并用新弧的扩展路径替换它,边界变为:[〈o103,b3,b1〉,〈o103,b3,b4〉,〈o103,o109〉]。
然后从边界中选择〈o103,b3,b1〉并扩展,边界变为:[〈o103,b3,b1,c2〉,〈o103,b3,b1,b2〉,〈o103,b3,b4〉,〈o103,o109〉]。
现在第一条路径就从边界中选出来了,并通过新弧扩展出来,产生边界路径:[〈o103,b3,b1,c2,c3〉,〈o103,b3,b1,c2,c1〉,〈o103,b3,b1,b2〉,〈o103,b3,b4〉,〈o103,o109〉]。
注意节点c3没有邻居,因此搜索回溯到最近的尚未造访的节点,即c1。
假定〈n0,…,nk〉是在边界中被选定的路径,边界的每一个其他元素都表示为〈n0,…,ni,m〉,其中i为了更好地理解深度优先的复杂度(参见下面“各种算法性能对比”的内容),考虑使用家族树来类比,一个节点的邻居对应的是树中的子节点。树的根是起始节点,树的分支对应的是从起始节点开始的路径。考虑边界顶端的路径的最终节点,边界的其他元素是这个节点父节点的其他子节点,对应就是“叔叔”、“伯伯”,等等。如果分支系数是b,列表的第一个元素的长度是n,那么最多有n×(b-1)个边界的其他元素。这些元素对应着每一个节点都有b-1个可选路径。因此,对于深度优先搜索,使用的空间开销与从起始节点到某一个节点的路径长度呈线性关系。各种算法性能对比各种算法(包含搜索算法)可以按以下几项进行比较:
  • 时间开销
  • 空间开销
  • 结果的质量以及准确性

时间开销、空间开销以及结果的准确性都是算法输入的函数。计算机科学家们所探讨的渐进复杂度(asymptotic complexity),规定了时空开销是如何随着算法的输入量的增加而增长的。算法对于输入大小n有时间(或空间)的复杂度函数O(f(n)),读作“大Of(n)”,这里f(n)是关于n的函数,如果存在常数n0和k,对于所有的n>n0, 都有算法的时间或空间开销少于k×f(n)。这个函数的最常见形式是指数函数,如2n、3n、1.015n;多项式函数,如n5、n2、n、n1/2;或对数函数,如logn。一般来说,指数函数算法比多项式函数算法复杂度增长更快,相应的,多项式函数算法比对数函数增长的快。
当输入大小为n时,如果存在常数n0和k,对于所有的n>n0,都有算法的时间或空间开销大于k×f(n),就称算法有时间或空间复杂度Ω(f(n))。一个算法如果有复杂度O(n)和Ω(n),那么它就有时间或空间的复杂度Θ(f(n))。通常情况下,不能说一个算法的复杂度是Θ(f(n)),因为大多数算法输入不同,时间开销也不同。因此,当比较算法时,必须确定问题分类。
当通过时间、空间或准确性某个方面衡量出算法A比算法B更优,则意味着:

  • A最坏的情况比B的最坏的情况好;
  • 在实践中,A能更好运行。或者在考虑典型性问题的平均情况时,A运行的平均情况比B好;
  • 由你描述哪类问题使用算法A比B好,所以算法的优劣取决于要解决的问题;
  • 对于任何的问题,A都比B好。

最坏情况的渐进式复杂度往往最容易显现,但它通常是最没用的。如果很容易确定所给定问题是哪一类,通过对问题的特征分类来决定哪种算法更优是最有用的方法。不幸的是,这种特征分类很难。
通过对问题的特征分类来确定哪种算法更优,可以在理论上通过数学方法或在经验上通过建立程序来实现。这些数学定理的有效性只能依赖于作为基础的假设。相似地,基于经验的程序验证只能在测试用例和算法实际的实现方法中有效。我们很容易通过举个反例来反驳一种算法对某类问题更优的猜想,但却很难证明这种猜想。如果第一个分支搜索就得到一个解,那么时间复杂度就与路径的深度呈线性关系,它只考虑这条路径上的元素,以及它的兄弟姐妹。最坏情况的时间复杂度是无限大。即使存在一个解,如果这个图是无限的或者循环的,深度优先搜索会陷入无限的分支然后永远找不到解。如果图是有限的树,前向分支系数最大是b,深度为n,那么最坏情况的时间复杂度是O(bn)。
【例3-8】 考虑修改前面的图,让Agent在位置之间移动更自由,得出图3-6,一条无限的路径从ts指向mail,然后回到ts,再返回mail,如此循环往复。显然,深度优先搜索将沿着这条路径永远搜索下去,而不会考虑到b3或者o109等可选择路径。前5次反复使用深度优先路径搜索算法得到的边界如下:

[〈o103〉]
[〈o103,ts〉,〈o103,b3〉,〈o103,o109〉]
[〈o103,ts,mail〉,〈o103,ts,o103〉,〈o103,b3〉,〈o103,o109〉]
[〈o103,ts,mail,ts〉,〈o103,ts,o103〉,〈o103,b3〉,〈o103,o109〉]
[〈o103,ts,mail,ts,mail〉,〈o103,ts,mail,ts,o103〉,〈o103,ts,o103〉,〈o103,b3〉,o103,o109〉]


2dcdd9e1e7445e550a5ffbd72f61cc844f5c9f73

可以通过不考虑有环路径来优化深度优先搜索。
因为深度优先搜索对邻居加入边界的顺序敏感,这一点必须仔细对待。这个顺序可以是静态的(这样邻居的顺序固定)或者是动态的(邻居的顺序由目标节点决定)。
深度优先搜索适用的条件:

  • 空间是被限定的;
  • 存在许多解,可能路径很长,尤其当几乎所有路径都导致一个解时;
  • 节点邻居的压栈的顺序可以调整,以便在第一次尝试中就找到解。
    深度优先搜索不适用的条件:
  • 当图是无限的或者图中有环的时候,有可能陷入无限的路径中;
  • 解路径存在于隐蔽的深度,因为在这种情况下可能要搜索很多条长路径才能发现短路径结果。
    深度优先搜索是许多其他搜索算法的基础,如迭代搜索。

3.5.2 宽度优先搜索
在宽度优先搜索(breadth-first search)中,边界是用一个先进先出(FIFO)队列实现的。因此,最开始从边界中选择的路径是最早进入队列的。
这个方法意味着从初始节点出发的路径按照弧数目多少的顺序依次产生。在每一个阶段中,选择弧最少的那条路径。84


1de871de06625c77c229661699c2309650d1ddca

【例3-9】 来看图3-7中的树形图。假定起始节点在顶部。在宽度优先搜索中,节点扩展的顺序与目标节点的位置无关,这与深度优先搜索相同。最开始搜索的16个节点的扩展顺序已经在图中标记出来了。在最开始扩展的16步完成后,阴影节点就是多条路径的末端,并组成了边界。
【例3-10】 考虑图3-2从o103的宽度优先搜索。唯一的目标节点是r123。最开始,边界是[〈o103〉]。然后经过o103的邻居得到扩展的边界,即[〈o103,ts〉,〈o103,b3〉,〈o103,o109〉]。这些都是o103的一条出弧所指向的节点。下面选择的三条路径是〈o103,ts〉,〈o103,b3〉,〈o103,o109〉,这个阶段,边界扩展为:[〈o103,ts,mail〉,〈o103,b3,b1〉,〈o103,b3,b4〉,〈o103,o109,o111〉,〈o103,o109,o119〉]。
这些路径都包含有两段弧,并都始于o103。经过下一步的边界节点选择和扩展,得到新的五条路径,这时边界包括的从o103出发的路径都含有三段弧。记作:[〈o103,b3,b1,c2〉,〈o103,b3,b1,b2〉,〈o103,b3,b4,o109〉,〈o103,o109,o119,storage〉,〈o103,o109,o119,o123〉]。
注意到边界的每一条路径都有近似相等的弧数。对于宽度优先搜索,通常边界中路径的弧数最大相差1条。85
假定搜索的分支系数是b。如果边界的第一条路径包含n段弧,那么边界中就至少有bn-1个节点。所有的这些路径包含n或者n+1段弧。因此,根据到达目标节点弧数最少的那条路径上的弧数,空间和时间复杂度呈指数级增长。无论如何,这个方法可以保证只要有解就能找到,并且是最少弧的解。
宽度优先搜索适用于:
  • 不存在空间问题;
  • 想找最少弧的路径;
  • 可能有很少的解,但是至少有一个短路径解;
  • 可能存在无限的路径,因为它会遍历所有的搜索空间,即使是无限的路径。

这个算法并不适用于所有的路径都很长,或者有一些可用的启发知识的情况。因为空间复杂度很大,所以它并不常用。
3.5.3 最低花费优先搜索
当路径的花费与弧有关时,我们常常想找到总花费最小的路径。例如,对于一个投递机器人,花费可能是两位置之间的距离,我们需要总距离最短的那条解路径。花费也可能是机器人按照弧实施动作所需要的各种资源。一个指导系统的花费可能是学生所需要的时间和精力。在每一种情况下,搜索者都试图找到最低花费的解路径来达到目标。
目前为止考虑的搜索算法不能保证找到最低花费的路径,他们完全没有使用弧花费的任何信息。宽度优先搜索首先找到弧数最少的路径,但这未必是最少花费的路径。
最简单的能保证找到最低花费路径的搜索方法与宽度优先搜索算法相似。不同的是,它是寻找最低花费的路径,而不是通过扩展路径找最少弧数的路径。这是通过把边界作为一个由花费函数排序的优先级队列来实现的。
【例3-11】 看图3-2,考虑图中从o103开始的最低花费优先搜索。唯一的目标节点是r123。这个例子中,路径由最后的节点表示,下标是路径的花费值。
最初,边界是[o1030]。下一阶段是[b34,ts8,o10912]。因为b3的花费最小,所以选择了到b3的路径,结果边界变为:[b18,ts8,b411,o10912]。86
因为b1的花费最小,然后选择到b1的路径,结果为:[ts8,c211,b411,o10912,b214]。
因为ts的花费最小,然后选择到ts的路径,结果为:[c211,b411,o10912,mail14,b214]。
然后选择到c2的路径,如此循环。注意最低花费优先搜索是如何逐渐增长路径的,它总是扩展花费值最低的路径。
如果一个问题存在解路径,弧线的花费被界定为低于一个正常数且分支系数也是有限的,那么最低花费优先搜索就能确定找到一个最优解(即有最低花费的路径)。而且,最先找到的路径就是花费最低的路径。因为算法产生的路径从最初就是按照路径花费值排序的,所以这个解是最优的。如果存在一个比第一个被发现的解更优的解,它在边界中会被选择得更早。
界定的弧花费是用来保证最低花费搜索能找到最优解。如果没有这样的界定,就会有有限花费的无限路径。例如,对于每一个i>0,节点n0,n1,n2,…对应的弧线〈ni-1,ni〉中每一条弧线的花费都是1/2i,这样的话,存在很多形式为〈n0,n1,n2,…,nk〉的路径,它们的花费都小于1。如果有一条弧从n0到目标节点的花费大于或等于1,它将永远都不会被选中。这个就是早在2300年前亚里士多德写到的“芝诺悖论”的基础。
像宽度优先搜索,最低花费优先搜索在时间和空间上都是典型的指数函数。它会产生所有的低于解路径花费的从起始节点开始的路径。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云人工智能产品-图像搜索(商业化)发布
产品介绍: 图像搜索(Image Search)是以深度学习和机器视觉技术为核心,结合不同行业应用和业务场景,帮助用户在自建图库中实现相同或相似图片搜索的以图搜图服务。适用客户: 所有具有图像库,并有图像搜索需求的客户。
1072 0
阿里妈妈首次公开新一代智能广告检索模型,重新定义传统搜索框架
阿里妈妈提出一种超出关键词和相关性的搜索框架:电子商务搜索中的个性化广告检索框架。这个新的搜索广告智能检索模型引入用户行为异构图挖掘、机器学习等相关技术,通过模型学习的方式智能构建索引,解决了传统搜索广告检索系统不能解决的种种痛点。
1844 0
人工智能: 自动寻路算法实现(一、广度优先搜索)
前言 随着人工智能技术的日益发达,我们的生活中也出现了越来越多的智能产品。我们今天要关注的是智能家居中的一员:扫地机器人。
1672 0
人工智能: 自动寻路算法实现(二、深度优先搜索)
前言 本篇文章是机器人自动寻路算法实现的第二章。我们要讨论的是一个在一个M×N的格子的房间中,有若干格子里有灰尘,有若干格子里有障碍物,而我们的扫地机器人则是要在不经过障碍物格子的前提下清理掉房间内的灰尘。
1451 0
带你读《少儿人工智能趣味入门动画与游戏编程一本通》之二:角色的基础:“运动”“外观”“声音”模块
Scratch是图形化的编程语言,它具有学习环境趣味性强、操作简单且直观等特点,很好适合6-12岁的孩子学习。本书是立足于Scratch 3.0版本的少儿编程入门书,能让孩子轻松愉快地掌握编程技能,锻炼和提高思维能力和创造力,为迎接人工智能时代的到来做好准备。本书以对Scratch中积木块的分类讲解作为主线,并将编程的核心思想融入大量精心设计的案例,让孩子在实际动手操作中更直观、更深刻地理解不同积木块的运用。本书对积木块的功能和用法解释详尽,语言通俗易懂,能够减少孩子对编程的畏惧心理,没有编程基础的家长也能陪伴孩子一起阅读,在融洽的亲子互动氛围中,自信、愉快地完成学习。
248 0
【沉淀】从网络中间件到搜索,从移动开发到分布式计算平台,阿里高级专家李睿博谈自己的折腾路
整个过程我觉得还是爱最重要。有爱才有勇气才有希望。我是真的爱写代码。从小学就开始爱,到现在快三十年了也还爱。
25733 0
《中国人工智能学会通讯》——9.25 搜索引擎点击模型综述
本节书摘来自CCAI《中国人工智能学会通讯》一书中的第9章,第9.25节, 更多章节内容可以访问云栖社区“CCAI”公众号查看。
1455 0
《中国人工智能学会通讯》——4.20 粒计算在智能信息服务中的应用
本节书摘来自CCAI《中国人工智能学会通讯》一书中的第4章,第4.20节, 更多章节内容可以访问云栖社区“CCAI”公众号查看。
1117 0
10059
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载