贪心法(II) 复杂任务调度 +++++++++++++++++++++++++++++++ 上一节介绍了贪心法最简单的一个例子，单机任务调度问题。这一节我们将看两个更加复杂一点的任务调度问题，:strong:`区间调度问题`\ 和\ :strong:`双机调度问题`\ 。我们将会看到，区间调度也适用贪心法求解，但是双机调度（乃至多机调度）则无法用贪心法求得最优解。 区间调度问题（洛谷P1803） ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ :strong:`区间调度问题`\ ，有时候也会以\ :strong:`活动安排问题`\ 、:strong:`教室安排问题`\ 等形式出现，其实它们都是同一个问题。 区间调度问题也是在一台机器上调度 :math:`n` 个任务，机器同样不能同时运行多个任务。和通常的单机调度不同，区间调度问题的输入数据是一系列的时间区间 :math:`[s_i,f_i),i=1,2,\dots,n`，:math:`s_i` 表示每个任务的开始时间，:math:`f_i` 表示结束时间，故而这个问题被称为区间调度问题。时间区间左闭右开意味着机器可以在运行完前一个任务之后立即启动下一个任务，中间无需停顿。这些区间相互之间是会有所重叠的。 显然，只要有两个任务的时间区间有重叠，这两个任务就只能选择调度其中一个，放弃另一个。所以区间调度的调度目标是选出其中一部分任务交给机器去运行，选中的任务互相之间没有时间重叠，而且被选中运行的任务数量要尽可能的多。 例如我们有11个任务以供调度，任务的开始时间、结束时间已知。为了更直观地观察任务之间的时间关系，我们画出甘特图： .. image:: ../../images/412_scheduling.png 仔细想一想，如果我们想要让更多的任务得到运行，那么我们就必须要让每一个任务运行完成后剩余的时间足够多。这就意味着每次调度的时候，我们都需要尽量先调度那些结束时间早的任务。这就是区间调度问题的贪心策略，具体实现的过程只有两步： 1. 对所有待调度的任务按各自的结束时间进行从小到大的升序排序。 2. 循环调度任务：第一个应该被调度的任务一定是排完序后的第一个任务，以后每一次调度，设上一个任务为 :math:`i` 号任务，那么下一个就是它后面的第一个开始时间不早于 :math:`f_i` 的任务，如此循环下去直到找不到下一个可调度任务为止，调度就完毕了。 按照这个策略，请手动排一排上面示例中的11项任务并完成调度，看看结果是不是图中标红的4项，也就是调度 :math:`\{2,6,9,11\}`\ ，再尝试一下还能不能找出可以完成更多任务的调度来？ .. admonition:: 练习 设输入的数据都是 ``int`` 取值范围之内的整数，编写一个区间调度的程序。 .. index:: 【凌乱的yyy】, 〖洛谷P1803〗 下面我们来看一个区间调度的例题：凌乱的yyy（洛谷P1803） **题目背景** 快noip了，yyy很紧张！ **题目描述** 现在各大oj上有n个比赛，每个比赛的开始、结束的时间点是知道的。 yyy认为，参加越多的比赛，noip就能考的越好（假的） 所以，他想知道他最多能参加几个比赛。 由于yyy是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。 **输入格式** 第一行是一个整数 :math:`n`\ ，接下来 :math:`n` 行每行是2个整数 :math:`a_i,b_i,(a_i \lt b_i)`\ ，表示比赛开始、结束的时间。 **输出格式** 一个整数最多参加的比赛数目。 **输入输出样例** 输入： .. code-block:: none 3 0 2 2 4 1 3 输出： .. code-block:: none 2 **说明/提示** 对于 :math:`20\%` 的数据，:math:`n\le10`\ ； 对于 :math:`50\%` 的数据，:math:`n\le1000`\ ； 对于 :math:`70\%` 的数据，:math:`n\le100000`\ ； 对于 :math:`100\%` 的数据，:math:`n\le1000000,0\le a_i \lt b_i \le 1000000`\ 。 **题解分析** 这就是一个典型的区间调度问题，和前面的算法完全没有任何区别，需要注意的只是编程上的一些技巧。每一场比赛由开始时间 :math:`a_i` 和结束时间 :math:`b_i` 两个数表示，所以定义一个结构来保存数据是显而易见的选择。程序中要实现对所有这些比赛按结束时间排序，用的编程技巧和上一节所述的没有什么太大区别。请思考一下，本题在排序的时候要不要带着比赛编号一起排？ 下面是具体的代码： .. literalinclude:: ../../codes/412_p1803.cpp :language: c++ 下面是得到的AC结果截图： .. image:: ../../images/412_p1803_1.png 我在这个题上做了一个有趣的实验，把所有的输入输出从C++的IO流改成传统的C标准IO ``scanf()/printf()``\ ，其他完全不变。再次提交代码，得到的AC结果如下： .. image:: ../../images/412_p1803_2.png 最后两个数据量为百万级的测试点，用C标准IO比用IO流快了近一半！足可见当输入数据的量非常大的时候，用传统的 ``cstdio`` 库函数确实要比用C++新的流式IO快很多。但也不能说IO流就无法满足竞赛的要求，绝大部分情况下使用IO流是不会造成TLE的。 双机调度问题 ^^^^^^^^^^^^ 我们前面已经讲过单机调度问题，知道了单机调度问题可以用贪心法求得最优解。但是如果有两台机器可以同时运行，或者一台机器可以同时运行两个任务，那么问题就变成了更为复杂的\ :strong:`双机调度问题`\ 。如果机器数量更多，或者一台机器可同时运行任务的通道数更多，那么就进一步升级为\ :strong:`多机调度问题`\ 。双机调度只是多机调度的一个特例，机器数量从二到更多的增加只是量变，但从单机到双机的变化却属于质的改变。我们很快就可以看到，一旦机器数量从一增加到二，问题就变得无法用贪心法求最优解了。 双机调度问题的一般性描述是：给出 :math:`n` 项任务 :math:`\{1,2,\dots,n\}`\ ，其中任务 :math:`i` 的运行时长为整数 :math:`t_i,i=1,2,\dots,n`\ 。将所有任务分成两部分 :math:`\{i_1,i_2,\dots,i_p\}` 和 :math:`\{j_1,j_2,\dots,j_q\}`\ ，\ :math:`p+q=n`\ ，各自调度到两台相同的机器同时开始运行。从0时刻开始计时，以较晚结束运行的机器的停机时间为最终的完成时间。求一个最优的调度，使得最终完成时间最短。 例如，任务数量为 :math:`n=6`\ ，各自的运行时长为 :math:`t_1=3,t_2=10,t_3=6,t_4=2,t_5=1,t_6=7`\ 。 对于这样一个比较简单的任务集，我们可以人为地进行调度尝试，并不太难就可以发现一个最优解：两台机器上调度的任务分别为 :math:`\{3,5,6\}` 和 :math:`\{1,2,4\}`\ 。前一台机器的总运行时长为 :math:`T_1=6+1+7=14`\ ，后一台为 :math:`T_2=3+10+2=15`\ ，最终完成时间为二者中较大的15。这个解已经是最优解了，因为所有任务的运行总时长为29，对它进行最均匀的二分就是29=14+15，其他任何分法都不会比它更好了。 不难发现这套示例数据还存在另外一个最优解{1,2,5}和{3,4,6}，它也能把总时间29分割成最为均衡的14和15。可见双机调度问题的最优解并不一定是唯一的。 总结上面的过程，不难归纳出一个获取双机调度最优解的方法，一共分三步： 1. 计算出所有任务的总耗时 :math:`T = t_1+t_2+\cdots+t_n`\ ，并计算出两台机器上的最佳运行时间分配，即均匀地二分总时间：:math:`T_1=\lfloor T/2 \rfloor`\ ，:math:`T_2=T-T_1`\ 。这样，如果总时间 :math:`T` 是偶数，那么有 :math:`T_1=T_2=T/2`\ ；如果是奇数，那么 :math:`T_2=T_1+1`\ 。 2. 完成第一台机器上以 :math:`T_1` 为目标的任务调度。即挑选合适的一部分任务，使它们的运行时间之和最大限度地接近但不超过 :math:`T_1`\ ，当然最好是恰好等于 :math:`T_1`\ 。 3. 把剩余的任务调度给第二台机器。 按照上面的三步法，我们就可以确保获得一个双机调度问题的最优解。 可是事情并没有想象的那样简单，问题出在第2步，怎样才能做到让调度给第一台机器的任务满足“运行时间之和最大限度地接近但不超过，最好是恰等于 :math:`T_1`\ ”。这样一个目标任务可以通过贪心法获得吗？想想似乎找不出这样的贪心策略。事实上也确实没有，因为仔细看一看这个要求，其实它是要完成一个“0-1背包问题”！你看出来了吗？这里背包的最大承重量为 :math:`T_1`\ ，所有任务就是要放入背包的物品，只不过每一项物品的重量和价值相等，都是 :math:`t_i`\ 。 所以，双机调度问题是一个穿着任务调度马甲的0-1背包问题。我们已经知道，它是一个NP难题，它没有贪心解法。这个问题只能留待日后等我们学会了背包问题的动态规划解法之后才能解决了。 .. admonition:: 补充 事实上，用贪心算法还是可以求出双机调度，乃至多机调度的近似解的。这个近似解的优秀程度和任务运行时长的分布均匀程度有关。如果所有任务的运行时长 :math:`t_i` 在一定的范围内均匀分布，而且任务数量很多的时候，那么这个近似解可能会相当接近甚至就是最优解。方法很简单，S形轮流分配任务，具体如下： 1. 假设要在 :math:`m` 台机器上调度总共 :math:`n` 项任务，:math:`n\gg m`\ （数学符号 :math:`\gg` 表示远大于，:math:`\ll` 表示远小于）。 2. 首先将所有任务按运行时长由小到大排序。 3. 按照短任务的优先的贪心策略，按机器号 :math:`1,2,\dots,m` 的顺序先调度完第 :math:`1` 轮 :math:`m` 项任务，每台机器一项。 4. 然后把机器顺序颠倒过来，按 :math:`m,m-1,\dots,1` 的顺序调度第 :math:`2` 轮 :math:`m` 项任务，每台机器一项。 5. 重复上述过程，每一轮任务调度完后颠倒调度时机器的顺序，直到所有任务分配完毕。 例如我们的示例中，按此方法调度的结果为 :math:`\{5,3,6\}` 和 :math:`\{4,1,2\}`\ ，恰好是一个最优解。 实践证明，这种简单的近似算法往往非常有效。虽然它并不能保证获得最优解，但它给出的解经常很接近甚至就是最优解。算法编程虽然不能用这种方法，但这种考虑问题的思路值得学习掌握。