在特定约束条件下找到最佳项目组合的算法

Question

我会尝试用数学语言来解释这个问题。
假设我有一组项目 X = {x_1, x_2, ..., x_n}。 X 的每一项都属于集合 S_1, S_2, ..., S_5 中的一个。我认为 X 的所有子集都包含 5 个项目:{x_i1, x_i2, ..., xi5} 所以 x_i1 属于 S_1, ..., x_i5属于 S_5。
一些子集被认为是正确的，而一些子集被认为是不正确的。如果子集不包含冲突项，则认为它是正确的。我有一个函数 f1 来确定一对项目是否冲突。
我还有一个函数 f2，它可以比较这些正确的子集并说出哪个子集更好(它们也可能相等)。
我需要找到最好的不冲突的子集。

我使用的算法:
我构建了所有子集，丢弃了不正确的子集。然后我使用 f2 作为排序函数对正确的子集进行排序，并获得第一个最佳子集(我使用快速排序算法)。就存在大量子集而言，此过程花费的时间不足。

在耗时方面是否有更好的方法？

已更新
让我们将 x_i 视为具有整数端点的区间。如果 2 个区间不相交，f1 返回 true，否则返回 false。 f2比较子集中区间的总长度。

Answer 1

本题是最大加权区间调度算法的变体。 DP算法的多项式复杂度为O(N*log(N))。与 O(N)天真的问题的空间，和O(2^G * N * logn(N)) O(2^G * N) 的复杂性这个变化问题的空间，其中 G , N分别代表组/子集(此处为 5)和间隔的总数。

如果x_i不代表区间，那么问题就出在NP上，其他解法已经证明了这一点。

先讲解最大加权区间调度的动态规划解法，再解变分问题。

• 我们得到了区间的起点和终点。让start(i) , end(i) , weight(i)区间的起点、终点、区间长度i分别。
• 根据起点的递增顺序对间隔进行排序。
• 令区间的排序顺序为1, 2, ... N .
• 让next(i)表示不与区间 i 重叠的下一个区间.
• 让我们定义一个子问题S(i)是仅考虑作业的最大加权间隔 i, i+1, ... N .
• S(1)是解决方案，它考虑了 1,2,... N 中的所有作业并返回最大加权间隔。
• 现在让我们定义S(i)递归地。

.

S(i)  = weight(i)                             if(i==N) // last job
      = max(weight(i)+S(next(i)), S(i+1)

这个解决方案的复杂度是 O(N*log(N) + N) . N*log(N)寻找 next(i)对于所有工作，以及 N用于解决子问题。空间是O(N)用于保存子问题的解决方案。

现在，让我们解决这个问题的变体。

• 让我们共同查看 X 中的所有区间。每个区间都属于集合 S_1、... S_5 中的一个。
• 让start(i) , end(i) , weight(i) , subset(i)是起点，终点，区间长度，区间的子集i分别。
• 根据起点的递增顺序对间隔进行排序。
• 令区间的排序顺序为1, 2, ... N .
• 让next(i)表示不与区间 i 重叠的下一个区间.
• 让我们定义一个子问题S(i, pending)是仅考虑作业的最大加权间隔 i, i+1, ... N和 pending是一个子集列表，我们必须从中选择一个区间。
• S(1, {S_1,...S_5})是考虑所有工作的解决方案1,...N , 为 S_1,...S_5 中的每一个选择一个区间并返回最大加权间隔。
• 现在让我们定义S(i)递归如下。

.

S(i, pending)  = 0                          if(pending==empty_set) // possible combination
               = -inf                       if(i==N && pending!={group(i)}) // incorrect combination
               = S(i+1, pending)            if(group(i) not element of pending)
               = max(weight(i)+S(next(i), pending-group(i)),
                     S(i+1, pending)

请注意，我可能遗漏了一些基本情况。

这个算法的复杂度是 O(2^G * N * logn(N))与 O(2^G * N)空间。 2^G * N表示子问题大小。

作为估计，对于 G<=10 的小值和高值 N>=100000 ，这个算法运行得非常快。对于 G>=20 的中值, N<=10000为了使该算法收敛，它也应该很低。而对于 G>=40 的高值，算法不收敛。