本节书摘来自华章计算机《人工智能：计算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　问题是使用图搜索来设计视频演示。假设存在一个视频片段的数据库，还有它的时间长度和主题，如下：

这里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中深度优先分支界限搜索方法类似于深度界限搜索。因为它们都是如果花费低于界限值时，只找到一条解路径。对于一个特定的深度界限，如果没有解，它是怎样结合迭代深化搜索来增加深度界限的？如果没有解，在有限图中，算法会返回一个⊥。算法应当允许界限任意增加，然后当解存在时，返回最优（最低花费）的路径。