此活动选择递归细分中有多少子问题？

Question

Activity Selection：给定一组具有开始和结束时间的活动A，找到相互兼容的活动的最大子集。

---

我的问题

这两种方法看起来是一样的，但firstApproach中的numSubproblems是指数级的，而secondApproach中的numSubproble是O(n^2)。如果我要记住结果，那么我该如何记忆firstApproach？

---

天真的firstApproach

let max = 0
for (a: Activities):
    let B = {Activities - allIncompatbleWith(a)}
    let maxOfSubproblem = ActivitySelection(B)
    max = max (max, maxOfSubproblem+1)
return max


1. Assume a particular activity `a` is part of the optimal solution
2. Find the set of activities incompatible with `a: allIncompatibleWith(a)`.
2. Solve Activity for the set of activities: ` {Activities - allImcompatibleWith(a)}`
3. Loop over all activities  `a in Activities` and choose maximum. 

---

CLRS第16.1节基于secondApproach

Solve for S(0, n+1)

let S(i,j) = 0
for (k: 0 to n):
    let a = Activities(k)
    let S(i,k) = solution for the set of activities that start after activity-i finishes and end before activity-k starts
   let S(k,j) = solution for the set of activities that start after activity-k finishes and end before activyty-j starts.
    S(i,j) = max (S(i,k) + S(k,j) + 1)
return S(i,j)


1. Assume a particular activity `a` is part of optimal solution
2. Solve the subproblems for: 
(1) activities that finish before `a` starts 
(2) activities that start after `a` finishes.

Let S(i, j) refer to the activities that lie between activities i and j (start after i and end before j). 
Then S(i,j) characterises the subproblems needed to be solved above. ),
S(i,j) = max S(i,k) + S(k,j) + 1, with the variable k looped over j-i indices.

我的分析

firstApproach：

#numSubproblems = #numSubset of the set of all activities = 2^n.

secondApproach：

#numSubproblems = #number of ways to chooose two indicises from n indices, with repetition. = n*n = O(n^2)

这两种方法看起来是一样的，但firstApproach中的numSubproblems是指数级的，而secondApproach中的numSubproble是O(n^2)。有什么收获？他们为什么不同，甚至认为这两种方法看起来是一样的？

Answer 1

这两种方法似乎是一样的

这两种解决方案并不相同。不同之处在于搜索空间中可能存在的状态数。两种解决方案都表现出重叠的子问题和最佳的子结构。如果没有记忆，两个解决方案都会浏览整个搜索空间。

解决方案1

这是一个backtracking解决方案，其中尝试了与活动兼容的所有子集，并且每次选择活动时，候选解决方案将增加1并与当前存储的最大值进行比较。它不会洞察活动的开始时间和结束时间。主要区别在于，您的重复状态是需要确定解决方案的整个活动子集（兼容活动）（无论其开始和结束时间如何）。如果您要记住解决方案，则必须使用位掩码（或（C ++中的std::bitset）来存储活动子集的解决方案。您还可以使用std::set或其他Set数据结构。

解决方案2

由于递归关系仅解决在当前活动开始之前完成的那些活动以及在当前活动结束之后开始的那些活动，因此第二解决方案中的子问题的状态数量大大减少。请注意，此类解决方案中的状态数由元组的可能值的数量（开始时间，结束时间）确定。由于有n个活动，因此州的数量最多为n2。如果我们记住这个解决方案，我们只需要在给定的开始时间和结束时间内存储解决方案，这会自动为这个范围内的活动子集提供解决方案，无论它们是否相互兼容。

Answer 2

记忆总是不会导致多项式时间渐近时间复杂度。在第一种方法中，您可以应用memoization，但这不会减少多项式时间的时间复杂度。

What is memoization?

简单来说，memoization只不过是一个递归解决方案（自上而下），它将计算解决方案的结果存储到子问题中。如果要再次计算相同的子问题，则返回原始存储的解决方案而不是重新计算它。

Memoization in your first recursive solution

在您的情况下，每个子问题都是为子集找到最佳活动选择。因此，memoization（在您的情况下）将导致存储所有子集的最佳解决方案。

毫无疑问，memoization将通过避免重新计算之前已被“看到”的活动子集的解决方案来提高性能，但它不能（在这种情况下）将时间复杂度降低到多项式时间，因为您最终存储了子每个子集的解决方案（在最坏的情况下）。

Where memoization gives us real benefit?

另一方面，如果你看到this，其中memoization应用于fibonacci系列，你必须存储的子解决方案的总数与输入的大小是线性的。因此它将指数复杂度降低为线性。

How can you memoize the first solution

要在第一种方法中应用memoization，您需要维护子解决方案。您可以使用的数据结构是Map<Set<Activity>, Integer>，它将存储给定Set<Activity>的最大兼容活动数。在java中，equals()上的java.util.Set可以在所有实现中正常工作，因此您可以使用它。

您的第一种方法将被修改为：

// this structure memoizes the sub-solutions
Map<Set<Activity>, Integer> map; 
ActivitySelection(Set<Activity> activities) {
    if(map contains activities)
        return map.getValueFor(activities);
    let max = 0
    for (a: activities):
        let B = {Activities - allIncompatbleWith(a)}
        let maxOfSubproblem = ActivitySelection(B)
        max = max (max, maxOfSubproblem+1)
    map.put(activities, max)
    return max
}

更轻松的说明：

第二个解决方案（CLRS 16.1）的时间复杂度将是O(n^3)而不是O(n^2)。你必须为i，j和k设置3个循环。这个解决方案的空间复杂性是O(n^2)。