有向无环图 有向无环图的历史与用例

最初的标题“达格的历史和使用案例”最初于2018年在Medium.com出版

刘烨翻译学校

在去中心化技术中，有向无环图是一个基于块的新领域。然而，dag已经使用了几千年，甚至是无意识地使用。在某种意义上，DAGs优于区块链，因为它通过结合区块链、工作量和权益证明，以及最长链原理和有向无环图的概念，允许更高的吞吐量。

然而，达格人的历史可以追溯到很久以前，中本聪开始写比特币白皮书之前，莱昂哈德·欧拉发表关于哥尼斯堡七桥的论文之前，甚至在古埃及人铺设金字塔的第一块石头之前。有向无环图首次使用的日期没有记录，但这个概念非常有用，可以追溯到人类存在的早期。

在我们之前发表的一篇文章中，我们引入了DAGs的概念。简单来说，有向无环图是一系列节点的集合，代表“事物”，节点之间通过有向边连接，表示与其他“事物”的连接，因此图中没有循环。举个例子，在一个只有单行道的城市里，一个人沿着任何一条街走，他都不会回到以前的任何位置。它是图论中的一个定义，但是在图论形式化之前，人们已经使用DAGs几千年了，没有一个正式的定义。

如前所述，莱昂哈德·欧拉于1736年出版的《哥尼斯堡的七座桥》被认为是第一篇关于图论的论文。哥尼斯堡七桥问题是数学史上一个值得注意的问题。挑战在于找到一条穿过哥尼斯堡(现在的加里宁格勒)七座桥的路线，而且只能穿过一次。在将城市地图简化为图形后，欧拉引入了关于边、顶点和面的量化公式。

从此，图论发展成为研究对象之间的关系，用数学结构来描述。有许多不同类型的图都有特定的定义，有向无环图就是其中之一。现在，虽然地图直到1736年才正式定义，但“七桥”问题在此之前已经存在了数百年，人们一直在创造这个问题的心理和物理表征。虽然没有正式的定义，但是这些表示都是图。就像图没有定义，但是还在使用，dag没有定义，但是已经在使用了！

Dags的一个老用例是创建一个家谱。有趣的是，图论中树的定义并不包括大多数系谱树。这是因为在大多数家谱中，当距离足够远时，远亲在某个时刻结婚，允许父系和母系家庭都有一个共同的祖先。这意味着一个家谱可以看作是一个有向无环图，其中每个节点都是一个人，每个父子关系都画成一个指向后代的箭头。这就形成了如下图，有向(箭头)，无环(没有人可以是自己的父亲)。

族谱树被描绘成有向无环图，这可以在古罗马找到，当时普林尼描述了装饰在罗马贵族房屋墙壁上的人物。在此之前，dag可能不记录，但在解释家族史时往往会有描述。

Dag的另一个历史用例是任务调度，动物和人类本能地使用Dag来计算任务完成的顺序。当完成一个需要很多任务的任务时，比如做晚饭，我们会在脑海中列出任务的顺序。有些任务在其他任务完成之前无法启动，而其他任务可以随时启动——这本身就是一个DAG。

在上面的DAG中，T1可能决定用哪种动物做晚餐，任务2是捕猎动物，任务3可以同时完成，就是捡柴火。任务4是生火。任务5，烹饪动物，不仅需要烧火，还需要捕猎动物。任务6是吃晚饭，需要先煮动物。

类似(但更复杂)的Dag可以用于任何大规模的任务，比如建造金字塔、设计罗马、策划战争期间的攻击等等。

Dags的其他用例更现代，有很多与计算机科学相关的用途。DAGs用于数据处理网络、版本历史和一些数据压缩算法。然而，重要的是要注意，DAGs不是一个新的启示，而是一个古老的解决问题的机制。达格·哈马舍尔德图书馆和区块链图书馆的合并是分布式分类账能力扩展的一大飞跃。