这是一个创建于 3155 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近写毕业设计遇到了一点问题，熬了好几天都未能解决。
我随机生成了一个有 N 个节点的无向图(用矩阵表示)，节点与节点之间并不是完全连通，节点之间权值为正，用 Floyd 算法计算出了任意两个节点之间的最短路径。
现在需要写一个启发式算法计算任意两点之间的最短路径，我查了一些资料，发现很多关于 A* 算法的例子都是用来解决网格状的图，如果我想用 A* 算法计算任意两点之间的最短路径，难道我还得把用矩阵表示的无向图转化为网格状的图再进行计算吗？
还是说我对 A* 算法还没有理解透彻，希望各位能够指点迷津，或者发一些例子文章博客给我看一下，谢谢～
我随机生成了一个有 N 个节点的无向图(用矩阵表示)，节点与节点之间并不是完全连通，节点之间权值为正，用 Floyd 算法计算出了任意两个节点之间的最短路径。
现在需要写一个启发式算法计算任意两点之间的最短路径，我查了一些资料，发现很多关于 A* 算法的例子都是用来解决网格状的图，如果我想用 A* 算法计算任意两点之间的最短路径，难道我还得把用矩阵表示的无向图转化为网格状的图再进行计算吗？
还是说我对 A* 算法还没有理解透彻，希望各位能够指点迷津，或者发一些例子文章博客给我看一下，谢谢～
 |
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 66 天前
要是计算所有任意两点之间的最短路径，那就只能用 dijkstra 算法了。
我这里有一个演示 https://gallery.selfboot.cn/zh/algorithms/dijkstra ，可以参考 |
Select Language