关于启发式算法 A*

This topic created in 3718 days ago, the information mentioned may be changed or developed.

最近写毕业设计遇到了一点问题，熬了好几天都未能解决。
我随机生成了一个有 N 个节点的无向图(用矩阵表示)，节点与节点之间并不是完全连通，节点之间权值为正，用 Floyd 算法计算出了任意两个节点之间的最短路径。
现在需要写一个启发式算法计算任意两点之间的最短路径，我查了一些资料，发现很多关于 A* 算法的例子都是用来解决网格状的图，如果我想用 A* 算法计算任意两点之间的最短路径，难道我还得把用矩阵表示的无向图转化为网格状的图再进行计算吗？
还是说我对 A* 算法还没有理解透彻，希望各位能够指点迷津，或者发一些例子文章博客给我看一下，谢谢～

算法

节点

路径

计算

12 replies • 2024-10-22 20:48:21 +08:00

66450146

May 9, 2016

A* 需要一个两点距离的近似值，在网格图中这个近似值就是两点间的直线距离

如果你自己生成的图没有这种特征那是没法用的……

lecher

May 9, 2016 via Android

A*并不能保证最优解算出最短路径，它的评估函数是为了尽可能选取可能最优解优先进行深度搜索。设计 A*算法的目的是用错误率换时间和空间，不寻找最优解的情况下，尽快计算出一个可行解。
如果你一定要计算最短路径， A*算法并不适合。

既然你已经用矩阵表示无向图了，那么两点之间的距离是无法估算的，你能做的只有靠起点到目前节点的权值总和做估值函数，预设一个估算权值，即如果已经连接的节点权值越小就优秀扩展此节点进行搜索，超出估算权值越多优先级越低。恶劣情况就是退化成广度搜索，如果估值权值选得算法好，还是有可能剪枝成功实现快速出解的。

allan888

May 9, 2016 via iPhone

@lecher 如果是评估函数保证不大于实际距离，比如两点间的直线距离这种，那么是最优的，实际上用的时候，选的评估函数一般也是能让他找出最优的。

h4x3rotab

May 9, 2016 via iPhone

本身用矩阵表示图，除非这个图非常稠密，也就是几乎每两个点都有边连接，否则效率都很低，开始就建成临接表是最好的。

其次， A*在游戏寻路用的多，主要是因为游戏里不是简单的计算最短路，经常还要考虑比如物体的目标也是在移动、地图本身不同时刻也在变化的这类复杂问题，这个时候普通最短路就不适用了。否则，通常情况 Dijkstra 都比 A*要更好。

xiamx

May 9, 2016

A* does not perform well on uniformly randomly generated graph

PPTing

May 9, 2016 via Android

@66450146 两个节点的权值用来代表两点直接的距离不可以吗？

PPTing

May 9, 2016 via Android

@lecher 嗯嗯，谢谢呀～
我不用一定要求最短路径，只要能够求出一个接近于最短路径的可行解，并且时间效率高于 Floyd 算法就可以，
或许我应该考虑换个启发式算法？

PPTing

May 9, 2016 via Android

@h4x3rotab 我生成的图节点比较多，并且节点之间的连接也比较多，我只需要在这个静态的图中求出最短路径就好了😁 Dijkstra 算法的效率低了一些，和 Floyd 应该是一样的吧，我已经实现了 Floyd 算法，现在需要实现一种启发式算法与其进行对比

66450146

May 9, 2016

@PPTing 在网格状的平面图里，两个点的直线距离更近有比较大可能意味着两个点的路径更短，尤其是对地图这样的场景来说非常适合。说玄乎点就是有正相关性

你想想，你生成的图有这样的特征吗？如果两个点的权值之和（或差）更大（或更小）的话，会意味着这两个点之间的距离很有可能更小吗？

PPTing

May 9, 2016 via Android

@66450146 有的，我生成的图从 A 到 B 的距离可能大于 A-C-B 的

h4x3rotab

May 10, 2016 via iPhone

@PPTing 节点多才更应该用 dijkstra 或者 spfa 吧

xuelang

Oct 22, 2024

要是计算所有任意两点之间的最短路径，那就只能用 dijkstra 算法了。

我这里有一个演示 https://gallery.selfboot.cn/zh/algorithms/dijkstra ，可以参考