1

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

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

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

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

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

谢谢您的帮助。

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

4

2 回答 2

1

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

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

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

现在算法：

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

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

在这样做的同时，我们甚至可以对这些依赖项进行完整性检查。如果约束规范中有问题，我们可以在此步骤中轻松检测到这一点。

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

将所有任务打包到一个名为 /notYetProcessed/ 的列表中
创建空列表 /result/
虽然 /notYetProcessed/ 中仍有要处理的任务，但请执行以下操作：
    创建空列表/remaining/
    对于 /t/ in /notYetProcessed/ 中的所有任务，请执行以下操作：
        如果 /t/ 满足所有依赖项，则执行以下操作：
            将 /t/ 添加到 /result/
        否则：
            将 /t/ 添加到 /remaining/
    如果 /length(notYetProcessed)/ 匹配 /length(remaining)/ 然后执行：
        以错误终止
    /notYetProcessed/ = /remaining/

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

如果上述算法因错误而终止，这意味着： * 在此循环中无法处理任何任务 * 这意味着：无法解决某些依赖关系 * 这意味着：存在一个任务依赖循环，完全涉及剩余的任务

第3步：现在将存储在中的所有任务一一处理result，您会没事的。

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

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

于 2018-01-29T08:14:44.843 回答
-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任务，然后是task，然后是not_before任务，然后插入（或者如果它们已经出现，则移动）后续任务以满足约束，但这似乎并没有帮助，因为not_before任务not_after可以退出相对于彼此的顺序，所以我们仍然需要大量的交换。

于 2018-01-29T04:37:09.163 回答