algorithm - 具有目标函数的拓扑排序

Question

我有一个有 N 个节点的 DAG，即 1, 2, ..., N，每个节点都有一个权重(我们可以称之为时间)x_1, x_2, ..., x_N。我想做一个拓扑排序，但难点是我在排序时有一个目标函数。我的目标函数是最小化几对节点之间的总时间。

例如，我有一个有 6 个节点的 DAG，我想要一个特定的拓扑排序，使得 (1,3) + (2,4) 最小化，其中 (A ,B) 表示两个节点 A 和 B 之间的时间。例如，如果我们有一个排序 [1, 6, 3, 2, 5, 4, 7], (1,3) = x_6 和 (2,4) = x_5。基于DAG，我想找到一个最小化(1,3) + (2,4)的排序。

这个问题我想了很久。生成所有可能的拓扑排序(引用 link )并逐一计算目标函数始终是一种可能的解决方案，但如果 N 很大，则需要太多时间。我还被建议在生成所有可能的排序时使用分支边界修剪(我不是很熟悉分支边界，但我认为这不会显着降低复杂性)。

有任何(最优或启发式)算法可以解决这类问题吗？如果该算法也可以应用于其他目标函数，例如最小化某些节点的总启动时间，那将是完美的。任何建议表示赞赏。

PS:或者，是否可以将此问题表述为线性整数优化问题？

Answer 1

解决这个问题的一种方法如下:

首先我们运行 All-Pairs 最短路径算法 Floyd-Warshall .该算法可以编码在essentially 5 lines of code中它在 O(V^3) 时间内运行。它生成图中每个顶点对之间的最短路径，即生成 V X V 最短路径矩阵作为其输出。

修改此算法很容易，这样我们也可以获得每个 O(N^2) 路径中包含的顶点数。所以现在我们可以消除所有少于 N 个顶点的路径。对于剩余的路径，我们按它们的成本对它们进行排序，然后测试它们中的每一个以查看是否不违反拓扑排序属性。如果不违反此属性，那么我们就找到了我们想要的结果。

上面的最后一步，即测试拓扑排序可以在 O(V+E) 中为每个 O(V^2) 路径执行。这会产生 O(V^4) 的最坏情况运行时间。然而在实践中这应该很快，因为 Floyd-Warshall 可以非常缓存友好并且我们在现实中只会测试 O(N^2) 路径的一小部分。此外，如果您的 DAG 不密集，那么您也可以使用适当的数据结构优化拓扑测试。