各位大牛，最近做图的最优路径相关，有没有针对多目标约束的相关算法？举个例子，就是交通规划中，时间<1 小时，并且油耗<1 升。找了一圈一般图论中的算的都是最优路径，不太满足需求。有相关的论文也行
microxiaoxiao · 2022-03-29 21:56:40 +08:00 · 1699 次点击这是一个创建于 968 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
enki0423 2022-03-29 22:03:41 +08:00 via iPhone
网络流？
|
 |
2
microxiaoxiao OP 对，现在是单权可以通过一般的图算法狄克斯特拉算法实现，topN 最优也可以利用相关改进算法实现，但是深入研究发现针对多约束的资料比较少，一种可行的思路是直接找到单权的 topN 直接计算剩余约束是否满足，就是想知道是否有比较可靠的理论算法，毕竟工程思路怕不够灵活。
|
 |
3
heart4lor 2022-03-29 23:03:24 +08:00
感觉有点像网络流，又有点像 dp ；既然提到了 dijkstra ，以 dijkstra 为例，是否可以考虑松弛时直接拓展`if (dist[v] > dist[u] + weight)`中的 dist 和 weight 到多维即可？
|
 |
4
kilasuelika 2022-03-30 00:27:03 +08:00 via Android
图的路径优化可以转化为一个整数规划。
以前用过 google 有个 or-tools ，有现成的路径规划器，里面可以进行约束。 |
 |
5
txx 2022-03-30 00:30:45 +08:00
最小费用流？
|
 |
6
vance123 2022-03-30 00:34:20 +08:00 via Android
用求解器吧，比算法灵活多了
|
 |
7
guoph 2022-03-30 00:47:12 +08:00
这个是运筹学（ Operations Research, OR ）的研究问题。可以使用混合整数规划（ Mixed Integer Programming, MIP ）建模，用 MIP 求解器求解。常用的求解器有商业的 Gurobi ，CPLEX ，和开源的 SCIP ，OR-Tools 等。以上求解器的文档或许能够给你提供些有帮助的例子。
|
|
8
microxiaoxiao OP @heart4lor 这个思路考虑过，但是要定义一个节点新距离不好定义，选最小。
|
|
9
microxiaoxiao OP @guoph @vance123 @kilasuelika 谢谢，是一些不错的工具集，主要就是想自己实现，黑盒子不好工程化，动态添加，删除节点什么的，可以参考一下。目前先就按 topN 或者深度优先+回溯的思路先选一个满足约束条件的路径也行，不要最优也行，就是感觉有点土办法。
|
Select Language