江苏龙网

  1. 首页 > 人文 > >

产业气象站 算法园地|南京大学陈道蓄教授：调度问题中的算法( 二 )


在图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分钟 。 显然 ， 边上的数据标在箭头末端的节点上也是可以的 。


推荐阅读


上一篇：问董秘|公...，投资者提问：请问新能源汽车动力电池系统和热管理系统会使用哪些精细化学品

下一篇：晨财经|除了关店，还有哪些大招？，ZARA等快时尚品牌遇“寒流”