加权区间调度解决方案构建

Question

我正在跟随Tardos的书学习动态规划。在加权区间调度问题的解决方案构建部分，我有一个疑问。
建议使用相同的成本数组，而不是使用另一个数组来存储解决方案，可以这样做：

Find-Solution(j)
 if  j = 0 then 
   output nothing
 else
   If Vj + M[p(j)] >= M[j-1] then
    output j together with the result of find-solution(p(j))
 else
   output find-solution(j-1)
 endif

我的问题是找到p(j)，应该花费O(n)时间，我们可以使这些递归调用在O(n)时间内完成，从而使这个算法的时间复杂度为O(n^2)，但书中声称这是O(n)。 此外，我们正在进行与计算成本数组m相同的计算。有没有一种方法可以消除这个问题。如果我想使用一个数组来存储解决方案，我应该在其中存储什么？

- ocwirk

Answer 1

找到 p[1..j] 的时间复杂度为 O(n log n)：

• 需要计算 1..j 中每个区间的 p[1..j]：O(n)
• 对于每个区间，需要使用二分查找找到最右侧相互兼容（不重叠）的区间：O(log n)

由于 O(n) 和 O(log n) 都是增长的（当 n 增加时），我们必须将它们的乘积作为最终复杂度，这就是为什么找到所有 p[1..j] 的时间复杂度为 O(n log n)。

现在，在查找解决方案时，它的时间复杂度为 O(n)，因为它假设预先计算了值。这很合理，因为我们想要集中精力在此方法中的 OPT 遍历上，并且不关心如何计算 p(j)。

最后，当我们有几个大 O 计算，并且需要找到它们的总和时，支配函数定义了总复杂度。在我们的情况下，如果：

• 找到 p[1..j] 的时间复杂度为 O(n log n)
• 使用 find-solution() 找到实际区间的时间复杂度为 O(n)
• 按完成时间排序区间的时间复杂度为 O(n log n)
• 迭代构建 OPT[1..j] 的时间复杂度为 O(n)

它们的总和将由 O(n log n) 支配：

O(n log n) + O(n) + O(n log n) + O(n) = O(n log n)

因此，整个算法的性能为 O(n log n)。

- Victor Farazdagi

Answer 2

我认为他们的分析假设您预先计算了所有p的值，在这种情况下，该方法的运行时间确实为O(n)。不过，计算p的值将需要O(n log n)的时间。

请参见如何计算p的方法：http://www.cs.cornell.edu/courses/cs4820/2010su/handouts/computation-of-p-j.pdf 要了解有关该算法的类似分析，请参见：http://www.cs.uiuc.edu/class/fa08/cs473/Lectures/lecture12.pdf。在那里，它还声称计算需要O(n)的时间。但是最后他对总运行时间的分析包括计算p在内，其时间复杂度为O(n log n)。

- ryaner

---

嗯，那个预计算的东西看起来是正确的。谢谢你的澄清。 - ocwirk

Answer 3

import collections
import bisect
import time
from datetime import datetime

"""
Weighted Interval scheduling algorithm.
Runtime complexity: O(n log n)
"""

class Interval(object):
    '''Date weighted interval'''

    def __init__(self, title, start, finish):
        self.title = title
        self.start = int(start)
        self.finish = int(finish)
        self.weight = self.finish - self.start

    def __repr__(self):
        return str((self.title, self.start, self.finish, self.weight))


def compute_previous_intervals(I):
    '''For every interval j, compute the rightmost mutually compatible interval i, where i < j
       I is a sorted list of Interval objects (sorted by finish time)
    '''
    # extract start and finish times
    start = [i.start for i in I]
    finish = [i.finish for i in I]
    print start
    print finish
    p = []
    for j in xrange(len(I)):
        i = bisect.bisect_right(finish, start[j]) - 1  # rightmost interval f_i <= s_j
        print j, i
        p.append(i)

    return p

def schedule_weighted_intervals(I):
    '''Use dynamic algorithm to schedule weighted intervals
       sorting is O(n log n),
       finding p[1..n] is O(n log n),
       finding OPT[1..n] is O(n),
       selecting is O(n)
       whole operation is dominated by O(n log n)
    '''

    I.sort(lambda x, y: x.finish - y.finish)  # f_1 <= f_2 <= .. <= f_n
    p = compute_previous_intervals(I)

    # compute OPTs iteratively in O(n), here we use DP
    OPT = collections.defaultdict(int)
    OPT[-1] = 0
    OPT[0] = 0
    for j in xrange(1, len(I)):
        OPT[j] = max(I[j].weight + OPT[p[j]], OPT[j - 1])

    # given OPT and p, find actual solution intervals in O(n)
    O = []
    def compute_solution(j):
        if j >= 0:  # will halt on OPT[-1]
            if I[j].weight + OPT[p[j]] > OPT[j - 1]:
                O.append(I[j])
                compute_solution(p[j])
            else:
                compute_solution(j - 1)
    compute_solution(len(I) - 1)

    # resort, as our O is in reverse order (OPTIONAL)
    O.sort(lambda x, y: x.finish - y.finish)

    return O

if __name__ == '__main__':
    I = []
    I.append(Interval("Summer School" , "2", "10"))
    I.append(Interval("Semester 1" , "1", "9"))
    I.append(Interval("Semester 2" , "11", "15"))
    I.append(Interval("Trimester 1" , "15", "20"))
    I.append(Interval("Trimester 2" , "14", "21"))
    I.append(Interval("Trimester 3" , "4", "11"))
    I.append(Interval("Trimester 4" , "15", "22"))
    O = schedule_weighted_intervals(I)
    print O

- user3388770