首页 文章

具有目标函数的拓扑排序

提问于
浏览
14

我有一个带有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 回答

  • 0

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

    首先,我们运行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不密集,那么您也可以使用适当的数据结构优化拓扑测试 .

  • 0

    这是一个想法:

    为简单起见,首先假设您有一对要优化(稍后我将对一般情况进行评论),并假设您已经将图形拓扑排序为数组 .

    从该对的较低节点(根据您的 topological 顺序)节点开始,例如 l ,结束于较高节点,比如 h . 对于在 lh 之间排序的每个节点,计算它是否由 l 从下面限定和/或由 h 从上面限定 . 您可以通过从 l 标记"upward" BFS中的节点来计算前一个属性,在 h 以上的节点 sorted 处切割;同样地,后者通过从 h 标记"downward" BFS,在 l 以下的节点 sorted 处切割 . 任一传递的复杂性将为O(B * L),其中 B 是分支因子, L 是最初在 lh 之间排序的节点数 .

    现在, h 之上没有从上面限制的所有节点都可以移动到 h 以上,并且 l 之下没有从下面限制的所有节点都可以移动到 l 以下(两个集可能重叠),而不会违反拓扑排序数组,只要保留向上或向下重定位的每组节点内的原始排序顺序 .

    如果从原始排序顺序切割的段不重叠,则可以根据需要将相同的过程应用于尽可能多的对 .

    如果任何两对重叠,例如 (l1, h1)(l2, h2) ,那么例如原始 sorted 顺序中的l1 <l2 <h1 <h2,您有以下两种情况:

    1)在 h1l2 恰好在 topological 顺序中无关的小事情中,你应该能够优化这两对彼此独立,只需要小心移动 l2 以上 h1h1 低于 l2 (但 not ,例如 h1 低于 l1 ,如果这应该是可能的话 . )

    2)如果 topological 顺序中的l2 <h1,您可以将两个对视为单对 (l1, h2) ,然后可能再次将该过程应用于 (l2, h1) .

    由于尚不清楚整个过程在重要的重叠情况下将会实现什么,特别是如果你有更复杂的重叠模式,所以无论重叠如何,都可以更好地统一处理所有对 . 在这种情况下,可以重复处理订单,同时每次运行产生比前一次改进(我不确定程序在目标函数方面是否会是单调的 - 可能不是 . )

相关问题