具有依赖项的任务排序算法

Question

在一个私人开源项目中，我遇到了以下问题：

有各种各样的任务要执行。其中一些任务将具有

• 它们必须在一个或多个特定的其他任务之后执行
• 它们必须在一个或多个特定的其他任务之前执行

我在寻找一个简单的算法，如何利用这些信息构建一个有向图，然后可以用于周期检测，并以一个允许尊重所有这些条件的顺序执行所有任务。

问：什么是构建这样一个图的有效、好的方法？

谢谢你的帮助。

注意：很明显，我们需要在图中增加两个节点：一个开始节点和一个结束节点。让我们把它们命名为开始和结束。显然，没有依赖关系的节点必须以START这样的构造结束-

Answer 1

您可以从任何顺序开始，然后遍历该顺序，交换任何不有序的元素。您可以重复这个过程，直到没有更多的任务是不有序的。

我会使用一个哈希表（或简单的数组）进行快速查找，以确定任务是否无序。

伪代码：

class Task:
    id: int # serial id of task, ie 1..n
    not_before: array[int] # ids of tasks this task cannot precede
    not_after: array[int] # ids of tasks this task cannot come after

tasks: array[Task] = ... # tasks in order of ids

order: array[int] = [1,2,...,n] # task ids in initial order

positions: array[int] = ... # positions[i] is the index of task i in order array

def swap_tasks(i, j):
    swap(order[positions[i]], order[positions[j]])
    swap(positions[i], positions[j])

repeat:
    made_swap = False
    for i in 0..n: # loop over task ids
        for j in tasks[i].not_before:
            if positions[i] < positions[j]:
                swap_tasks(i, j)
                made_swap = True
        for j in tasks[i].not_after:
            if positions[i] > positions[j]:
                swap_tasks(i, j)
                made_swap = True
    if made_swap == False:
        break

对于n任务和O（k）每个任务的约束，这应该在O（n²log（k））中运行，因为一个任务最多可以移动n次（因为它不能返回到上一个被交换的任务的位置）。

我想过按顺序处理任务并插入not_after任务，然后是任务，然后是not_before任务，然后插入（或移动（如果它们已经出现）后续任务以满足约束，但这似乎并没有什么帮助，因为not_before和not_after任务可能彼此不按顺序，所以我们仍然需要大量的交换。

Answer 2

需求中有一个“杀手”特性，阻止了简单的解决方案。约束的方向不是一个而是两个：

• 任务A必须在任务B之后执行=

在现实世界中，我面临的这些依赖关系甚至更加复杂，但这并不重要：所有这些都可以分解为刚刚描述的模拟情况。

现在算法：

步骤1：将每个任务的所有这些约束编译为每个任务的一组单向依赖项。这样就可以很容易地处理单向依赖关系。首先构建一个图，然后执行循环检测，然后执行拓扑排序（感谢术语Dimitry）的第一个想法可以完全放弃。因此，每个项目最终都有一组依赖项：

• 如果任务A必须在任务B之后执行，我们将“B”存储在A的依赖项集中。

在这样做的同时，我们甚至可以对这些依赖项进行健全性检查。如果约束规范中存在错误，我们可以在这一步中轻松检测到。

第2步：现在我们有一个非常简单的问题，因为只有单向依赖关系。这些可以被视为先决条件：只有满足所有先决条件，才能执行任务。现在我们可以进行如下操作：

pack all tasks into a list named /notYetProcessed/
create empty list /result/
while there are still tasks to process in /notYetProcessed/ do:
    create empty list /remaining/
    for all tasks /t/ in /notYetProcessed/ do:
        if all dependencies are met for /t/ then do:
            add /t/ to /result/
        else do:
            add /t/ to /remaining/
    if /length(notYetProcessed)/ matches /length(remaining)/ then do:
        terminate with error
    /notYetProcessed/ = /remaining/

外部while条件终止后，结果将包含一个要处理的任务列表，其顺序遵循开头定义的所有约束。

如果上述算法终止时出现错误，这意味着：*此循环中无法处理任何任务*这意味着：无法解析某些依赖关系*这意味着：存在一个任务依赖循环，该循环恰好涉及剩余的任务

步骤3：现在一个接一个地处理存储在结果中的所有任务，一个接一个地处理，你就没事了。

正如您所见，这可以在不构建数据的特殊图形表示的情况下完成。拓扑排序是通过接受第一个解决方案（“所有可能的排序顺序的第一个变体”）来“直接”对数据执行的，我们可以得到第一个解决方案。

可能有一些更有效的算法来解决这个问题（在执行第一个依赖项编译之后），我可能不知道。如果是这样，我很乐意了解他们！