如果必须满足所有先决条件，则最大化 K 课程的价值总和

Question

背景：当我试图为我公司的软件工程师提出招聘挑战时，我遇到了以下问题。我很快意识到这可能太难了，因为我自己想不出一个好的解决方案:-) 不过，我很想知道是否有人能想出一个有效的算法。

考虑一名工人，他正在决定参加 select 继续教育课程中的哪一个。每门课程都会教给他们一项技能，这将使他们的薪水增加一定的已知数额。工人希望获得最高薪水提升，但需要考虑一些限制条件：每门课程需要一个月才能完成，并且工人一次只能学习一门课程。他们只有 K 个月的时间可以接受教育。此外，有些课程有先决条件，只有在工人已经完成所有先决条件课程的情况下才能参加。工人如何找到能给他们带来最大加薪的课程？

更正式地，考虑具有 N 个节点的有向无环图，其值为 v[0]，...，v[N-1]（均为正），以及 M 条有向边的列表 E = [ (a[0],b[0]), ..., (a[M-1],b[M-1])]。为简单起见，我们可以假设拓扑顺序（即 0 <= a[i] < b[i] < N for i = 0, ..., M-1）。如果我们只能 select 一个节点，如果它在 DAG 中的所有祖先都被 selected，那么 K 个节点的最大总和是多少？

我们可以通过遍历所有大小为 K 的子集并检查是否满足所有先决条件来在 O(M + K * N^K) 中轻松解决此问题。一个简单的 Python 实现如下：

def maxSumNodes(v, E, K):
    # For each node, compute all of its direct ancestors in the DAG
    N = len(v)
    ancestors = [[] for i in range(N)]
    for a, b in E:
        ancestors[b].append(a)
    maxSumValues = 0
    for r in itertools.combinations(range(N), K):
        sumValues = sum(v[i] for i in r)
        nodesSelected = set(r)
        if all(all(x in nodesSelected for x in ancestors[y]) for y in r):
            maxSumValues = max(maxSumValues, sumValues)
    return maxSumValues

但是，如果 K 很大（例如 N = 1,000,000，K = 500,000），这将变得非常昂贵。 N 中是否存在适用于任何 K 的多项式算法？或者，是否可以证明该问题是 NP-hard 问题？

Answer 1

我找到了这个算法，它只比较所有符合有效要求的k集

class Node(val value: Int, val children: List<Node> = emptyList())

fun maximise(activeNodes: List<Node>, capacity: Int) : Int {
    if(capacity == 0 || activeNodes.isEmpty()) return 0
    return activeNodes.maxOf { it.value + maximise(activeNodes - it + it.children, capacity - 1) }
}

val courses = listOf(Node(value = 1, children = listOf(Node(value = 20))), Node(value = 5))
val months = 2
maximise(courses, months)

（构建 DAG 不是问题，所以我只是假设我的输入已经是 DAG 形式）

如果有很多要求，这个算法会比你的算法表现得更好。然而，该算法的最坏情况（无要求）归结为检查每个可能的 k 集，这意味着 O(N^K).

这个问题当然看起来 NP-hard，但是证明它很复杂。我得到的最接近证明的是将其转换为修改后的 knapsack problem（这是 NP-hard）（@user3386109 在评论中也提到）：

从 DAG 中所有路径的列表开始，将它们的组合值作为值，将它们的长度作为权重。现在开始解决你的背包问题，但是每当一个项目被选中时，

删除该路径的所有子集
按如下方式修改该路径的所有超集：按该路径值减少值，按该路径权重减少权重。

我认为这至少和背包一样难，但我无法证明。

Answer 2

这道题是NP完全题。您可以证明，对于给定的顶点加权 DAG 和整数 k 和 M，决定是否存在总价值至少为 k 任务的有效计划的问题11=]，是NP完全的。该证明使用小工具和从一些第一个困难证明中借用的策略来安排 Garey and Johnson.

