更改

有向无环图 (查看源代码)

2021年6月14日 (一) 11:45的版本

添加71字节、 2021年6月14日 (一) 11:45

→‎调度

第132行：第132行：

==应用==

===调度===

−

有向无环图的偏序关系可以在调度上有着先后顺序限制的系统任务中发挥作用。<ref>~~{{harvtxt|~~Skiena|2009}}, p. ~~469~~.</ref>调度问题的一个重要种类是串联需要更新的对象，如[[电子计算表]]中某个单元格的计算公式依赖于其他单元格，或在程序的[[源代码]]被修改后重新编译[[目标代码|目标文件]]。 '''依赖图 Dependency graph''' 则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为 '''环状依赖 Circular dependency''' 。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 }}.</ref>

+

有向无环图的偏序关系可以在调度上有着先后顺序限制的系统任务中发挥作用。<ref>Skiena, Steven S. (2009), The Algorithm Design Manual, Springer, pp. 179–181, ISBN 978-1-84800-070-4..</ref>调度问题的一个重要种类是串联需要更新的对象，如[[电子计算表]]中某个单元格的计算公式依赖于其他单元格，或在程序的[[源代码]]被修改后重新编译[[目标代码|目标文件]]。 '''依赖图 Dependency graph''' 则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为 '''环状依赖 Circular dependency''' 。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 }}.</ref>

举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。<ref name="hgt1181">{{citation |title=Handbook of Graph Theory |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |first3=Ping |last3=Zhang | author3-link = Ping Zhang (graph theorist)|edition=2nd |publisher=CRC Press |year=2013 |isbn=978-1-4398-8018-0 |page=1181 |url=https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181}}.</ref>相似的任务调度场景出现在程序源代码编译的 '''Makefile''' ，<ref name="hgt1181" />和优化计算机程序底层执行的[[指令调度]]中。<ref>{{citation |title=The Compiler Design Handbook: Optimizations and Machine Code Generation |first1=Y. N. |last1=Srikant |first2=Priti |last2=Shankar |edition=2nd |publisher=CRC Press|year=2007 |isbn=978-1-4200-4383-9 |pages=19–39 |url=https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39}}.</ref>

第139行：第139行：

[[File:PERT_chart_for_a_project.png|thumb|图10：一个有着五个里程碑（注有10–50）和六个任务（注有A–F）的计划评审图。ADF和BC是[[关键路径]]]]

[[计划评审技术]]是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑 (项目管理) Milestone (project management)，每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的[[最长路径问题|最长路径]]即为项目的[[关键路径]]。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref>

−

===数据处理网络===

薄荷

7,129

个编辑