4

我有不同长度的电影剪辑（a1,...,an ）的（播放）列表（A） 。我想创建一个新列表(B)，其中剪辑 ( b1,...,bm ) 与(A)中的剪辑连接。

还有一个限制MAX_LEN，（B）中的bx不能超过。只有 a 中的相邻剪辑可以连接（a1+a2+a3是合法的连接，a1+a3不是）。(A)中的所有剪辑必须在(B)中出现一次，并且必须按照它们在(A)中出现的顺序出现

最优解主要：

1)最小化(B)中的剪辑数量。

和次要的：

2)最大化(B)中最短剪辑的持续时间。

主要约束1)比2)更重要，因此对于NumOfClips( S1 ) < NumOfClips( S1 )的 2 个不同解决方案S1和S2 ，即使 durationOfShortestClip( S1 ) < durationOfShortestClip( S2 )， S1也比S2 “更优” 。

这是一个示例，显示了一个输入列表(A)三个可能的输出(B1)和(B2)和(B3)。( B1 )或(B2)都满足1)（尽管(B2)是比(B1)更好的解决方案，因为 25>23）最佳解决方案是(B3)。 输入和输出列表示例

我想知道如何以有效的方式找到最佳解决方案？其他帮助完整的信息/线索，例如存在或不存在最优子问题等，也值得赞赏。

4

2 回答 2

0

一个非常模糊的想法，但它至少证明你的问题是多项式的。我的解决方案是那种O(N^3 * log N * log L)，其中 L 是所有剪辑的长度之和。

首先找到适当的最小可能数量的剪辑组G- 这相当简单。只需将尽可能多的剪辑放在第一组中，然后继续下一个。G这肯定会产生（即标准1）的最小值。然而，根据标准 2) 的最优性仍有待找到。

这是怎么回事：

  • 创建矩阵mat[i][j]，mat[i][j] = 1其中包含索引之间的 iff 剪辑i索引之间且j总和小于MAX_LEN。中的所有其他值mat均为 0。
  • 您对所有组中剪辑总和的最小值进行二分搜索。这一步给出了log L我算法中的因素。假设在给定的步骤中，选择的值是M
  • 复制matas copy_mat。copy_mat[i][j] = 1 <=> mat[i][j] = 1 and SUM(clips i..j) >= M
  • 将此矩阵提高到找到的剪辑组数的幂G。矩阵乘法给出因子N^3了最简单的方法。提高权力会增加额外的log N因素。
  • 如果copy_mat[1][N] = 1然后有一个解决方案M，请尝试增加它。否则 - 减少。
  • 减少二分查找步骤。

当二分搜索完成时，它将找到最佳值M。如果您需要找到确切的分组，则需要在进行矩阵乘法时使用一个辅助矩阵，但我认为您应该能够自己弄清楚最后一点。

我将继续考虑更快的解决方案，但我的至少证明您的问题不是复杂性指数级的，并且可以相对快速地处理大约 1000 个剪辑的数量。

于 2013-01-08T15:45:31.940 回答
0

对于实现的主要约束，您可以使用贪心算法。因为您应该将（A）中的第一个元素剪辑设置为（B）中的第一个元素，现在如果您在第一个元素（B）中有空白空间，并且在（A）中有第二个元素剪辑) 可以在第一个元素中设置为 (B)，所以这样做，否则设置为 B 中的第二个元素。重复此解决方案以设置 (A) 中的所有剪辑在 (B) 中出现一次。在这个结果中，您将 (B) 中的剪辑数量减少了 o(n)。对于最佳解决方案，您实现了次要约束，您应该最大化最短的持续时间。假设贪心算法提供 B，即 B(i) 是列表中的第 i 个元素项。很明显，B(i) 中的任何剪辑都不能出现在 B(i-1) 中，所以只有 b(i) 中的最后一个成员) 可以出现在 b(i+1) 中。所以检查移动是否最大化（B）中最短剪辑的持续时间。

于 2013-01-08T15:43:31.677 回答