预计阅读本页时间：-
A*搜索
广度优先搜索能够找到一个最优解（如果存在），但是可能需要访问大量的节点，因为我们可以看到，它并没有尝试对候选走法进行排序。相反，深度优先搜索却是尽可能多地向前探测路径，不过，深度优先搜索的搜索深度必须得到限制，要不然它很有可能会在没有任何结果的路径上花费大量的时间。A*搜索在搜索时能够利用启发式信息，智能地调整搜索策略。
如图7-10所示，A*搜索是一种迭代的有序搜索，它维护一个棋面状态的开放集合。在每次迭代时，A*搜索使用一个评价函数f*(n)评价开放集合中的所有棋面状态，选择最小的棋面状态。我们定义f*(n)=g*(n)+h*(n)：
g*(n)估算从初始状态到状态n的最短走法序列。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
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*搜索得到的是开销最小的解。
