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

PopularSearchAlgorithms

Unit

2Contents

NewWords

Abbreviations

PhrasesNotes参考译文NewWordsNewWordsNewWordsNewWordsNewWordsPhrasesPhrasesPhrasesAbbreviationsListeningtoTextA热门搜索算法搜索是人工智能中解决问题的通用技术。有一些单人游戏，如智力拼图、数独游戏、填字游戏等。搜索算法可以帮助你搜索此类游戏中的特定位置。1.搜索术语问题空间——这是搜索发生的环境。（一组状态和一组运算符来改变这些状态。）问题实例——它是初始状态+目标状态。问题空间图——它代表问题状态。状态由节点显示，运算符由边显示。问题的深度——从初始状态到目标状态的最短路径或最短操作符序列的长度。空间复杂度——存储在内存中的最大节点数。时间复杂度——创建的最大节点数。可容许性——总是找到最优解的算法的属性。分支因子——问题空间图中的平均子节点数。深度——从初始状态到目标状态的最短路径的长度。参考译文1.蛮力搜索策略它们很简单，因为它们不需要任何特定领域的知识。在很少的可能状态下，这些策略颇为适用。要求：•状态描述•一组有效的运算符•初始状态•目标状态描述2.1广度优先搜索它从根节点开始，首先探索相邻节点并向下一级邻居移动。它一次生成一个树，直到找到解决方案。它可以使用FIFO队列数据结构实现。该方法提供了解决问题的最短路径。如果分支因子（给定节点的子节点的平均数量）=b且深度=d，则该级别的节点数是bd。参考译文在最坏情况下创建的节点总数是b+b2+b3+...+bd。缺点：由于保存了每个级别的节点以创建下一个节点，因此会消耗大量内存空间。存储节点的空间要求是指数级的。其复杂性取决于节点数量。它可以检查重复的节点。2.2深度优先搜索它用LIFO堆栈数据结构以递归方式实现。它创建与广度优先方法相同的节点集，只是顺序不同。由于单个路径上的节点存储在从根节点到叶节点的每次迭代中，因此存储节点的空间要求是线性的。当分支因子带深度为m时，存储空间为bm。缺点：此算法可能无法终止并在一条路径上无限循环。解决这一问题的方法是选择截止深度。如果理想截止值为d且当选择的截止值小于d，则该算法可能失败。当选择的截止值大于d，则会增加执行时间。其复杂性取决于路径的数量。它无法检查重复的节点。参考译文参考译文2.3双向搜索它从初始状态向前搜索，从目标状态向后搜索，直到两者相遇以识别共同状态。从初始状态开始的路径与来自目标状态的反向路径相关联。每次搜索仅完成总路径的一半。2.4等代价搜索排序是通过增加节点路径的代价来完成的。它总是扩展最低代价节点。如果每个转换具有相同的代价，则与广度优先搜索相同。它以代价增加的顺序探索路径。缺点：可能有多个长路径。等代价搜索必须全部探索。2.5迭代深化深度优先搜索它执行深度优先搜索到级别1，重新开始，执行完整的深度优先搜索到级别2，并继续以这种方式直到找到解决方案。直到生成所有较低节点，它才会创建一个节点。它只保存节点堆栈。算法在深度d处找到解时结束。在深度d处创建的节点的数量是bd，且在深度d-1处是bd-1。参考译文

参考译文3.知情（启发式）搜索策略为了解决具有大量可能状态的大问题，需要添加针对问题的知识以提高搜索算法的效率。3.1启发式评估函数其计算两个状态之间最佳路径的代价。滑动拼图游戏的启发式函数由计算移动滑块的数量来完成，每个滑块都来自其目标状态，还要加上全部滑块的移动数。3.2纯启发式搜索它按照启发式值的顺序扩展节点。它创建了两个列表，一个是已经展开的节点的闭合列表，另一个是已创建但未展开的节点的开放列表。在每次迭代中，扩展具有最小启发式值的节点，创建其所有子节点并将其放置在闭合列表中。然后，将启发式函数应用于子节点，并根据它们的启发式值将它们放置在打开列表中。保存较短的路径，并处理较长的路径。参考译文3.3A*搜索它是最佳优先搜索的最知名形式。它避免扩展那些很昂贵的路径，而是首先扩展最有希望的路径。f(n)=g(n)+h(n)，其中•g(n)到达节点的成本（到目前为止）•h(n)从节点到目标的估计成本•f(n)估计从n到目标的路径总成本。它通过增加f(n)使用优先级队列来实现。3.4贪婪最佳优先搜索它扩展估计最接近目标的节点。它基于f(n)=h(n)扩展节点。它使用优先级队列实现。缺点：它可能卡在循环中。这不是最佳的。参考译文4.本地搜索算法它们从一个预期的解决方案开始，然后转移到邻近的解决方案。即使它们在结束之前的任何时间被中断，它们也可以返回一个有效的解决方案。4.1爬山搜索它是一种迭代算法，从问题的任意解决方案开始，并尝试通过逐步更改解决方案的单个元素来找到更好的解决方案。如果更改产生更好的解决方案，则将新增更改视为新解决方案。重复该过程直到没有进一步的改进。函数Hill-Climbing(problem)返回一个局部最大值的状态。缺点：该算法既不完整也不优化。参考译文4.2局部集束搜索在该算法中，它在任何给定时间保持k个状态。一开始，这些状态是随机生成的。这些k个状态的后继者是在目标函数的帮助下计算出来的。如果这些后继者中的任何一个是目标函数的最大值，则算法停止。否则，（初始k状态和k个状态的后继者=2k）状态被放置在池中。然后按数字对池进行排序。选择最高的k个状态作为新的初始状态。此过程持续进行直到达到最大值。函数BeamSearch(problem,k)返回一个解状态。参考译文参考译文4.3模拟退火退火是加热和冷却金属而改变其内部结构以改变其物理性质的过程。当金属冷却时，就形成了其新结构，而且金属保留其新获得的性能。在模拟退火过程中，温度一直可变。我们最初将温度设置为高，然后在算法进行时让它慢慢“冷却”。当温度高时，算法允许接受具有高频率的更差的解决方案。开始•初始化k=0;L=整数变量;•从i→j，搜索性能差异Δ。•如果Δ<=0，则接受；否则，如果exp(-Δ/T(k))>random(0,1)则接受；•对L(k)步骤重复步骤1和2。•k=k+1;重复步骤1到4，