V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
PPTing
V2EX  ›  编程

关于启发式算法 A*

  •  
  •   PPTing · 2016-05-09 01:58:35 +08:00 · 4269 次点击
    这是一个创建于 3124 天前的主题,其中的信息可能已经有所发展或是发生改变。
    最近写毕业设计遇到了一点问题,熬了好几天都未能解决。
    我随机生成了一个有 N 个节点的无向图(用矩阵表示),节点与节点之间并不是完全连通,节点之间权值为正,用 Floyd 算法计算出了任意两个节点之间的最短路径。
    现在需要写一个启发式算法计算任意两点之间的最短路径,我查了一些资料,发现很多关于 A* 算法的例子都是用来解决网格状的图,如果我想用 A* 算法计算任意两点之间的最短路径,难道我还得把用矩阵表示的无向图转化为网格状的图再进行计算吗?
    还是说我对 A* 算法还没有理解透彻,希望各位能够指点迷津,或者发一些例子文章博客给我看一下,谢谢~
    12 条回复    2024-10-22 20:48:21 +08:00
    66450146
        1
    66450146  
       2016-05-09 03:09:43 +08:00
    A* 需要一个两点距离的近似值,在网格图中这个近似值就是两点间的直线距离

    如果你自己生成的图没有这种特征那是没法用的……
    lecher
        2
    lecher  
       2016-05-09 03:27:05 +08:00 via Android   ❤️ 1
    A*并不能保证最优解算出最短路径,它的评估函数是为了尽可能选取可能最优解优先进行深度搜索。设计 A*算法的目的是用错误率换时间和空间,不寻找最优解的情况下,尽快计算出一个可行解。
    如果你一定要计算最短路径, A*算法并不适合。

    既然你已经用矩阵表示无向图了,那么两点之间的距离是无法估算的,你能做的只有靠起点到目前节点的权值总和做估值函数,预设一个估算权值,即如果已经连接的节点权值越小就优秀扩展此节点进行搜索,超出估算权值越多优先级越低。恶劣情况就是退化成广度搜索,如果估值权值选得算法好,还是有可能剪枝成功实现快速出解的。
    allan888
        3
    allan888  
       2016-05-09 04:47:15 +08:00 via iPhone
    @lecher 如果是评估函数保证不大于实际距离,比如两点间的直线距离这种,那么是最优的,实际上用的时候,选的评估函数一般也是能让他找出最优的。
    h4x3rotab
        4
    h4x3rotab  
       2016-05-09 08:23:05 +08:00 via iPhone
    本身用矩阵表示图,除非这个图非常稠密,也就是几乎每两个点都有边连接,否则效率都很低,开始就建成临接表是最好的。

    其次, A*在游戏寻路用的多,主要是因为游戏里不是简单的计算最短路,经常还要考虑比如物体的目标也是在移动、地图本身不同时刻也在变化的这类复杂问题,这个时候普通最短路就不适用了。否则,通常情况 Dijkstra 都比 A*要更好。
    xiamx
        5
    xiamx  
       2016-05-09 08:39:36 +08:00
    A* does not perform well on uniformly randomly generated graph
    PPTing
        6
    PPTing  
    OP
       2016-05-09 09:37:23 +08:00 via Android
    @66450146 两个节点的权值用来代表两点直接的距离不可以吗?
    PPTing
        7
    PPTing  
    OP
       2016-05-09 09:50:41 +08:00 via Android
    @lecher 嗯嗯,谢谢呀~
    我不用一定要求最短路径,只要能够求出一个接近于最短路径的可行解,并且时间效率高于 Floyd 算法就可以,
    或许我应该考虑换个启发式算法?
    PPTing
        8
    PPTing  
    OP
       2016-05-09 09:56:20 +08:00 via Android
    @h4x3rotab 我生成的图节点比较多,并且节点之间的连接也比较多,我只需要在这个静态的图中求出最短路径就好了😁 Dijkstra 算法的效率低了一些,和 Floyd 应该是一样的吧,我已经实现了 Floyd 算法,现在需要实现一种启发式算法与其进行对比
    66450146
        9
    66450146  
       2016-05-09 16:25:16 +08:00
    @PPTing 在网格状的平面图里,两个点的直线距离更近有比较大可能意味着两个点的路径更短,尤其是对地图这样的场景来说非常适合。说玄乎点就是有正相关性

    你想想,你生成的图有这样的特征吗?如果两个点的权值之和(或差)更大(或更小)的话,会意味着这两个点之间的距离很有可能更小吗?
    PPTing
        10
    PPTing  
    OP
       2016-05-09 16:33:03 +08:00 via Android
    @66450146 有的,我生成的图从 A 到 B 的距离可能大于 A-C-B 的
    h4x3rotab
        11
    h4x3rotab  
       2016-05-10 00:57:56 +08:00 via iPhone
    @PPTing 节点多才更应该用 dijkstra 或者 spfa 吧
    xuelang
        12
    xuelang  
       35 天前
    要是计算所有任意两点之间的最短路径,那就只能用 dijkstra 算法了。

    我这里有一个演示 https://gallery.selfboot.cn/zh/algorithms/dijkstra ,可以参考
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4191 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 05:23 · PVG 13:23 · LAX 21:23 · JFK 00:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.