贪心算法:区间着色
Greedy algorithm: Interval coloring
在间隔调度中,算法是选择最早的结束时间。但在间隔着色中,前者不起作用。是否有关于为什么选择最早完成时间不适用于间隔着色的示例或解释?
区间着色问题是:给定一组区间,我们要着色
所有间隔,以便给定相同颜色的间隔不相交,目标是尽量减少使用的颜色数量。这可以被认为是区间划分问题(如果它更有意义的话)
我说的区间调度问题是:如果你去一个主题公园,演出很多,每场演出的开始和结束时间就是一个区间,你就是资源。您想参加尽可能多的节目。
在找到示例之前,这只是玩弄图片的一种情况。我画的第一张显示问题的图片有以下分区:
A: (0, 2) (3, 7)
B: (1, 4) (5, 6)
图片看起来像这样:
-- ----
--- -
但是寻找最早的停止时间规则会产生以下颜色:
A: (0, 2) (5, 6)
B: (1, 4)
C: (3, 7)
这是哪个分区:
-- -
---
----
所以这个贪婪规则在这个例子中不是最优的。
如果你只需要一个关于着色的贪婪算法的反例,@btilly 已经提供了一个。
我正在尝试给出使其更直观的理由。
首先,对于调度问题,确实可以证明贪心算法是有效的。思路是这样的:
如果我不选择结束时间最早的节目,我无法获得更好的结果,让我们看看。
如果有两个区间A、B,且A的结束时间较早,则B是
- 开始时间晚于A的结束时间,那么完全不冲突,为什么不两者都冲突?
- 开始时间早于A的结束时间,有冲突,我只能选择A OR B,但是A结束的时间早一些,之后有更多的机会选择更多的节目,不是吗?
然而,对于着色问题,它完全是另一类问题。
您被迫选择所有间隔,而问题的答案是所有时间的最大冲突间隔数。
试着这样想:一直以来,最多同时进行 5 场考试,您至少要使用 5 个教室(颜色),对吗?
所以我们不能通过选择最早完成时间找到这个,时间没有告诉你任何东西。
它可能会帮助您决定是否选择此间隔(如在调度问题中),但不能告诉您所需的 MINIMUM # 资源。它们只是不同类别的问题。
已编辑:
重新阅读 OP 的问题后,据我所知,这里有更多关于着色问题的详细信息。
定义 depth
为所有时间的最大冲突数。逻辑上我们知道 depth
是下界,但我们必须证明它也是上限(通过反证法)。
证明
证明需要SORT INTERVALS BY START TIME IN ASCENDING ORDER 或 FINISH TIME IN DESENDING ORDER,如下所示:
假设区间集合depth
为d
,答案大于d
。让 x
成为我们处理的第一个使用资源 d+1
的区间,
由于处理顺序是按开始时间升序排列的,也就是说至少有d
个间隔在x
之前开始并且与x有冲突,那么集合的depth
至少是d+1
,自相矛盾。所以d
= depth
也是答案的上界,是区间着色的最优答案。
请注意,如果您按开始时间降序或结束时间升序排序,则不能使用相同的推理。
概念/目标
现在我们知道深度就是答案,我们必须找到它。从概念上讲,无论您是使用开始时间还是结束时间,升序还是降序来查找,所有选项都可以为您提供间隔集的深度。
实施考虑
然而,为了实现,如果你必须在 O(n lg n) 中找到它,你将不得不使用 GREEDY METHOD + 一些数据结构,这可能需要间隔有某种排序。不过那是另外一回事了,是为了实现,概念上的,没关系,你只想找到区间集的深度。
TL;DR
对于区间调度问题,贪心法本身确实已经是最优策略;而对于区间着色问题,贪心法只能帮助证明深度是答案,并且可以在实现中用于查找深度(但不是@btilly 的反例中所示的方式)
实际上,您看到的根据开始时间对输入进行排序的算法版本可能不适用于结束时间。这里的关键点在于,在算法中,当有不止一种颜色可用时,规则是任意分配。上面的反例说明了这一点。
如果您想改为使用完成时间的顺序,则需要对算法进行一项更改。让我们假设对于每个现有的颜色 i,在所有由 i 着色的区间中,最大的完成时间是 F_i。那么当有不止一种颜色可用时,规则是用具有最大 F_i 的可用颜色为区间着色。
如果您进行此更改,该算法将适用于完成时间的顺序。我运行 模拟并为此写了完成的正式证明。
直觉很简单,因为排序是按完成时间排序的,您不希望它占用太多资源。虽然可能有两种颜色可用,但您希望使用小于 "expensive" 的颜色来为下一个间隔保存 space,该间隔实际上可能在当前颜色之前开始并在当前颜色之后结束。
让我们用上面的例子,
答: (0, 2) (5, 6)
乙: (1, 4)
C: (3, 7)
这不起作用,因为在分配 (5,6) 时,选择了 A,但是,如果按照我的算法版本,我们知道 A 的结尾是 2,B 的结尾是 4,所以你选择 B,最大的结尾。这为 (3,7) 节省了比 (5,6) 早开始但晚结束的位置。
按开始时间排序不存在此类问题,因为按开始时间排序,你知道在当前作业之后,不会有其他作业更早开始,所以你不需要保存资源。
注意,虽然这可能是使完成时间顺序起作用的一种方法,但 运行ning 时间比具有开始时间顺序的原始算法要大。因为您必须 运行 遍历所有颜色才能找到不仅可用而且结尾最大的颜色。
在间隔调度中,算法是选择最早的结束时间。但在间隔着色中,前者不起作用。是否有关于为什么选择最早完成时间不适用于间隔着色的示例或解释?
区间着色问题是:给定一组区间,我们要着色 所有间隔,以便给定相同颜色的间隔不相交,目标是尽量减少使用的颜色数量。这可以被认为是区间划分问题(如果它更有意义的话)
我说的区间调度问题是:如果你去一个主题公园,演出很多,每场演出的开始和结束时间就是一个区间,你就是资源。您想参加尽可能多的节目。
在找到示例之前,这只是玩弄图片的一种情况。我画的第一张显示问题的图片有以下分区:
A: (0, 2) (3, 7)
B: (1, 4) (5, 6)
图片看起来像这样:
-- ----
--- -
但是寻找最早的停止时间规则会产生以下颜色:
A: (0, 2) (5, 6)
B: (1, 4)
C: (3, 7)
这是哪个分区:
-- -
---
----
所以这个贪婪规则在这个例子中不是最优的。
如果你只需要一个关于着色的贪婪算法的反例,@btilly 已经提供了一个。
我正在尝试给出使其更直观的理由。
首先,对于调度问题,确实可以证明贪心算法是有效的。思路是这样的:
如果我不选择结束时间最早的节目,我无法获得更好的结果,让我们看看。
如果有两个区间A、B,且A的结束时间较早,则B是
- 开始时间晚于A的结束时间,那么完全不冲突,为什么不两者都冲突?
- 开始时间早于A的结束时间,有冲突,我只能选择A OR B,但是A结束的时间早一些,之后有更多的机会选择更多的节目,不是吗?
然而,对于着色问题,它完全是另一类问题。
您被迫选择所有间隔,而问题的答案是所有时间的最大冲突间隔数。
试着这样想:一直以来,最多同时进行 5 场考试,您至少要使用 5 个教室(颜色),对吗?
所以我们不能通过选择最早完成时间找到这个,时间没有告诉你任何东西。
它可能会帮助您决定是否选择此间隔(如在调度问题中),但不能告诉您所需的 MINIMUM # 资源。它们只是不同类别的问题。
已编辑:
重新阅读 OP 的问题后,据我所知,这里有更多关于着色问题的详细信息。
定义 depth
为所有时间的最大冲突数。逻辑上我们知道 depth
是下界,但我们必须证明它也是上限(通过反证法)。
证明
证明需要SORT INTERVALS BY START TIME IN ASCENDING ORDER 或 FINISH TIME IN DESENDING ORDER,如下所示:
假设区间集合depth
为d
,答案大于d
。让 x
成为我们处理的第一个使用资源 d+1
的区间,
由于处理顺序是按开始时间升序排列的,也就是说至少有d
个间隔在x
之前开始并且与x有冲突,那么集合的depth
至少是d+1
,自相矛盾。所以d
= depth
也是答案的上界,是区间着色的最优答案。
请注意,如果您按开始时间降序或结束时间升序排序,则不能使用相同的推理。
概念/目标
现在我们知道深度就是答案,我们必须找到它。从概念上讲,无论您是使用开始时间还是结束时间,升序还是降序来查找,所有选项都可以为您提供间隔集的深度。
实施考虑
然而,为了实现,如果你必须在 O(n lg n) 中找到它,你将不得不使用 GREEDY METHOD + 一些数据结构,这可能需要间隔有某种排序。不过那是另外一回事了,是为了实现,概念上的,没关系,你只想找到区间集的深度。
TL;DR
对于区间调度问题,贪心法本身确实已经是最优策略;而对于区间着色问题,贪心法只能帮助证明深度是答案,并且可以在实现中用于查找深度(但不是@btilly 的反例中所示的方式)
实际上,您看到的根据开始时间对输入进行排序的算法版本可能不适用于结束时间。这里的关键点在于,在算法中,当有不止一种颜色可用时,规则是任意分配。上面的反例说明了这一点。
如果您想改为使用完成时间的顺序,则需要对算法进行一项更改。让我们假设对于每个现有的颜色 i,在所有由 i 着色的区间中,最大的完成时间是 F_i。那么当有不止一种颜色可用时,规则是用具有最大 F_i 的可用颜色为区间着色。
如果您进行此更改,该算法将适用于完成时间的顺序。我运行 模拟并为此写了完成的正式证明。
直觉很简单,因为排序是按完成时间排序的,您不希望它占用太多资源。虽然可能有两种颜色可用,但您希望使用小于 "expensive" 的颜色来为下一个间隔保存 space,该间隔实际上可能在当前颜色之前开始并在当前颜色之后结束。
让我们用上面的例子, 答: (0, 2) (5, 6) 乙: (1, 4) C: (3, 7) 这不起作用,因为在分配 (5,6) 时,选择了 A,但是,如果按照我的算法版本,我们知道 A 的结尾是 2,B 的结尾是 4,所以你选择 B,最大的结尾。这为 (3,7) 节省了比 (5,6) 早开始但晚结束的位置。
按开始时间排序不存在此类问题,因为按开始时间排序,你知道在当前作业之后,不会有其他作业更早开始,所以你不需要保存资源。
注意,虽然这可能是使完成时间顺序起作用的一种方法,但 运行ning 时间比具有开始时间顺序的原始算法要大。因为您必须 运行 遍历所有颜色才能找到不仅可用而且结尾最大的颜色。