• 请不要在回答技术问题时复制粘贴 AI 生成的内容
各位大牛，最近做图的最优路径相关，有没有针对多目标约束的相关算法？举个例子，就是交通规划中，时间<1 小时，并且油耗<1 升。找了一圈一般图论中的算的都是最优路径，不太满足需求。有相关的论文也行
microxiaoxiao · Mar 29, 2022 · 3086 viewsThis topic created in 1687 days ago, the information mentioned may be changed or developed.
 |
enki0423Mar 29, 2022 via iPhone
1
网络流？
|
 |
2
对，现在是单权可以通过一般的图算法狄克斯特拉算法实现，topN 最优也可以利用相关改进算法实现，但是深入研究发现针对多约束的资料比较少，一种可行的思路是直接找到单权的 topN 直接计算剩余约束是否满足，就是想知道是否有比较可靠的理论算法，毕竟工程思路怕不够灵活。
|
 |
heart4lorMar 29, 2022
3
感觉有点像网络流，又有点像 dp ；既然提到了 dijkstra ，以 dijkstra 为例，是否可以考虑松弛时直接拓展`if (dist[v] > dist[u] + weight)`中的 dist 和 weight 到多维即可？
|
 |
kilasuelikaMar 30, 2022 via Android
4
图的路径优化可以转化为一个整数规划。
以前用过 google 有个 or-tools ，有现成的路径规划器，里面可以进行约束。 |
 |
txxMar 30, 2022
5
最小费用流？
|
 |
vance123Mar 30, 2022 via Android
6
用求解器吧，比算法灵活多了
|
 |
guophMar 30, 2022
7
这个是运筹学（ Operations Research, OR ）的研究问题。可以使用混合整数规划（ Mixed Integer Programming, MIP ）建模，用 MIP 求解器求解。常用的求解器有商业的 Gurobi ，CPLEX ，和开源的 SCIP ，OR-Tools 等。以上求解器的文档或许能够给你提供些有帮助的例子。
|
|
8
@heart4lor 这个思路考虑过，但是要定义一个节点新距离不好定义，选最小。
|
|
9
@guoph @vance123 @kilasuelika 谢谢，是一些不错的工具集，主要就是想自己实现，黑盒子不好工程化，动态添加，删除节点什么的，可以参考一下。目前先就按 topN 或者深度优先+回溯的思路先选一个满足约束条件的路径也行，不要最优也行，就是感觉有点土办法。
|
Select Language