人工智能英语课件 u3（清华AI英语）

Best-FirstSearch

Unit

3Contents

NewWords

Abbreviations

PhrasesNotes参考译文NewWordsNewWordsNewWordsNewWordsPhrasesListeningtoTextA最佳优先搜索1.序言本文介绍了最佳优先搜索的一般形式。有许多特定的算法遵循最佳优先搜索的基本形式但却使用更复杂的评估函数。A*是最佳优先搜索的一个流行变体。虽然此处包含的信息与这些搜索算法相关，但本文没有专门讨论A*或其它变体。2.定义最佳优先搜索最常见形式是简单的启发式搜索算法。这里的“启发式”是指一般的问题解决规则或一组规则，它们不能保证得到最佳解决方案甚至不能得到任何解决方案，但可以作为解决问题的有用指南。最佳优先搜索是基于图的搜索算法，这意味着搜索空间可以表示为由路径连接的一系列节点。参考译文3.它如何工作名称“最佳优先”指首先探索具有最佳“得分”的节点的方法。用评估函数为每个候选节点分配分数。该算法含有两个列表，一个列表包含尚待探索的候选节点（OPEN），另一个列表包含已访问节点（CLOSED）。由于每个访问节点的所有未访问的后继节点都包括在OPEN列表中，因此该算法不限于仅探索最近访问的节点的后继节点。换句话说，该算法总是选择图中所有未访问节点中的最佳节点，而不是仅限于小的子集（例如直接邻居）。其他搜索策略（例如深度优先和广度优先）具有这样的限制。该策略的优点是，如果算法到达死角节点，它将继续尝试其它节点。参考译文4.算法最佳优先搜索最基本形式包括以下算法：第一步是使用单个节点（起始节点）定义OPEN列表。第二步是检查OPEN是否为空。如果它为空，则算法返回失败并退出。第三步是从OPEN中删除具有最高分数n的节点，并将其置于CLOSED中。第四步“扩展”节点n，其中扩展是n的后继节点的标识。然后，第五步检查每个后继节点，以查看它们中的一个是否是目标节点。如果任何后继者是目标节点，则算法返回成功和解决方案，该解决方案包括从目标向后追溯到起始节点的路径。否则，算法前进到第六步。对于每个后继节点，算法将评估函数f应用于它，然后检查节点是否已处于OPEN或CLOSED状态。如果该节点尚未进入任一列表，则会将其添加到OPEN。最后，第七步通过将算法回送到第二步来建立循环结构。如果算法在步骤5中返回成功或在步骤2中失败，则该循环中断。参考译文参考译文这里的算法用伪代码表示为：1)定义一个列表，OPEN，仅由单个节点（即起始节点）组成。2)如果列表为空，则返回失败。3)从列表中删除具有最佳分数的节点n（f为最小的节点），并将其移至列表CLOSED。4)展开节点n。5)如果n的任何后继者是目标节点，则返回成功和解决方案（通过跟踪从目标节点到开始节点的路径）。6)对于每个后继节点：A)将评估函数f应用于节点。B)如果节点未在任何列表中，则将其添加到OPEN。7)通过将算法回送到第二步来建立循环结构。Pearl为FOR循环添加了第三步，旨在防止重新扩展已经访问过的节点。上面省略了该步骤，因为对于所有最佳优先搜索算法这一步并不常见。5.评估函数用于确定节点得分的特定评估函数在上述算法中没有精确定义，因为所使用的实际函数由程序员的确定，并且可以根据搜索空间的特性而变化。虽然评估函数可以在很大程度上确定搜索的有效性和效率，但是为了理解搜索算法，我们不需要关心函数的特性。

参考译文6.应用最佳搜索及其更高级的变体已用于游戏和网络爬虫等应用程序。在网络爬虫程序中，每个网页都被视为一个节点，页面上的所有超链接都被视为未访问的后继节点。使用最佳优先搜索的网络爬虫程序通常使用评估函数，该函数根据其父页面的内容与搜索查询的相似程度为链接分配优先级。在游戏中，最佳优先搜索可以为游戏角色提供路径搜索算法。例如，对手可以使用它来查找游戏世界中玩家的位置。有些游戏把地形分成可进入或不可进入的区块。在这种情况下，搜索算法将每个区块视为节点，其中