MIM*_*IGA 15 algorithm graph topological-sort
我有一个带有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).
我一直在想这个问题.生成所有可能的拓扑排序(参考链接)并逐个计算目标函数始终是一种可能的解决方案,但如果N很大则需要花费太多时间.我还建议在生成所有可能的排序时使用分支绑定修剪(我不是非常熟悉的分支绑定但我认为这不会大大降低复杂性).
针对此类问题的任何(最佳或启发式)算法？如果算法也可以应用于其他目标函数,例如最小化某些节点的总开始时间,那将是完美的.任何建议表示赞赏.
PS:或者,是否有可能将此问题表述为线性整数优化问题？
解决这个问题的一种方法如下：
首先，我们运行全对最短路径算法Floyd-Warshall。该算法基本上可以用 5 行代码编写，并且可以及时运行O(V^3)。它生成图中每个顶点对之间的最短路径，即生成最短路径的 VXV 矩阵作为其输出。
修改这个算法很简单，这样我们也可以获得每条路径中包含的顶点数O(N^2)。所以现在我们可以消除所有少于 N 个顶点的路径。对于其余路径，我们按其成本对它们进行排序，然后测试每条路径以查看是否违反拓扑排序属性。如果不违反这个性质，那么我们就找到了我们想要的结果。
上面的最后一步，即测试拓扑排序可以针对每条 O(V^2) 路径在 O(V+E) 中执行。这会产生最坏情况下的运行时间O(V^4)。然而在实践中，这应该很快，因为 Floyd-Warshall 可以变得非常缓存友好，并且我们实际上只会测试 O(N^2) 路径的一小部分。此外，如果您的 DAG 不密集，那么您也可以使用适当的数据结构来优化拓扑测试。