事实上，我将证明更强的说法，即使将所有权重限制为 1 或 2 并且 DAG 的最长路径和最大入度最多为 2,问题是NP-Hard.

首先，问题出在 NP 中：给定 k 个任务的见证（调度），我们可以在线性时间内测试调度是否有效并且至少具有 M 个值。

您可以给出 CLIQUE 的归约：假设我们有一个 CLIQUE 实例，它是一个无向简单图 G，具有顶点 V = {v1, v2...vq} 和边 E = {e1, e2,...er} 以及一个整数 p，我们被问到 G 是否有一个大小为 p.

的集团

我们将其转换为以下 DAG 调度实例：

我们的顶点集（任务）是{V1, V2...Vq} U {E1, E2,...Er}
所有任务 Vi 的值 1 1 <= i <= q
所有任务 Ej 的值 2 1 <= j <= r
每当 vi 是 G 中 ej 的端点时，我们的 DAG 中就有一个弧线 (Vi, Ej)。
k = p(p+1)/2
M = p^2

优先级 constraints/DAG 边恰恰是我们不能执行边任务 Ej 直到我们完成对应于其端点的两个顶点任务的要求。我们必须证明，当且仅当 G 有一个大小为 p 的集团时，我们的 DAG 中存在一个价值至少 M 的 k 任务的有效时间表。 =76=]

假设我们有一个包含 k 个任务的有效时间表，其价值至少为 M。由于 M 是 p^2，并且 k = p(p+1)/2，达到此值的一种方法是至少完成 p(p-1)/2 个边缘任务，其值 2，另外任何 p 其他任务。事实上，我们必须完成至少这么多边缘任务才能达到价值 M:

由于G是一个简单的图，要使p(p-1)/2条边的两个端点都被顶点覆盖，我们必须至少使用p个顶点。所以一定是恰好 p 个顶点任务完成，因此恰好 p(p-1)/2 个边任务完成，根据优先约束，这意味着那些 p 个对应的顶点形成一个团在 G.

为了证明另一个方向，直接给定G中一个大小为p的团，我们可以选择p对应的顶点任务和p(p-1)/2对应的顶点任务边缘任务以获得价值 M 的 k 任务的时间表。证明到此结束。

关于这个引人入胜的问题以及尝试有效解决它的曲折旅程的一些结束语：

从某种意义上说，CLIQUE 是最难的 NP-Complete 问题之一，因此从 CLIQUE 减少意味着这个问题继承了它的难度：DAG 调度问题难以近似且固定参数难以处理，在这个意义上比 Knapsack 更难。
由于 DAG 调度仅取决于可达性约束，因此起初似乎可以采用有效的解决方案。实际上，您可以对图进行传递归约，然后使用拓扑排序，其中顶点也按深度排序（最长路径以顶点结束）。
在实践中，这个问题的许多有趣实例都可以有效地解决（这是我凭直觉怀疑问题不是 NP-Hard 的原因之一）。如果 DAG 很深并且一些顶点有很多祖先，而不是最多 2 个，我们可以通过拓扑顺序向后进行深度优先搜索。猜测一个顶点在我们的时间表中会强制其所有祖先也出现在时间表中。这大大减少了图的大小（可能分成许多不连贯的、容易解决的组件）并减少了 k 祖先的数量。

总的来说，这是一个非常有趣的问题——我无法在别处找到确切的问题，甚至无法找到有关 DAG 相关结构属性的太多信息。然而，CLIQUE 可用于许多调度问题：顶点和边任务的术语和使用改编自 Garey and Johnson's 1976 hardness proof, (which I highly recommend reading) 表面上不同的问题：调度整个（未加权的）DAG，但任务具有可变的截止日期和单位处理时间，我们只想知道是否最多可以使 k 个任务在截止日期前延迟。

如果必须满足所有先决条件，则最大化 K 课程的价值总和

Maximize sum of values of K courses if all prerequisites must be met

algorithm

graph-algorithm

directed-acyclic-graphs