387
个编辑
更改
跳到导航
跳到搜索
第225行：
第225行： − + 第231行：
第231行： − 托勒密王朝的家谱，许多近亲之间的婚姻导致家谱崩溃 − === Scheduling === − Family trees may be seen as directed acyclic graphs, with a vertex for each family member and an edge for each parent-child relationship. Despite the name, these graphs are not necessarily trees because of the possibility of marriages between relatives (so a child has a common ancestor on both the mother's and father's side) causing pedigree collapse. The graphs of matrilineal descent ("mother" relationships between women) and patrilineal descent ("father" relationships between men) are trees within this graph. Because+ − 家族树可以看作是有向无圈图，每个家族成员有一个顶点，每个亲子关系有一条边。除了名字，这些图并不一定是树，因为亲戚之间的婚姻(所以一个孩子在母亲和父亲方面有一个共同的祖先)会导致家谱崩溃。母系血统(女性之间的“母亲”关系)和父系血统(男性之间的“父亲”关系)的图表就是这个图表中的树。因为+ − + + + + − no one can become their own ancestor, family trees are acyclic.+ − 没有人能成为自己的祖先，家谱是无环的。
→Applications
的贝尔曼-福特算法等。[28]最长路径则是一个NP困难问题。[29]
的贝尔曼-福特算法等。[28]最长路径则是一个NP困难问题。[29]
== Applications ==
== Applications 应用 ==
Family tree of the [[Ptolemaic dynasty, with many marriages between close relatives causing pedigree collapse]]
Family tree of the [[Ptolemaic dynasty, with many marriages between close relatives causing pedigree collapse]]
=== Scheduling 调度 ===
Directed acyclic graphs representations of partial orderings have many applications in [[Schedule|scheduling]] for systems of tasks with ordering constraints.<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref>
Directed acyclic graphs representations of partial orderings have many applications in [[Schedule|scheduling]] for systems of tasks with ordering constraints.<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref>
Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks with ordering constraints.[29] An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a spreadsheet after one of the cells has been changed, or the object files of a piece of computer software after its source code has been changed. In this context, a dependency graph is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a circular dependency, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle. Dependency graphs without circular dependencies form DAGs.[30]
有向无环图的偏序关系可以在调度有着先后顺序限制的系统任务中发挥作用。[29]调度问题的一个重要种类是串联需要更新的对象，如電子試算表中某个单元格的计算公式依赖于其他单元格，或在程序的源代码被修改后重新编译目标文件。依赖图（英语：dependency graph）则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为环状依赖（英语：circular dependency）。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。[31]
For instance, when one cell of a spreadsheet changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell.[31] Similar problems of task ordering arise in makefiles for program compilation[31] and instruction scheduling for low-level computer program optimization.[32]
举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。[31]相似的任务调度场景出现在程序源代码编译的makefile，[31]和优化计算机程序底层执行的指令调度中。[32]
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed.
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed.