有关A* 寻路算法.看了这个算法 大致都明白.就是有点不大清楚.
题目
有关A* 寻路算法.看了这个算法 大致都明白.就是有点不大清楚.
就是说A* 寻路 中,每一点 A到下一点B 都有一个G值(表示步数) 当发现 A到B的G值,比目前B的G还小.那么更新B的G值.
假设有最优路径永远不经过B,那么B的G值是多少.
问题就出来了 A*寻路算法 是不是要遍历所有可能的路径,最终确定所有点的G值(假设没有路障);最后根据父节点 依次回来?
答案
1.B的G值是指从起点A开始,到达该点的最短距离,和B在不在最短路径上没有关系.
2.不是遍历所有路径,而是所有点.对于m*n的矩阵,遍历所有点的复杂度是m*n(多项式复杂度),而遍历所有路径的复杂度是4的(m*n)次幂(每个点都有4个可能的方向).从幂指数复杂度降低到多项式复杂度,这就是A*算法的意义所在.
3.最优路径是要从终点一步步倒退回来.比如终点的G值是k,那么最多需要4*k次查找,依然是多项式复杂度.但多数问题(对于纯算法题来说)只是需要知道到达终点的步骤,很少要你找出固定路径的.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点
- 若x^(1/2)-x(-1/2)=3.求[x^(3/2)-x(-3/2)-3]/[x^2+x^(-2)-2]的值
- clear的副词形式
- 期终考试,小明的语文成绩和数学成绩加起来是197分,数学成绩和英语成绩加起来是199分,语文成绩和英语成绩加起来是196分.小明的各科成绩分别是多少分?
- 图书角科技书比故事书多四分之一,科技书比故事书多4本,图书角有故事书多少本
- 已知x=1是一元二次方程ax的平方+bx-10=0的一个解,且a≠b,求a平方-b平方/2a-2b的值
- Fe,Cu,Ag,Zn.Au的物理性质
- there is____waiter service in a pub.
- whose has a birthday in july
- 如图,已知边长为16的正方形abcd,e为ad的中点,p为ce的中点,求三角形bdp的面积
- 中招语文阅读理解都考什么体裁的文章