加权 Activity 选择问题，允许改变开始时间
Weighted Activity Selection Problem with allowing shifting starting time
我有一些带有权重的活动，我想通过最大化总权重来 select 不重叠的活动。这是已知问题并且存在解决方案。
就我而言，我可以在一定程度上改变活动的开始时间，而持续时间保持不变。这将给我一些灵活性，我可能会提高我的利用率。
示例场景如下所示，其中所有活动都应该在间隔 (0-200) 内：
(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 125 100
a6: 120 140 150
a7: 126 130 100
如果不改变灵活性，我会选择 (a1, a3, a6) 就是这样。另一方面，我最多 将灵活性 转移到 left/right t 个单位对于给出 t 的任何任务。在那种情况下，我可能会想出这个时间表，并且所有任务都可以 selected 除了 a7，因为 shift 无法避免冲突。
t: 5
a1: 8 10 120 (shifted -2 to left)
a2: 10 13 100
a3: 14 18 150
a4: 18 24 100 (shifted +4 to right)
a5: 115 120 100 (shifted -5 to left)
a6: 120 140 150
在我的问题中，相对于 activity 持续时间，我的总时间非常长。虽然活动平均大约 10 秒，但我的总时间甚至会达到 10000 秒。然而，这并不意味着所有活动都可以 selected，因为转移灵活性不足以让某些活动不重叠。
同样在我的问题中，有一组活动重叠并且非常空 space 没有活动，并且出现另一组重叠活动，即 a1、a2、a3 和 a4 是 cluster1，a5，a6 和 a7 是 cluster2。每个簇都可以通过向左和向右移动其中的一些来及时扩展。通过这样做，我可以 select 比原来的 activity select 离子问题更多的活动。但是，我不知道如何决定将哪些任务向左或向右移动。
我的期望是找到一个接近最优的解决方案，其中总利润将以某种方式达到局部最优。我不需要全局最优值。我也没有关于集群利用率的任何标准，即我不能保证每个集群的最小数量 activity 等。实际上，这些集群是我在视觉上描述的。没有定义的集群。但是，在时域中，活动以某种方式分离为集群。
另外 activity 开始和结束时间都是整数，因为我可以忽略分数。我将有大约 50 个活动，平均持续时间为 10 个。时间 window 就像 10000。
这个问题有什么可行的解决办法吗？
您提到您可以将活动划分为不重叠的集群，即使其中的活动移动到一定程度也是如此。这些集群中的每一个都可以独立考虑，并且为每个集群计算的最佳结果简单地总结为最终答案。因此，该算法的第一步可以是一个试验 运行，在两个方向上扩展所有活动，找到哪些形成集群，并独立处理每个集群。在最坏的情况下，所有活动可能会形成一个集群。
根据剩余簇的最大大小，有几种方法。如果它低于 20（甚至 30，取决于您希望您的程序在几秒或几分钟内达到 运行），您可以将对给定集群中所有活动子集的搜索与贪婪方法结合起来。换句话说：如果您正在处理 N 个元素的子集，请尝试它的每个 2^N 个可能的子集（好吧，2^N-1 如果我们忘记了空子集），检查这个特定子集中的活动是否可以按非重叠方式进行调度，并选择符合条件且总和最大的子集。
我们如何检查给定的活动子集是否可以以非重叠方式安排？让我们按照结尾的升序对它们进行排序，并从左到右处理它们。对于每个 activity，我们都尽量尽早安排，确保它不会与我们已经考虑过的活动相交。因此，集群中的第一个 activity 始终比原计划早 t 启动，第二个在第一个结束时启动，或者比原计划早 t 启动，以两者为准更大，等等。如果在任何时候我们都无法以不与前一个重叠的方式安排下一个 activity，则无法以非重叠方式安排该子集中的活动。该算法需要 O(NlogN) time，并且每个聚类总共在 O(2^N * NlogN) 中处理。再次注意这个函数增长非常快，所以如果你处理的是足够大的集群，这种方法会超出 window.
===
另一种方法特定于您提供的附加限制。如果活动的开始和结束以及参数 t 都是以整数秒为单位测量的，并且 t 大约是 2 分钟，那么每个集群的问题都设置在一个小的离散 space.即使您可以将任务定位为从非整数秒值开始，也始终存在仅使用整数的最佳解决方案。 （为了证明这一点，请考虑一个不使用整数的最佳解决方案 - 因为 t 是整数，所以你总是可以将任务从最左边开始，向左移动一点，以便它从整数值开始。）
知道开始和结束时间是离散的，你可以建立一个DP解决方案：按照活动结束的升序处理*，并记住你可以从第一个1获得的最大可能权重和， 2, ..., 如果给定的 activity 在时间 x 结束，则从 activity_start - t 到 activity_start + t 每个 x 的 N 个活动。如果我们将这个 memoized 函数表示为 f[activity][end_time]，那么递推关系就是 f[a][e] = weight[a] + max(f[i][j] over all i < a, j <= e - (end[a] - start[a])，大致可以翻译为 "if activity a ended at time e, the previous activity must have ended at or before start of a - so let's pick the maximum total weight over previous activities and their ends, and add the current activity's weight".
*同样，我们可以证明至少存在一个保留此顺序的最佳答案，即使可能存在其他不具备此顺序的最佳答案属性
我们可以更进一步，消除对先前活动的迭代，而不是在 f 中编码此信息。然后它的定义将更改为“f[a][e] 是前 a 个活动的最大可能总权重，如果 none 个活动在 e 之后结束”，递推关系将变为 f[a][e] = max(f[a-1][e], weight[a] + max(f[a-1][i] over i <= e - (end[a] - start[a])]))，其计算复杂度为 O(X * N)，其中 X 是放置任务 starts/ends 的离散 space 的总跨度。
我假设您不仅需要计算可能的最大重量，还需要计算 select 获得它所需的活动，甚至可能需要开始每项活动的确切时间。值得庆幸的是，我们可以从 f 的值中推导出所有这些，或者在计算 f 的同时计算它。后者更容易推理，所以让我们介绍第二个函数g[activity][end]。 g[activity][end] returns 一对 (last_activity, last_activity_end)，本质上向我们指出了 f[activity][end] 中最佳权重使用的确切 activity 及其时间。
让我们通过您提供的示例来说明其工作原理：
(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 125 100
a6: 120 140 150
a7: 126 130 100
- 我们按结束时间对活动进行排序，从而交换 a7 和 a6。
- 我们为第一个activity初始化
f和g的值：
f[1][7] = 120, f[1][8] = 120, ..., f[1][17] = 120，这意味着第一个 activity 可以在 7 到 17 之间的任何位置结束，成本为 120。所有其他 i 的 f[1][i] 应设置为 0 .
g[1][7] = (1, 7), g[1][8] = (1, 8), ..., g[1][17] = (1, 17)，意味着 f[1][i] 值中包含的最后一个 activity 是 a1，并在 i 处结束。 g[1][i] 对于 [7, 17] 之外的所有 i 是 undefined/irrelevant.
- 这就是有趣的开始。对于每个
i 使得 a2 不能在时间 i 结束，让我们分配 f[2][i] = f[1][i], g[2][i] = g[1][i]，这实际上意味着我们不会使用 activity a2 在这些答案中。对于所有其他 i，即在 [8..18] 区间内，我们有：
f[2][8] = max(f[1][8], 100 + max(f[1][0..5])) = f[1][8]
f[2][9] = max(f[1][9], 100 + max(f[1][0..6])) = f[1][9]
f[2][10] = max(f[1][10], 100 + max(f[1][0..7]))。这是第一次第二个子句不只是普通的 100，如 f[1][7]>0。实际上，它是 100+f[1][7]=220，这意味着我们可以采用 activity a2，以一种在时间 10 处结束的方式移动它，并获得总重量220。我们继续以这种方式为所有 i <= 18.
计算 f[2][i]
g 的值是：g[2][8]=g[1][8]=(1, 8)、g[2][9]=g[1][9]=(1, 9)、g[2][10]=(2, 10)，因为取 activity a2 和在这种情况下，在时间 10 结束。
我希望这种情况的继续模式是可见的 - 我们计算 f 和 g 的所有值直到最后，然后选择所有可能的最大值 f[N][e]最后 activity 的结束时间 e。借助辅助函数 g，我们可以向后遍历这些值以计算出确切的活动和时间。即，我们使用的最后一个activity，它的时间在g[N][e]。我们称它们为 A 和 T。我们知道A开始于T-(end[A]-start[A])。然后，之前的 activity 必须在该点或之前结束 - 所以让我们看一下 g[A-1][T-(end[A]-start[A])，依此类推。
请注意，即使您不将任何东西划分到集群中，这种方法也有效，但是通过划分，可以在其中安排任务的 space 的大小会减少，并且 运行时间.
您可能会注意到，这些解决方案都不是输入大小的多项式。我有一种感觉，你的问题没有一般的多项式解决方案，但我无法通过将另一个 NP 完全问题减少到它来证明它。真的很想阅读减少/更好的通用解决方案！
我有一些带有权重的活动，我想通过最大化总权重来 select 不重叠的活动。这是已知问题并且存在解决方案。
就我而言，我可以在一定程度上改变活动的开始时间，而持续时间保持不变。这将给我一些灵活性，我可能会提高我的利用率。
示例场景如下所示，其中所有活动都应该在间隔 (0-200) 内：
(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 125 100
a6: 120 140 150
a7: 126 130 100
如果不改变灵活性，我会选择 (a1, a3, a6) 就是这样。另一方面，我最多 将灵活性 转移到 left/right t 个单位对于给出 t 的任何任务。在那种情况下，我可能会想出这个时间表，并且所有任务都可以 selected 除了 a7，因为 shift 无法避免冲突。
t: 5
a1: 8 10 120 (shifted -2 to left)
a2: 10 13 100
a3: 14 18 150
a4: 18 24 100 (shifted +4 to right)
a5: 115 120 100 (shifted -5 to left)
a6: 120 140 150
在我的问题中，相对于 activity 持续时间，我的总时间非常长。虽然活动平均大约 10 秒，但我的总时间甚至会达到 10000 秒。然而，这并不意味着所有活动都可以 selected，因为转移灵活性不足以让某些活动不重叠。
同样在我的问题中，有一组活动重叠并且非常空 space 没有活动，并且出现另一组重叠活动，即 a1、a2、a3 和 a4 是 cluster1，a5，a6 和 a7 是 cluster2。每个簇都可以通过向左和向右移动其中的一些来及时扩展。通过这样做，我可以 select 比原来的 activity select 离子问题更多的活动。但是，我不知道如何决定将哪些任务向左或向右移动。
我的期望是找到一个接近最优的解决方案，其中总利润将以某种方式达到局部最优。我不需要全局最优值。我也没有关于集群利用率的任何标准，即我不能保证每个集群的最小数量 activity 等。实际上，这些集群是我在视觉上描述的。没有定义的集群。但是，在时域中，活动以某种方式分离为集群。
另外 activity 开始和结束时间都是整数，因为我可以忽略分数。我将有大约 50 个活动，平均持续时间为 10 个。时间 window 就像 10000。
这个问题有什么可行的解决办法吗？
您提到您可以将活动划分为不重叠的集群，即使其中的活动移动到一定程度也是如此。这些集群中的每一个都可以独立考虑，并且为每个集群计算的最佳结果简单地总结为最终答案。因此，该算法的第一步可以是一个试验 运行，在两个方向上扩展所有活动，找到哪些形成集群，并独立处理每个集群。在最坏的情况下，所有活动可能会形成一个集群。
根据剩余簇的最大大小，有几种方法。如果它低于 20（甚至 30，取决于您希望您的程序在几秒或几分钟内达到 运行），您可以将对给定集群中所有活动子集的搜索与贪婪方法结合起来。换句话说：如果您正在处理 N 个元素的子集，请尝试它的每个 2^N 个可能的子集（好吧，2^N-1 如果我们忘记了空子集），检查这个特定子集中的活动是否可以按非重叠方式进行调度，并选择符合条件且总和最大的子集。
我们如何检查给定的活动子集是否可以以非重叠方式安排？让我们按照结尾的升序对它们进行排序，并从左到右处理它们。对于每个 activity，我们都尽量尽早安排，确保它不会与我们已经考虑过的活动相交。因此，集群中的第一个 activity 始终比原计划早 t 启动，第二个在第一个结束时启动，或者比原计划早 t 启动，以两者为准更大，等等。如果在任何时候我们都无法以不与前一个重叠的方式安排下一个 activity，则无法以非重叠方式安排该子集中的活动。该算法需要 O(NlogN) time，并且每个聚类总共在 O(2^N * NlogN) 中处理。再次注意这个函数增长非常快，所以如果你处理的是足够大的集群，这种方法会超出 window.
===
另一种方法特定于您提供的附加限制。如果活动的开始和结束以及参数 t 都是以整数秒为单位测量的，并且 t 大约是 2 分钟，那么每个集群的问题都设置在一个小的离散 space.即使您可以将任务定位为从非整数秒值开始，也始终存在仅使用整数的最佳解决方案。 （为了证明这一点，请考虑一个不使用整数的最佳解决方案 - 因为 t 是整数，所以你总是可以将任务从最左边开始，向左移动一点，以便它从整数值开始。）
知道开始和结束时间是离散的，你可以建立一个DP解决方案：按照活动结束的升序处理*，并记住你可以从第一个1获得的最大可能权重和， 2, ..., 如果给定的 activity 在时间 x 结束，则从 activity_start - t 到 activity_start + t 每个 x 的 N 个活动。如果我们将这个 memoized 函数表示为 f[activity][end_time]，那么递推关系就是 f[a][e] = weight[a] + max(f[i][j] over all i < a, j <= e - (end[a] - start[a])，大致可以翻译为 "if activity a ended at time e, the previous activity must have ended at or before start of a - so let's pick the maximum total weight over previous activities and their ends, and add the current activity's weight".
*同样，我们可以证明至少存在一个保留此顺序的最佳答案，即使可能存在其他不具备此顺序的最佳答案属性
我们可以更进一步，消除对先前活动的迭代，而不是在 f 中编码此信息。然后它的定义将更改为“f[a][e] 是前 a 个活动的最大可能总权重，如果 none 个活动在 e 之后结束”，递推关系将变为 f[a][e] = max(f[a-1][e], weight[a] + max(f[a-1][i] over i <= e - (end[a] - start[a])]))，其计算复杂度为 O(X * N)，其中 X 是放置任务 starts/ends 的离散 space 的总跨度。
我假设您不仅需要计算可能的最大重量，还需要计算 select 获得它所需的活动，甚至可能需要开始每项活动的确切时间。值得庆幸的是，我们可以从 f 的值中推导出所有这些，或者在计算 f 的同时计算它。后者更容易推理，所以让我们介绍第二个函数g[activity][end]。 g[activity][end] returns 一对 (last_activity, last_activity_end)，本质上向我们指出了 f[activity][end] 中最佳权重使用的确切 activity 及其时间。
让我们通过您提供的示例来说明其工作原理：
(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 125 100
a6: 120 140 150
a7: 126 130 100
- 我们按结束时间对活动进行排序，从而交换 a7 和 a6。
- 我们为第一个activity初始化
f和g的值：
f[1][7] = 120, f[1][8] = 120, ..., f[1][17] = 120，这意味着第一个 activity 可以在 7 到 17 之间的任何位置结束，成本为 120。所有其他 i 的 f[1][i] 应设置为 0 .
g[1][7] = (1, 7), g[1][8] = (1, 8), ..., g[1][17] = (1, 17)，意味着 f[1][i] 值中包含的最后一个 activity 是 a1，并在 i 处结束。 g[1][i] 对于 [7, 17] 之外的所有 i 是 undefined/irrelevant.
- 这就是有趣的开始。对于每个
i使得a2不能在时间i结束，让我们分配f[2][i] = f[1][i], g[2][i] = g[1][i]，这实际上意味着我们不会使用 activitya2在这些答案中。对于所有其他i，即在[8..18]区间内，我们有：
f[2][8] = max(f[1][8], 100 + max(f[1][0..5])) = f[1][8]
f[2][9] = max(f[1][9], 100 + max(f[1][0..6])) = f[1][9]
f[2][10] = max(f[1][10], 100 + max(f[1][0..7]))。这是第一次第二个子句不只是普通的 100，如 f[1][7]>0。实际上，它是 100+f[1][7]=220，这意味着我们可以采用 activity a2，以一种在时间 10 处结束的方式移动它，并获得总重量220。我们继续以这种方式为所有 i <= 18.
f[2][i]
g 的值是：g[2][8]=g[1][8]=(1, 8)、g[2][9]=g[1][9]=(1, 9)、g[2][10]=(2, 10)，因为取 activity a2 和在这种情况下，在时间 10 结束。
我希望这种情况的继续模式是可见的 - 我们计算 f 和 g 的所有值直到最后，然后选择所有可能的最大值 f[N][e]最后 activity 的结束时间 e。借助辅助函数 g，我们可以向后遍历这些值以计算出确切的活动和时间。即，我们使用的最后一个activity，它的时间在g[N][e]。我们称它们为 A 和 T。我们知道A开始于T-(end[A]-start[A])。然后，之前的 activity 必须在该点或之前结束 - 所以让我们看一下 g[A-1][T-(end[A]-start[A])，依此类推。
请注意，即使您不将任何东西划分到集群中，这种方法也有效，但是通过划分，可以在其中安排任务的 space 的大小会减少，并且 运行时间.
您可能会注意到，这些解决方案都不是输入大小的多项式。我有一种感觉，你的问题没有一般的多项式解决方案，但我无法通过将另一个 NP 完全问题减少到它来证明它。真的很想阅读减少/更好的通用解决方案！