1
66450146 2016-05-09 03:09:43 +08:00
A* 需要一个两点距离的近似值,在网格图中这个近似值就是两点间的直线距离
如果你自己生成的图没有这种特征那是没法用的…… |
2
lecher 2016-05-09 03:27:05 +08:00 via Android 1
A*并不能保证最优解算出最短路径,它的评估函数是为了尽可能选取可能最优解优先进行深度搜索。设计 A*算法的目的是用错误率换时间和空间,不寻找最优解的情况下,尽快计算出一个可行解。
如果你一定要计算最短路径, A*算法并不适合。 既然你已经用矩阵表示无向图了,那么两点之间的距离是无法估算的,你能做的只有靠起点到目前节点的权值总和做估值函数,预设一个估算权值,即如果已经连接的节点权值越小就优秀扩展此节点进行搜索,超出估算权值越多优先级越低。恶劣情况就是退化成广度搜索,如果估值权值选得算法好,还是有可能剪枝成功实现快速出解的。 |
3
allan888 2016-05-09 04:47:15 +08:00 via iPhone
@lecher 如果是评估函数保证不大于实际距离,比如两点间的直线距离这种,那么是最优的,实际上用的时候,选的评估函数一般也是能让他找出最优的。
|
4
h4x3rotab 2016-05-09 08:23:05 +08:00 via iPhone
本身用矩阵表示图,除非这个图非常稠密,也就是几乎每两个点都有边连接,否则效率都很低,开始就建成临接表是最好的。
其次, A*在游戏寻路用的多,主要是因为游戏里不是简单的计算最短路,经常还要考虑比如物体的目标也是在移动、地图本身不同时刻也在变化的这类复杂问题,这个时候普通最短路就不适用了。否则,通常情况 Dijkstra 都比 A*要更好。 |
5
xiamx 2016-05-09 08:39:36 +08:00
A* does not perform well on uniformly randomly generated graph
|
7
PPTing OP |
8
PPTing OP @h4x3rotab 我生成的图节点比较多,并且节点之间的连接也比较多,我只需要在这个静态的图中求出最短路径就好了😁 Dijkstra 算法的效率低了一些,和 Floyd 应该是一样的吧,我已经实现了 Floyd 算法,现在需要实现一种启发式算法与其进行对比
|
9
66450146 2016-05-09 16:25:16 +08:00
@PPTing 在网格状的平面图里,两个点的直线距离更近有比较大可能意味着两个点的路径更短,尤其是对地图这样的场景来说非常适合。说玄乎点就是有正相关性
你想想,你生成的图有这样的特征吗?如果两个点的权值之和(或差)更大(或更小)的话,会意味着这两个点之间的距离很有可能更小吗? |
12
xuelang 61 天前
要是计算所有任意两点之间的最短路径,那就只能用 dijkstra 算法了。
我这里有一个演示 https://gallery.selfboot.cn/zh/algorithms/dijkstra ,可以参考 |