A* 如何搜索图表？

Question

A* 搜索将从节点 S 开始并继续到节点 G。在节点 S，打开列表将包含 A 和 B，其值分别为 7 和 6。创建 table 显示作为 A* 算法访问的每个节点的开放列表进步。

任何人都可以向我解释 A* 将如何搜索这个。

open list = [S]; closed list = []
open list = [A,B]; closed list = [S]
whats next?

Answer 1

A* 是一种最佳优先算法，这意味着它通过扩展最有前途的节点来探索图指定的规则。在这种情况下，规则是最有前途的节点是具有 最小 f 值 的节点，其中 f(n) = g(n) + h( n)，即已经走过的总和（g 值）加上我们的启发式 "promise" 我们的剩余路径（h 值）是最小的。

因此，让我按顺序写开列表，因为通常A*的开列表是优先队列：

it 0: open list = [S]; closed list = []

it 1: in this iteration we will have closed list = [S] and a PQ of open nodes with,
open list = 
| (B, 6) | (g = 3 + h = 3)
| (A, 7) | (g = 2 + h = 5)

之后，B是最有希望的路径（6 < 7）所以这个节点将被放入封闭列表，

it 2: closed list = [S,B];
open list = 
| (A, 7) | (g = 2 + h = 5)
| (D, 10) | (g = 6 + h = 4)
| (C, 11) | (g = 8 + h = 3)

算法再次选择扩展具有较低 f 值 (A) 的节点，

it 3: closed list = [S,B,A];
open list = 
| (C, 9) | (g = 6 + h = 3) <-- new path found with lower g-value, we update the node
| (D, 10) | (g = 6 + h = 4)

在更新到成本低于（S->B->C）的 C（S->A->C）的路径成本后，该节点成为 A* 最有希望的节点，

it 4: closed list = [S,B,A,C];
open list =
| (F, 9) | (g = 8 + h = 1)
| (D, 10) | (g = 6 + h = 4)
| (E, 13) | (g = 10 + h = 3)

F现在最有前途，扩充了，

it 5: closed list = [S,B,A,C,F];
open list = 
| (G, 9) | (g = 9 + h = 0)
| (D, 10) | (g = 6 + h = 4)
| (E, 13) | (g = 10 + h = 3)

我们已经将目标节点添加到开放列表中，但这并不意味着算法完成，因为可能（不在这个问题中）还有其他路径比已经找到的短（S->A->C->F->G）。 算法将在扩展目标节点时结束。在下一次迭代中，我们再次扩展最有希望的节点。

it 6: we expand the goal node G.

算法完成，returns 路径 S->A->C->F->G，成本为 9。

请注意你的启发式函数是一致的，这意味着一旦一个节点被A*搜索算法扩展（或放入封闭列表），成本达到它的最低可能（假设没有负成本周期）。这也意味着 启发式是可接受的 并且 A* 保证找到的解决方案是从 S 到 G 的最短可能路径 。更重要的是，当A*使用一致的启发式算法时，它是一个最优算法，即没有其他算法在具有相同启发式信息的情况下可以扩展更少的节点并仍然保证找到最短路径。

A* 如何搜索图表？

How would A* search a graph?

algorithm

heuristics

a-star