同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库
广度优先搜索能够找到一个最优解(如果存在),但是可能需要访问大量的节点,因为我们可以看到,它并没有尝试对候选走法进行排序。相反,深度优先搜索却是尽可能多地向前探测路径,不过,深度优先搜索的搜索深度必须得到限制,要不然它很有可能会在没有任何结果的路径上花费大量的时间。A*搜索在搜索时能够利用启发式信息,智能地调整搜索策略。
如图7-10所示,A*搜索是一种迭代的有序搜索,它维护一个棋面状态的开放集合。在每次迭代时,A*搜索使用一个评价函数f*(n)评价开放集合中的所有棋面状态,选择最小的棋面状态。我们定义f*(n)=g*(n)+h*(n):
g*(n)估算从初始状态到状态n的最短走法序列。
h*(n)估算从状态n到目标状态的最短走法序列。
f*(n)估算从初始状态开始,经过状态n,到达目标状态的最短走法序列。
星号*表示使用了启发式信息(自从1968年开发出此算法后,这个记法被广泛接受),因此f*(n),g*(n)以及h*(n)是对实际开销f(n),g(n)和h(n)的估算,这些实际开销只能在得到解之后才能够知道。简而言之,f*(n)越低,表示状态n越接近目标状态。
f*(n)最关键的部分是启发式的计算h*(n),因为g*(n)能够在搜索的过程中,通过记录状态n的深度计算出来[1]。如果h*(n)不能够准确地区分开有继续搜索价值的状态和没有价值的状态,那么A*搜索不会表现得比上述任何盲目搜索要好。如果能够准确地估算h*(n),那么使用f*(n)就能够得到一个开销最小的解。
输入
算法从一个初始棋面状态开始,寻找一个目标状态。算法假设(a)在给定棋面状态下可以尝试所有的可行走法,以及(b)计算棋面状态n的评估函数f*(n)。
输出
返回一个走法的序列,表示从初始状态到目标状态的近似开销最小的路径(或者只是输出是否存在一个解)。
假设
如果估算得到的结果和实际结果相差不远,那么A*搜索得到的是开销最小的解。
请支持我们,让我们可以支付服务器费用。
使用微信支付打赏