我有一个带有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:或者,是否有可能将此问题表述为线性整数优化问题？