问具有目标函数的拓扑排序

EN

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

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

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

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

这是一个想法：

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

取数组片段，从该对的较低(根据拓扑顺序)节点开始(假设l )，并在较高节点(假设h )结束。对于在l和h之间排序的每个节点，计算它是否从下到下由l和/或从上到上由h限定。您可以通过在l的“向上”BFS中标记节点，在h之上的节点排序的处切割节点来计算前者的属性；类似地，通过在h的“向下”的BFS中标记节点，在l下的节点排序的处切割节点，可以计算前一个属性。这两个过程的复杂度都是O( B*L )，其中B是分支因子，L是最初在l和h之间排序的节点数。

现在，如果保留向上或向下重定位的每组节点内的原始排序顺序，则所有未由h从上方限定的节点可以移动到h上方，并且所有未由l从下方限定的节点可以移到l下方(两个集合可能重叠)，所有这些都不会违反数组的拓扑排序。

如果从原始排序顺序中剪切的线段不重叠，则可以根据需要对任意数量的线段应用相同的过程。

如果任何两个对重叠，例如(l1, h1)和(l2, h2)，例如l1 < l2 < h1 < h2在原始排序的顺序中，则会出现以下两种情况：

1)在拓扑代码顺序中h1和l2碰巧不相关的小情况下，您应该能够优化这两个对，它们基本上彼此独立，只需小心地将l2移到h1之上或h1移到l2之下(但不是，例如h1，如果这应该是可能的话)。

2)如果l2 < h1在拓扑顺序中，您可以将这两个对视为单对(l1, h2)，然后可能将该过程再次应用于(l2, h1)。

由于还不清楚在非平凡的重叠情况下，完整的过程将实现什么，特别是如果您有更复杂的重叠模式，那么无论重叠与否，统一对待所有对可能会更好。在这种情况下，可以重复处理订单，同时每次运行都会产生比前一次更好的结果(我不确定这个过程在目标函数方面是否会是单调的--可能不是)。