算法园地|南京大学陈道蓄教授：调度问题中的算法
文章图片
文章图片
陈道蓄
南京大学教授、博士生导师
曾任南京大学计算机系主任 。 近年来积极投入计算机专业基础课改革以及计算思维普及 ， 因此获得中国计算机学会杰出教育奖与南京大学教学终身成就奖 。
说到“调度” ， 人们往往会想到交通运输部门的运行安排 ， 也会想到企业中复杂的生产任务安排 。 其实 ， 日常生活中也经常面临着多个事项需要合理安排；只不过任务数不大 ， 也不涉及明显的经济指标限制 ， 人们凭经验就足以应付 ， 很少会联想到“算法” 。 当需要解决的任务数增加 ， 且包含相互依赖关系时 ， 算法可以帮助我们顺利有效地完成任务 。
单纯依赖关系约束下的任务调度
我们从仅考虑任务间的依赖约束开始 。 如果任务X只能在另外某个任务Y完成后才能开始 ， 我们就说X依赖Y 。 下面来看一个简单的例子 。
同学们打算在教室里组织一场联欢活动 ， 还准备自己动手包饺子 。 他们拟定了一张准备工作任务表 ， 包含所有任务事项、每项任务耗时、任务间依赖关系（注意：只需列出直接依赖关系 ， 而间接依赖关系自然地隐含在其中） 。 管理上通常将这些任务的集合称为一个“项目” 。 任务列表见表1 。
文章图片
表1为准备一个联欢活动涉及的各项任务及其关系示例
有些任务之间没有依赖关系 ， 执行顺序无关紧要 ， 如果有多个执行者 ， 这样的任务就可以并行 。 这里说的“调度” ， 就是要给每项任务分配一个不同的序号 ， 表示它们执行的顺序 ， 满足：如果任务X依赖任务Y ， 则X的序号就要大于Y的序号；如果两个任务之间没有依赖关系 ， 则对它们的序号关系没有要求 。 从数学上看 ， 原来所有任务间的依赖关系确定了一个“偏序” ， 即并非任意两个任务都必须“有先后”（称为“可比”） 。 调度就是要在此基础上生成一个“全序” ， 即任何两个任务皆“可比” ， 对任意两个原来就“可比”的任务 ， 新关系与原关系保持一致 。 换句话说 ， 如果按照这个序号串行执行 ， 一定满足原来要求的依赖关系 。 这个问题被称为“拓扑排序”问题 。 读者应该注意到 ， 如果只要解决拓扑排序问题 ， 我们并不需要考虑上述例子中每项子任务的耗时 。
我们可以建立一个有向图模型 。 图中每个节点表示一个任务 ， 节点X和Y之间存在从X到Y的有向边（X→Y）当且仅当对应的任务X直接依赖于任务Y 。 上述例子的图模型如图1所示 。 图中节点名称采用表1中的任务名称 。 我们暂时不考虑任务的耗时 。
在这个模型上解决拓扑排序问题的思路非常简单 。 我们要给每个节点分配一个序号 ， 这需要遍历所有节点 。 根据问题要求 ， 如果任务X依赖任务Y（无论是直接还是间接） ， 分配给节点X的序号必须大于Y的序号 。 在图模型中存在的任意一个简单有向通路表明任务i-1依赖任务i（1＜i≤k） 。 这条通路可以看作一条“依赖链” ， 显然通路中的节点被分配的序号是严格递减的 。
文章图片
图1与表1示例数据对应的有向图
图节点遍历常用算法有两种：深度优先与广度优先 。 我们在本系列文章中前面讨论走迷宫算法时介绍过深度优先算法（DFS） 。 它的基本步骤如下（这里假设从起始点一定可通达所有节点）：①选择一个起始点 ， 并将其作为第一个“当前节点” ， 设置状态为“已访问” 。 ②如果当前节点所有的相邻节点都是“已访问”状态 ， 结束从当前节点开始的遍历子过程 ， 退出（回溯） 。 如果当前节点就是起始点 ， 则整个遍历完成 。 ③取当前节点相邻节点中的一个尚未访问过的节点w作为新的“当前节点” ， 设置状态为“已访问” ， 从w开始递归执行本过程（即上述第2步） 。
在图1中从L开始执行深度优先搜索过程 ， 可能产生的一个访问序列如下：L ， K ， H ， F ， C ， A(A ， 回溯)(C ， 回溯)(F ， 回溯)(H) ， E(E ， 回溯)(H) ， B(B ， 回溯)(H ， 回溯)(K) ， G ， D(D ， 回溯)(G ， 回溯)(K回溯)(L) ， J(J回溯)(L ， 结束） 。 它对应表2中的“访问序” 。 具体的访问序列与当前节点的所有相邻节点被访问的次序有关（由算法实现决定 ， 即上述算法第3步节点w的选取） 。 这对后面生成的全序有影响 ， 但对满足问题的约束条件没有影响 。
下面来看“拓扑序”的确定 。 在深度优先搜索过程中 ， 任一节点在回溯后就再也不会被访问了 ， 也就是它所依赖的节点都已经访问过了 ， 因此如果我们在其即将回溯前给它分配拓扑序号 ， 且号码值从1开始依次加1 ， 则上述过程给出的拓扑序号与任务名称的对应关系如表2中的第三行所示 。 读者容易验证这个次序满足表1中的任务依赖要求 ， 即按照这个序号 ， 先做“1”（A） ， 后做“2”（C） ， …… ， 最后做“11”（L） ， 就不会出现当要做一件事的时候 ， 它前面还有该做没做的事情 。
表2深度优先遍历生成的任务名称与访问序号、拓扑序号的对应关系
对前述深度优先算法稍加修改（在回溯前给节点编号） ， 即可得一个拓扑排序算法（留作读者练习） 。 其中有两点值得注意:第一 ， 起始节点（将最后编号）应该是不被任何其他节点依赖的 ， 即要选入度为0的节点；第二 ， 对于任意的依赖关系输入 ， 拓扑排序问题未必都有解 。 设想一下 ， 有两个任务X和Y ， X依赖于Y ， 但Y也依赖于X（可能是间接的）,这就形成了所谓相互依赖的“死循环” ， 无论怎么安排都没法满足它们 。 这种状况在图1所示的图模型中体现为一条有向回路 。 在算法中判断这种情况的标准方法是用3个状态（通常形象地用颜色白、灰、黑标记）来表征一个节点在深度优先搜索过程中不同时间段上的情况 。 White表示“尚未发现” ， grey表示“已发现但还未关闭”（在进入DFS时设置） ， black表示“已关闭”（即已回溯 ， 在离开DFS时设置） 。 在第2步 ， 发现了一个灰色节点 ， 就意味着图中存在回路（读者可想想其中的道理） 。
这个算法只是在深度优先搜索过程中增加了常数次简单赋值操作 ， 所以其时间代价与深度优先搜索算法一样 ， 为O(m+n) ， 其中m与n分别是输入图的边数与节点数 。
对于不熟悉深度优先等递归性质算法的读者 ， 还可以有一个概念上较简单 ， 但时间代价较大一些的拓扑排序算法 。 其要点是：不断删去有向图中出度为0的节点 。 删除的顺序就是节点的拓扑序 。 这种思路的程序实现十分容易 ， 直接操作邻接矩阵就可以 ， 不用递归 ， 对初学者有一定教益 。
执行时间与依赖关系共同约束下的任务调度
【算法园地|南京大学陈道蓄教授：调度问题中的算法】现在我们来考虑任务执行时间的影响 。 将表1给出的例子画出反向依赖图 ， 并将每个子任务的耗时标注在指向相应节点的边上 ， 我们就得到图2 。 此时 ， 边A→B的含义是“B必须在A做完了后才可以开始”（即B依赖于A） ， 上面的“30”表示B需要耗时30分钟 。 显然 ， 边上的数据标在箭头末端的节点上也是可以的 。
推荐阅读
- 娱乐的快递小哥|南京这家好吃到抽嘴巴都不丢的水饺，1元1个吃到撑，虹苑人都知道
- 历史建筑|漫步南京路、走进徐家汇源……上海建筑是一本读不尽的大书
- 蜱虫|南京7月来收治5例蜱虫叮咬重症患者，千万警惕这种小虫子！
- 央视新闻客户端|被游客偷摘的并蒂莲被制成标本 今天起在南京玄武湖展出
- 空手套白狼|南京男子租借数台豪车后转售，“空手套白狼”诈骗200多万被刑拘
- |南京长江江豚晚霞下嬉闹，市民欢呼：太美了！
- 金陵|寻找金陵美少年 《跟着课本去旅行》南京站海选成功举行
- 中国新闻社|南京玄武湖被采摘的并蒂莲蓬已制成标本：将长期展出
- 南京凭景区门票用餐打折|南京凭景区门票用餐打折怎么回事？具体详情曝光这个福利太赞了
- 景区门票用餐打折|南京凭景区门票用餐打折，哪些景区和餐厅可以打折