《人工智能:计算Agent基础》——3.10 习题-阿里云开发者社区

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

《人工智能:计算Agent基础》——3.10 习题

简介:
+关注继续查看

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

3.10 习题

3.1 评论下面的话:人工智能的一个主要目标是为图搜索问题建立一般的启发信息。
3.2 在边界中的任一元素被选中这一方面来说,哪一种路径搜索程序是公平的?在没有环路的有限图,或者有环路的有限图,或者无限图(有有限的分支元素)中考虑这个问题。
3.3 看图3-13的在网格中寻找路径的问题,要找的是从s到g的路径。可以在水平方向和竖直方向上移动,一次只能一个方向。阴影部分表示禁止移动。
 图3-13 一个格搜索问题(a) 在图3-13的网格中,为从s到g的深度优先搜索的路径上各个扩展的节点标号。操作的顺序是上、左、右、下。假设有循环检查。
(b) 对于同样的网格,标号扩展的节点,是为了得到从s到g的最优优先搜索解。曼哈顿距离应当作为评价函数。曼哈顿距离是两点的x轴方向上的距离加上y轴方向上的距离。它对应的是在网格中沿着城市旅游。假设有多路径剪枝,那么发现的第一条路径是哪条?
(c) 对于同样的网格,标号扩展的节点,是为了得到从s到g的启发式深度优先搜索解。曼哈顿距离作为评价函数。假设存在路径循环检查,那么找到的路径是什么?
(d) 用A搜索方法标号节点的顺序,使用多路径剪枝,找到的路径是什么?
(e) 描述用动态规划算法如何解决相同问题。给出每个节点的dist值,描述找到的路径。
(f) 按照经验,哪种搜索方法最适合这个问题?
(g) 假设图在各个方向上延伸。也就是说,这个图没有界限,但是s、g和那些阴影障碍物都在相同的地方。用哪种方法会找不到路径?哪种是最好的方法?为什么?
3.4 问题是使用图搜索来设计视频演示。假设存在一个视频片段的数据库,还有它的时间长度和主题,如下:


75b33a75430bafeeccbfe2fdd371d755a1514ff4

这里Segs是必须要表示出来的一个列表,To_Cover也是必须表示的一系列主题。假设没有列表包含任何一个To_Cover。
节点的邻居通过To_Cover进行选择。对于每一个列表有邻居包含已经选择的主题。(这部分作用是要考虑这些相邻点的确切结构。)
例如,给出上述数据库,节点〈[welcome,robots],[]〉的邻居是〈[],[seg2]〉和〈[robots],[seg0]〉,假设选择了welcome。
因此,每一个弧线添加一段,但是可以包含一个或多个主题。假设弧线的成本等于片段添加的时间。
目标是设计一个描述,包含了MustCover所有的主题。起始节点是〈MustCover,[]〉,目标节点是〈[],Presentation〉。从起始节点到目标节点的花费值是这个描述的时间。因此,最优的描述是包含了MustCover所有的主题的最短的描述。
(a) 假设目标包含了所有主题[welcome,skiing,robots]。假设算法总是选择每个节点最左边的主题为其查找邻居。画出最低花费优先算法所有扩展的节点直到找到最终的解。这就会显示所有扩展的节点,到找到目标节点时,边界就会出现。
(b) 给定一个非平凡的启发函数h,它是实际花费的低估值。(注意对于所有的节点h(n)=0是平凡的启发函数。)它满足启发函数的单调性质吗?
3.5 画出两个不同的图,标出初始节点和目标节点,其中一个图表示向前搜索比向后搜索好,另外一个图表示向后搜索比向前搜索好。
3.6 实现迭代深化A算法。基于图3-10中的迭代深化搜索方法。
3.7 假设我们要找一个从初始节点到目标节点的路径,不是寻找最优路径,而是寻找花费值比最低花费多10%的路径。建议迭代深化A算法的替代方法可以得到解。为什么这有利于迭代深化A搜索?
3.8 如何修改深度优先分支界限搜索方法,来找到花费值比最低花费多10%的路径。这个算法与上面一题中的A算法的优化方案相比怎么样?
3.9 对于迭代深化搜索的分母b-1,当b≈1时,这就不是一个很好的近似。给出一个当b=1时更好的迭代深度复杂性的估计。这一章中其他算法的复杂度怎么算?提示:分支系数越接近1,迭代深化的分母越小。
3.10 双向搜索必须确保何时两个边界相交。为下面每个决定确定何时相交:
(a) 宽度优先搜索和深度界限深度优先搜索。
(b) 迭代深化搜索和深度界限深度优先搜索。
(c) A算法和深度界限深度界限搜索。
(d) A算法和A算法。
3.11 考虑前面3.7.6节中“A算法的最优性”处讨论的反例的算法,回答:
(a) 什么时候算法停止?(提示:到向前搜索找到目标,算法才会停止。)
(b) 应该保留什么样的数据结构?
(c) 完整的描述算法。
(d) 描述怎么样找到最优路径。
(e) 给出一个例子说明它扩展了比A少(多)的节点。
3.12 表述A算法的最优性,对于指定算法的种类,A是最优的。给出证明。
3.13 图3-11中深度优先分支界限搜索方法类似于深度界限搜索。因为它们都是如果花费低于界限值时,只找到一条解路径。对于一个特定的深度界限,如果没有解,它是怎样结合迭代深化搜索来增加深度界限的?如果没有解,在有限图中,算法会返回一个⊥。算法应当允许界限任意增加,然后当解存在时,返回最优(最低花费)的路径。

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

相关文章
大华股份携手阿里云计算 涉足智能家居
本文讲的是大华股份携手阿里云计算 涉足智能家居,“爸爸妈妈,快打开电视机”。以后小朋友这种急切的要求可能并不是为了看喜洋洋,而是着急看到电视另一头的爷爷奶奶。
1731 0
业界首个机密计算容器运行时—Inclavare Containers正式进入CNCF!
Inclavare Containers 通过云原生计算基金会(CNCF)TOC 投票正式成为 CNCF 官方沙箱项目。
151 0
边缘计算学习脑图
边缘学习小结
888 0
从大数据到快数据 数据智创未来——2019 CCF大数据与计算智能大赛正式开赛!
万物互联时代,数据驾驭和治理能力已成为企业的核心竞争力。作为中国最大的云计算服务提供商,阿里云始终致力于推动Big Data(大数据)向Fast Data(快数据)演进,培养强大的大数据分析开发者群体。
3411 0
端计算Walle:2235亿次运算,为了无法计算的端智能价值
本文知识点提炼: 1、端计算在移动设备上的应用探索 2、技术方案与核心模块设计 3、总结与展望
1427 0
应用留数定理计算实积分 $\dps{I(x)=\int_{-1}^1\frac{\rd t}{\sqrt{1-t^2}(t-x)}\ (|x|>1,x\in\bbR)}$ [华中师范大学2010年复变函数复试试题]
应用留数定理计算实积分 $\dps{I(x)=\int_{-1}^1\frac{\rd t}{\sqrt{1-t^2}(t-x)}\ (|x|>1,x\in\bbR)}$ [华中师范大学2010年复变函数复试试题]     解答: $$\beex \bea I(x)&=\int_{-1}^1 ...
1249 0
10059
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载