排序具有依赖关系的任务的算法

Question

在一个私有(private)的开源项目中，我遇到了以下问题:

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

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

我正在寻找一种简单的算法，了解如何根据该信息构建有向图，然后可以将其用于循环检测并按照允许尊重所有这些执行顺序条件的顺序执行所有任务任务。

问:构建这样一个图表的高效好方法是什么？

感谢您的帮助。

注意:很明显，我们将需要图中的两个额外节点:起始节点和结束节点。让我们将它们命名为 START 和 END。很明显，没有依赖关系的节点必须以诸如 START -> A -> END 的结构结束。但是我不太清楚如何找到一种好方法来结束 START -> B -> C -> END 序列，因为 B 必须后跟 C，同时没有从 B 到 END 的边缘并且没有边缘从 START 到 C。

Answer 1

需求中有一个“ killer 级”功能，无法轻松解决。约束的方向不是一个，而是两个:

• 任务A必须在任务B之后执行=> A“依赖于”B
• 任务 A 必须在任务 B 之前执行 => B“依赖于”A

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

现在的算法:

第 1 步:将每个任务的所有这些约束编译为每个任务的一组单向依赖项。然后可以真正轻松地处理单向依赖性。首先构建图形，然后执行循环检测然后执行拓扑排序(感谢 Dimitry 这个术语)的第一个想法可以完全放弃。所以每个项目都以一组依赖项结束:

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

在执行此操作时，我们甚至可以对这些依赖项进行健全性检查。如果约束规范有问题，我们可以在此步骤中轻松检测到。

第 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 条件终止后，result 将包含要按照开始定义的所有约束的顺序处理的任务列表。

如果上述算法以错误终止，这意味着:* 没有任务可以在这个循环中处理* 这意味着:某些依赖项无法解决* 这意味着:存在一个任务依赖循环，正好涉及剩余的任务

第 3 步:现在将存储在 result 中的所有任务一一处理，一一处理就可以了。

如您所见，这甚至无需构建数据的特殊图形表示即可完成。通过接受我们可以获得的第一个解决方案(= 所有可能排序顺序的第一个变体)，“直接”对数据执行拓扑排序。

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