7

目前我正在阅读 Skiena 的“算法设计手册”（嗯，开始阅读）

他提出了一个他称之为“电影调度问题”的问题：

问题：电影调度问题

输入：线上的一组 n 个区间。

输出：可以从 I 中选择的相互不重叠区间的最大子集是多少？

例子：（每条虚线是一部电影，你想找到一个电影数量最多的集合）

                      ----a---
-----b----    -----c---    ---d---
        -----e---  -------f---
            --g--  --h--

我想解决这个问题的算法是这样的：我可以扔掉“最坏的罪犯”（与大多数其他电影相交），直到没有最坏的罪犯（零交叉）。我看到的唯一问题是，如果有平局（比如两部不同的电影，每部都与其他 3 部电影相交），我扔掉哪一部有关系吗？

基本上我想知道如何将这个想法变成“数学”以及如何证明它是正确/不正确的。

4

3 回答 3

12

算法不正确。让我们考虑以下示例：

反例

           |----F----|       |-----G------| 

        |-------D-------|  |--------E--------|

|-----A------|    |------B------|    |------C-------|

你可以看到有一个大小至少为 3 的解，因为你可以pick A, B and C。

首先，让我们计算每个区间的交叉点数：

A = 2    [F, D]
B = 4    [D, F, E, G]
C = 2    [E, G]
D = 3    [A, B, F]
E = 3    [B, C, G]
F = 3    [A, B, D]
G = 3    [B, C, E]

现在考虑运行你的算法。在第一步中，我们删除B，因为它与最多数量的 invervals 相交，我们得到：

           |----F----|       |-----G------| 

        |-------D-------|  |--------E--------|

|-----A------|                      |------C-------|

很容易看出，现在{A, D, F}你只能选择一个，因为每一对都相交。与 的情况相同{G, E, C}，所以删除后B，最多可以选择一个 from{A, D, F}和最多一个 from {G, E, C}，得到总和2，小于 的大小{A, B, C}。

结论是，在删除B与最多数量的invervals相交后，您无法获得最大数量的非相交电影。

正确的解决方案

这个问题是众所周知的，一种解决方案是选择首先结束的区间，删除与其相交的所有区间并继续直到没有要检查的区间。这是一个贪心方法的例子，你可以找到或开发一个证明它是正确的。

于 2013-09-13T00:22:50.093 回答
2

对我来说，这看起来像是一个动态编程问题：

定义以下函数：

sched(t) = best schedule starting at time t
next(t) = set of movies that start next after time t
len(m) = length of movie m

next返回一个集合，因为可能有多个电影同时开始。

那么sched应该定义如下：

sched(t) = max { 1 + sched(t + len(m)), sched(t+1) } where m in next(t)

此递归函数m从中选择一部电影next(t)并比较可能包含或不包含的最大集合m。

调用sched您的第一部电影的时间，您将获得最佳集合的大小。获得最佳集合本身只需要一些额外的逻辑来记住您在每次调用时选择了哪些电影。

如果您使用记忆化，我认为这种递归（与迭代相反）算法在 O(n^2) 中运行，其中 n 是电影的数量。

这是正确的，但我必须查阅我的算法教科书才能给你一个明确的证明，但希望这个算法能直观地理解为什么它是正确的。

于 2013-09-13T00:44:45.480 回答
0 
# go through the database and create a 2-D matrix indexed a..h by a..h.  Set each
# element of the matrix to 1 if the row index movie overlaps the column index movie.

mtx = []
for i in range(8):
    column = []
    for j in range(8):
        column.append(0)
    mtx.append(column)

# b <> e
mtx[1][4] = 1
mtx[4][1] = 1

# e <> g
mtx[4][6] = 1
mtx[6][4] = 1

# e <> c
mtx[4][2] = 1
mtx[2][4] = 1

# c <> a
mtx[2][0] = 1
mtx[0][2] = 1

# c <> f
mtx[2][5] = 1
mtx[5][2] = 1

# c <> g
mtx[2][6] = 1
mtx[6][2] = 1

# c <> h
mtx[2][7] = 1
mtx[7][2] = 1

# d <> f
mtx[3][5] = 1
mtx[5][3] = 1

# a <> f
mtx[0][5] = 1
mtx[5][0] = 1

# a <> d
mtx[0][3] = 1
mtx[3][0] = 1

# a <> h
mtx[0][7] = 1
mtx[7][0] = 1

# g <> e
mtx[4][7] = 1
mtx[7][4] = 1

# print out contstraints
for line in mtx:
    print line

# keep track of which movies are still allowed
allowed = set(range(8))

# loop through in greedy fashion, picking movie that throws out the least
# number of other movies at each step
best = 8
while best > 0:
    best_col = None
    best_lost = set()
    best = 8  # score if move does not overlap with any other
    # each step, only try movies still allowed
    for col in allowed:
        lost = set()
        for row in range(8):
            # keep track of other movies eliminated by this selection
            if mtx[row][col] == 1:
                lost.add(row)
        # this was the best of all the allowed choices so far
        if len(lost) < best:
            best_col = col
            best_lost = lost
            best = len(lost)
    # there was a valid selection, process
    if best_col > 0:
        print 'watch movie: ', str(unichr(best_col+ord('a')))
        for row in best_lost:
            # now eliminate the other movies you can't now watch
            if row in allowed:
                print 'throwing out: ', str(unichr(row+ord('a')))
                allowed.remove(row)
        # also throw out this movie from the allowed list (can't watch twice)
        allowed.remove(best_col)

# this is just a greedy algorithm, not guaranteed optimal!
# you could also iterate through all possible combinations of movies
# and simply eliminate all illegal possibilities (brute force search)
于 2013-09-13T01:07:25.383 回答