![区块链交易所](https://175.178.95.144/qu/d/file/exchange/negocie-coins.png alt="Negocie Coins的Logo">)
区块链交易所
![区块链交易所](https://175.178.95.144/qu/d/file/exchange/ripple-china.png alt="Ripple China的Logo">)
DAG（有向无环图）的发展与应用
发布：中币网 时间：2018-11-28 00:53:34 加入收藏 打赏
但DAG的历史可以追溯到中本聪第一次写比特币白皮书之前，莱昂哈德•欧拉(Leonhard Euler)发表关于“哥尼斯堡七桥”(Seven Bridges of Konigsberg)的论文之前，甚至可以追溯到古埃及人铺设金字塔第一块石头之前。人们并不知道DAG的第一次使用的具体时间，但是这个概念非常有用，它可以追溯到人类存在的早期。
简单地说，DAG是节点的集合，这些节点表示“事物”，由表示与其他“事物”链接的有向边连接，在图中没有循环。例如，一个城市只有一条街道，如果一个人沿着任何街道旅行，他都永远不能回到以前的任何位置。它是图论中给出的一个定义，但是在图论正式形成之前的几千年里，DAG一直没有一个正式的定义。
如前所述，莱昂哈德·欧拉于1736年发表的《哥尼斯堡的七桥》被认为是第一个涉及图论的论文。哥尼斯堡七桥是数学史上一个引人注目的问题。将城市地图简化成图形后，欧拉引入了关于边、顶点和面数的公式。
图论发展成为一门研究对象之间关系的学科，并且用数学结构来描述的。有许多不同类型的图，都有特定的定义，DAG就是其中之一。虽然图论直到1736年才被正式定义，“七座桥”问题在此之前已经存在了几百年，人们一直在创造这个问题的心理和物理表征。虽然没有正式的定义，但这些表示都是图形。正如图形没有定义，但它们被使用了一样，DAG也没有定义，但它们也被使用了!
DAG的一个古老用例是创建一个家谱。有趣的是，图论中树的定义并不包括大多数的系谱树。这是因为，在大多数历史足够久远的家族中，在某些时候，远亲会进行交配，从而在家族的父系和母系双方都有一个共同的祖先。这意味着，一个家谱可以被认为是一把匕首，其中每个节点都是一个人，并且每个父子关系都被画成指向后代的箭头。这形成了一个如下图所示的图，它是有向的(箭头)和无环的(没有人可以是自己的父母)。
古罗马时期，老普林尼(Pliny the Elder)就有记载，他描绘了装饰罗马贵族住宅墙壁的图形。在此之前，DAG可能没有被记录下来，但在解释家族史时经常被描述出来。
DAG的另一个历史用例是任务调度，动物和人类都在使用DAG来计算任务完成的顺序。当需要完成多项任务的工作时，比如做饭，我们会在脑海中列出任务的顺序。有些任务在其他任务完成之前不能开始，而其他任务可以在任何时候开始——这本身就是一个DAG。
在上面的DAG中，T1可能是决定猎食哪种动物，T 2是猎食动物，T3是收集柴火，可以同时进行。T4是生火。T5是烹饪动物，这需要生火和猎食动物，而T6是吃晚餐，这需要动物首先被烹饪。
类似的(但更为复杂的)DAG可以用于任何大型任务，如建造金字塔、策划战争期间的袭击等等。
DAG的其他用例更加现代，具有与计算机科学相关的多种用途。数据处理网络和一些数据压缩算法都使用DAG。但是值得注意的是，DAG并不是一个新的发现，而是一个古老的问题解决机制。DAG和区块链的合并是分布式账本可伸缩性的一个巨大飞跃。
来源：区块网
来源：中币网 https://www.zhongbi.net/news/blocknews/121229.html 声明：登载此文仅出于分享区块链知识，并不意味着赞同其观点或证实其描述。文章内容仅供参考，不构成投资建议。投资者据此操作，风险自担。 此文如侵犯到您的合法权益，请联系我们3111859717@qq.com，我们将第一时间处理。
