电影调度_问题_

Question

目前我正在阅读Skiena的"算法设计手册"(好了,开始阅读)

他问一个他称之为"电影调度问题"的问题:

问题:电影调度问题

输入:线上n个区间的集合I.

输出:可以从I中选择的相互非重叠区间的最大子集是什么？

示例:(每条虚线都是一部电影,您想要找到电影数量最多的一组)

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

我想要解决它的算法是这样的:我可以抛出"最坏的罪犯"(与大多数其他电影相交),直到没有最严重的罪犯(零交叉点).我看到的唯一问题是,如果有一个平局(比如两部不同的电影,每部电影与其他3部电影相交),我扔出哪一部电影是否重要？

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

Answer 1

算法不正确.让我们考虑以下示例:

反

           |----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,你最多可以选择一个{A, D, F},最多一个{G, E, C},以获得总数2,小于的大小{A, B, C}.

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

正确的解决方案

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