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

各位大牛,最近做图的最优路径相关,有没有针对多目标约束的相关算法?举个例子,就是交通规划中,时间<1 小时,并且油耗<1 升。找了一圈一般图论中的算的都是最优路径,不太满足需求。有相关的论文也行

  •  
  •   microxiaoxiao · 2022-03-29 21:56:40 +08:00 · 1459 次点击
    这是一个创建于 730 天前的主题,其中的信息可能已经有所发展或是发生改变。
    9 条回复    2022-03-30 19:48:39 +08:00
    enki0423
        1
    enki0423  
       2022-03-29 22:03:41 +08:00 via iPhone
    网络流?
    microxiaoxiao
        2
    microxiaoxiao  
    OP
       2022-03-29 22:10:41 +08:00
    对,现在是单权可以通过一般的图算法狄克斯特拉算法实现,topN 最优也可以利用相关改进算法实现,但是深入研究发现针对多约束的资料比较少,一种可行的思路是直接找到单权的 topN 直接计算剩余约束是否满足,就是想知道是否有比较可靠的理论算法,毕竟工程思路怕不够灵活。
    heart4lor
        3
    heart4lor  
       2022-03-29 23:03:24 +08:00
    感觉有点像网络流,又有点像 dp ;既然提到了 dijkstra ,以 dijkstra 为例,是否可以考虑松弛时直接拓展`if (dist[v] > dist[u] + weight)`中的 dist 和 weight 到多维即可?
    kilasuelika
        4
    kilasuelika  
       2022-03-30 00:27:03 +08:00 via Android
    图的路径优化可以转化为一个整数规划。
    以前用过 google 有个 or-tools ,有现成的路径规划器,里面可以进行约束。
    txx
        5
    txx  
       2022-03-30 00:30:45 +08:00
    最小费用流?
    vance123
        6
    vance123  
       2022-03-30 00:34:20 +08:00 via Android
    用求解器吧,比算法灵活多了
    guoph
        7
    guoph  
       2022-03-30 00:47:12 +08:00
    这个是运筹学( Operations Research, OR )的研究问题。可以使用混合整数规划( Mixed Integer Programming, MIP )建模,用 MIP 求解器求解。常用的求解器有商业的 Gurobi ,CPLEX ,和开源的 SCIP ,OR-Tools 等。以上求解器的文档或许能够给你提供些有帮助的例子。
    microxiaoxiao
        8
    microxiaoxiao  
    OP
       2022-03-30 19:42:05 +08:00
    @heart4lor 这个思路考虑过,但是要定义一个节点新距离不好定义,选最小。
    microxiaoxiao
        9
    microxiaoxiao  
    OP
       2022-03-30 19:48:39 +08:00
    @guoph @vance123 @kilasuelika 谢谢,是一些不错的工具集,主要就是想自己实现,黑盒子不好工程化,动态添加,删除节点什么的,可以参考一下。目前先就按 topN 或者深度优先+回溯的思路先选一个满足约束条件的路径也行,不要最优也行,就是感觉有点土办法。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1195 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:24 · PVG 02:24 · LAX 11:24 · JFK 14:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.