有关A* 寻路算法。 看了这个算法 大致都明白。就是有点不大清楚。

Question

就是说A* 寻路 中，每一点 A到下一点B 都有一个G值（表示步数） 当发现 A到B的G值，比目前B的G还小。那么更新B的G值。

假设有最优路径永远不经过B，那么B的G值是多少。

问题就出来了 A*寻路算法 是不是要遍历所有可能的路径，最终确定所有点的G值（假设没有路障）；最后根据父节点 依次回来？

Answer 1

1. B的G值是指从起点A开始，到达该点的最短距离，和B在不在最短路径上没有关系。

2. 不是遍历所有路径，而是所有点。对于m*n的矩阵， 遍历所有点的复杂度是m*n（多项式复杂度），而遍历所有路径的复杂度是4的(m*n)次幂(每个点都有4个可能的方向)。从幂指数复杂度降低到多项式复杂度，这就是A*算法的意义所在。

3. 最优路径是要从终点一步步倒退回来。比如终点的G值是k，那么最多需要4*k次查找，依然是多项式复杂度。但多数问题(对于纯算法题来说)只是需要知道到达终点的步骤，很少要你找出固定路径的。