题目

有关A* 寻路算法.看了这个算法 大致都明白.就是有点不大清楚.
就是说A* 寻路 中,每一点 A到下一点B 都有一个G值（表示步数） 当发现 A到B的G值,比目前B的G还小.那么更新B的G值.
假设有最优路径永远不经过B,那么B的G值是多少.
问题就出来了 A*寻路算法 是不是要遍历所有可能的路径,最终确定所有点的G值（假设没有路障）；最后根据父节点 依次回来?

提问时间：2020-12-08

答案

1.B的G值是指从起点A开始,到达该点的最短距离,和B在不在最短路径上没有关系.
2.不是遍历所有路径,而是所有点.对于m*n的矩阵,遍历所有点的复杂度是m*n（多项式复杂度）,而遍历所有路径的复杂度是4的(m*n)次幂(每个点都有4个可能的方向).从幂指数复杂度降低到多项式复杂度,这就是A*算法的意义所在.
3.最优路径是要从终点一步步倒退回来.比如终点的G值是k,那么最多需要4*k次查找,依然是多项式复杂度.但多数问题(对于纯算法题来说)只是需要知道到达终点的步骤,很少要你找出固定路径的.