我有一个带有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:或者,是否有可能将此问题表述为线性整数优化问题?
2 回答
解决此问题的一种方法如下:
首先,我们运行All-Pairs最短路径算法Floyd-Warshall . 该算法可以在essentially 5 lines of code中编码,并在
O(V^3)
时间运行 . 它在图中的每对顶点之间产生最短路径,即,它产生最短路径的V×V矩阵作为其输出 .修改此算法非常简单,这样我们也可以获得每个
O(N^2)
路径中包含的顶点数 . 所以现在我们可以消除所有小于N个顶点的路径 . 对于其余路径,我们按成本对它们进行排序,然后测试每个路径以查看拓扑排序属性是否未被违反 . 如果没有违反此属性,那么我们已经找到了我们想要的结果 .对于每个O(V ^ 2)路径,可以在O(V E)中执行上述最后一步,即测试拓扑排序 . 这会产生
O(V^4)
的最坏情况运行时间 . 然而在实践中这应该是快速的,因为Floyd-Warshall可以非常缓存,我们现在只测试一小部分O(N ^ 2)路径 . 此外,如果您的DAG不密集,那么您也可以使用适当的数据结构优化拓扑测试 .这是一个想法:
为简单起见,首先假设您有一对要优化(稍后我将对一般情况进行评论),并假设您已经将图形拓扑排序为数组 .
从该对的较低节点(根据您的 topological 顺序)节点开始,例如
l
,结束于较高节点,比如h
. 对于在l
和h
之间排序的每个节点,计算它是否由l
从下面限定和/或由h
从上面限定 . 您可以通过从l
标记"upward" BFS中的节点来计算前一个属性,在h
以上的节点 sorted 处切割;同样地,后者通过从h
标记"downward" BFS,在l
以下的节点 sorted 处切割 . 任一传递的复杂性将为O(B * L),其中B
是分支因子,L
是最初在l
和h
之间排序的节点数 .现在,
h
之上没有从上面限制的所有节点都可以移动到h
以上,并且l
之下没有从下面限制的所有节点都可以移动到l
以下(两个集可能重叠),而不会违反拓扑排序数组,只要保留向上或向下重定位的每组节点内的原始排序顺序 .如果从原始排序顺序切割的段不重叠,则可以根据需要将相同的过程应用于尽可能多的对 .
如果任何两对重叠,例如
(l1, h1)
和(l2, h2)
,那么例如原始 sorted 顺序中的l1 <l2 <h1 <h2,您有以下两种情况:1)在
h1
和l2
恰好在 topological 顺序中无关的小事情中,你应该能够优化这两对彼此独立,只需要小心移动l2
以上h1
或h1
低于l2
(但 not ,例如h1
低于l1
,如果这应该是可能的话 . )2)如果 topological 顺序中的l2 <h1,您可以将两个对视为单对
(l1, h2)
,然后可能再次将该过程应用于(l2, h1)
.由于尚不清楚整个过程在重要的重叠情况下将会实现什么,特别是如果你有更复杂的重叠模式,所以无论重叠如何,都可以更好地统一处理所有对 . 在这种情况下,可以重复处理订单,同时每次运行产生比前一次改进(我不确定程序在目标函数方面是否会是单调的 - 可能不是 . )