A*寻路是一种广度优先搜索？ 第1页

假如说待遍历的图是一棵二叉树的话，那么：

• dfs是先序遍历
• bfs是层次遍历
• A*的遍历有点特别。它是给所有节点赋予权重（就是h(n)=f(n)+g(n)）。从根节点开始，扩展所有子节点，加入到优先队列中。然后把根节点抛掉，在优先队列中找权重最小（或最大）的节点将其扩展，把它所有子节点加入优先队列中并抛弃该节点。以此类推。

因此A*的遍历模式跟dfs与bfs都不太一样。与bfs的相同点在于每次都扩展某个节点的所有子节点。不同的地方在于bfs扩展顺序固定且与权重无关，而A*的扩展顺序由权重决定。

随便举个例子。（下图是分支限界法解01背包问题的图，不是A*，你就把b看作是A*中的代价函数h(n)=f(n)+g(n)好了。这个图就做个示意。）

每种方法遍历的次序分别为：

• dfs：ABDFGHIECJLNOPQMK
• bfs：ABCDEJKFGLMHINOPQ
• A*：ABCDEFGHIJKLMNOPQ

所以用到的数据结构也不一样

• dfs->栈
• bfs->队列
• A*->优先队列

此外，题中“A*接近最优解”的说法不太好。A*一定是最优解。不是最优解的叫A。