我将尝试重写之前的答案，并详细说明为什么它是最佳的。
A*算法直接取自维基百科 http://en.wikipedia.org/wiki/A*_search_algorithm is
function A*(start,goal)
closedset := the empty set // The set of nodes already evaluated.
openset := set containing the initial node // The set of tentative nodes to be evaluated.
came_from := the empty map // The map of navigated nodes.
g_score[start] := 0 // Distance from start along optimal path.
h_score[start] := heuristic_estimate_of_distance(start, goal)
f_score[start] := h_score[start] // Estimated total distance from start to goal through y.
while openset is not empty
x := the node in openset having the lowest f_score[] value
if x = goal
return reconstruct_path(came_from, came_from[goal])
remove x from openset
add x to closedset
foreach y in neighbor_nodes(x)
if y in closedset
continue
tentative_g_score := g_score[x] + dist_between(x,y)
if y not in openset
add y to openset
tentative_is_better := true
elseif tentative_g_score < g_score[y]
tentative_is_better := true
else
tentative_is_better := false
if tentative_is_better = true
came_from[y] := x
g_score[y] := tentative_g_score
h_score[y] := heuristic_estimate_of_distance(y, goal)
f_score[y] := g_score[y] + h_score[y]
return failure
function reconstruct_path(came_from, current_node)
if came_from[current_node] is set
p = reconstruct_path(came_from, came_from[current_node])
return (p + current_node)
else
return current_node
让我在这里填写所有详细信息。
heuristic_estimate_of_distance is the function Σ d(xi) where d(.) is the Manhattan distance of each square xi from its goal state.
所以设置
1 2 3
4 7 6
8 5
会有一个heuristic_estimate_of_distance1+2+1=4，因为 8,5 中的每一个都距其目标位置 1，d(.)=1，而 7 距其目标状态 2，d(7)=2。
A* 搜索的节点集被定义为起始位置，后跟所有可能的合法位置。这就是起始位置x如上所述：
x =
1 2 3
4 7 6
8 5
那么函数neighbor_nodes(x)产生 2 种可能的合法动作：
1 2 3
4 7
8 5 6
or
1 2 3
4 7 6
8 5
功能dist_between(x,y)定义为从状态转换所发生的平方移动数x to y。出于算法的目的，这在 A* 中通常等于 1。
closedset and openset两者都特定于 A* 算法，并且可以使用标准数据结构（我相信优先级队列）来实现。came_from是使用的数据结构
使用函数重建找到的解决方案reconstruct_path谁的详细信息可以在维基百科上找到。如果您不想记住解决方案，则无需实施此解决方案。
最后，我将讨论最优性问题。考虑 A* 维基百科文章的摘录：
“如果启发式函数 h 是可接受的，这意味着它永远不会高估达到目标的实际最小成本，那么如果我们不使用闭集，则 A* 本身就是可接受的（或最优的）。如果使用闭集，则h 也必须是单调的（或一致的），A* 才能达到最优。这意味着对于任何一对相邻节点 x 和 y，其中 d(x,y) 表示它们之间的边的长度，我们必须有：
h(x)
因此，足以表明我们的启发式是可接受的且单调的。对于前者（可接受性），请注意，给定任何配置，我们的启发式（所有距离的总和）估计每个方格不仅受到合法移动的约束，并且可以自由地朝其目标位置移动，这显然是一个乐观的估计，因此我们的启发式是可以接受的（或者它永远不会高估，因为达到目标位置总是需要at least与启发式估计一样多的动作。）
单调性要求用文字表述就是：
“任何节点的启发式成本（到目标状态的估计距离）必须小于或等于转换到任何相邻节点的成本加上该节点的启发式成本。”
它主要是为了防止出现负循环的可能性，即转换到不相关的节点可能会比实际进行转换的成本减少到目标节点的距离，这表明启发式很差。
在我们的例子中，显示单调性非常简单。根据我们对 d 的定义，任何相邻节点 x,y 都具有 d(x,y)=1。因此我们需要展示
h(x)
这相当于
h(x) - h(y)
这相当于
Σ d(xi) - Σ d(yi) <= 1
这相当于
Σ d(xi) - d(yi) <= 1
根据我们的定义我们知道neighbor_nodes(x)两个邻居节点 x,y 最多可以有一个方格的位置不同，这意味着在我们的总和中
d(xi) - d(yi) = 0
对于除 1 之外的所有 i 值。不失一般性地说，i=k 是这样。此外，我们知道，对于 i=k，节点最多移动了一处，因此它到
目标状态最多只能比前一个状态多 1，因此：
Σ d(xi) - d(yi) = d(xk) - d(yk) <= 1
表现出单调性。这显示了需要显示的内容，从而证明该算法将是最优的（以大 O 表示法或渐近方式）。
请注意，我已经在大 O 表示法方面展示了最优性，但在调整启发式方面仍然有很大的发挥空间。您可以对其添加额外的扭曲，以便更接近地估计到目标状态的实际距离，however你必须做sure启发式总是低估否则你就会失去最优性！
稍后编辑许多卫星
后来（很久）再次阅读这篇文章，我意识到我编写它的方式有点混淆了该算法的最优性的含义。
我试图在这里理解最优性有两个不同的含义：
1) 该算法产生最优解，即给定客观标准的最佳可能解。
2) 该算法使用相同的启发式扩展了所有可能算法的最少状态节点数。
理解为什么需要启发式的可接纳性和单调性来获得 1) 的最简单方法是将 A* 视为 Dijkstra 最短路径算法在图上的应用，其中边权重由迄今为止移动的节点距离加上启发式给出距离。如果没有这两个属性，我们就会在图中出现负边，从而可能出现负循环，并且 Dijkstra 的最短路径算法将不再返回正确答案！ （构建一个简单的例子来说服自己。）
2）实际上很难理解。要充分理解这句话的意思，这个说法上有很多量词，比如在谈论其他算法时，一个指的是similar算法如 A* 扩展节点并在没有先验信息（启发式除外）的情况下进行搜索。显然，人们可以构造一个简单的反例，否则，例如神谕或精灵会在每一步告诉你答案。为了深入理解这一陈述，我强烈建议阅读历史部分的最后一段维基百科 https://en.wikipedia.org/wiki/A*_search_algorithm#History以及查看该仔细陈述的句子中的所有引文和脚注。
我希望这能消除潜在读者中剩余的困惑。
