《算法的乐趣》第二十四节

本节总结了前文的穷举算法：近2亿个组合中只有一组通过全部线索，验证了答案的唯一性；该算法属于多维度穷举，即对每个维度分别穷举再按关系组合。

本节总结了前文的穷举算法：近2亿个组合中只有一组通过全部线索，验证了答案的唯一性；该算法属于多维度穷举，即对每个维度分别穷举再按关系组合。随后引入项目管理，说明如何将项目分解为存在前后依赖的活动，并通过软件按开始时间排序、查找关键路径，以保证工程顺利进行并估算最短工期。这些功能背后的算法是图论中的有向图拓扑排序与关键路径查找。

本节接着介绍有向无环图（DAG）的两种表示方法：顶点表示活动的AOV网（用于拓扑排序）和边表示活动、权值为时间的AOE网（用于估算工期）。拓扑排序是把顶点排成线性序列，使每条有向边的起点都在终点之前。其基本过程是反复选取入度为0的顶点输出并删除其发出的边；若最终仍有未输出的顶点，则说明图中存在环路。按此序列安排活动可保证依赖关系不冲突，且一个DAG往往有多个合法拓扑序列。

最后讲解按活动开始时间排序的算法：无前驱的活动开始时间为0，有前驱的活动开始时间取各前驱的开始时间与持续时间之和的最大值。以邻接表存储AOV网后，在拓扑排序过程中，对同时出现的多个入度为0的顶点按开始时间排序输出，从而得到符合Project软件“按照开始时间排序”功能的序列。