最初的標(biāo)題“達格的歷史和使用案例”最初于2018年在Medium.com出版

劉燁翻譯學(xué)校

在去中心化技術(shù)中，有向無環(huán)圖是一個基于塊的新領(lǐng)域。然而，dag已經(jīng)使用了幾千年，甚至是無意識地使用。在某種意義上，DAGs優(yōu)于區(qū)塊鏈，因為它通過結(jié)合區(qū)塊鏈、工作量和權(quán)益證明，以及最長鏈原理和有向無環(huán)圖的概念，允許更高的吞吐量。

然而，達格人的歷史可以追溯到很久以前，中本聰開始寫比特幣白皮書之前，萊昂哈德·歐拉發(fā)表關(guān)于哥尼斯堡七橋的論文之前，甚至在古埃及人鋪設(shè)金字塔的第一塊石頭之前。有向無環(huán)圖首次使用的日期沒有記錄，但這個概念非常有用，可以追溯到人類存在的早期。

在我們之前發(fā)表的一篇文章中，我們引入了DAGs的概念。簡單來說，有向無環(huán)圖是一系列節(jié)點的集合，代表“事物”，節(jié)點之間通過有向邊連接，表示與其他“事物”的連接，因此圖中沒有循環(huán)。舉個例子，在一個只有單行道的城市里，一個人沿著任何一條街走，他都不會回到以前的任何位置。它是圖論中的一個定義，但是在圖論形式化之前，人們已經(jīng)使用DAGs幾千年了，沒有一個正式的定義。

如前所述，萊昂哈德·歐拉于1736年出版的《哥尼斯堡的七座橋》被認(rèn)為是第一篇關(guān)于圖論的論文。哥尼斯堡七橋問題是數(shù)學(xué)史上一個值得注意的問題。挑戰(zhàn)在于找到一條穿過哥尼斯堡(現(xiàn)在的加里寧格勒)七座橋的路線，而且只能穿過一次。在將城市地圖簡化為圖形后，歐拉引入了關(guān)于邊、頂點和面的量化公式。

從此，圖論發(fā)展成為研究對象之間的關(guān)系，用數(shù)學(xué)結(jié)構(gòu)來描述。有許多不同類型的圖都有特定的定義，有向無環(huán)圖就是其中之一?，F(xiàn)在，雖然地圖直到1736年才正式定義，但“七橋”問題在此之前已經(jīng)存在了數(shù)百年，人們一直在創(chuàng)造這個問題的心理和物理表征。雖然沒有正式的定義，但是這些表示都是圖。就像圖沒有定義，但是還在使用，dag沒有定義，但是已經(jīng)在使用了！

Dags的一個老用例是創(chuàng)建一個家譜。有趣的是，圖論中樹的定義并不包括大多數(shù)系譜樹。這是因為在大多數(shù)家譜中，當(dāng)距離足夠遠時，遠親在某個時刻結(jié)婚，允許父系和母系家庭都有一個共同的祖先。這意味著一個家譜可以看作是一個有向無環(huán)圖，其中每個節(jié)點都是一個人，每個父子關(guān)系都畫成一個指向后代的箭頭。這就形成了如下圖，有向(箭頭)，無環(huán)(沒有人可以是自己的父親)。

族譜樹被描繪成有向無環(huán)圖，這可以在古羅馬找到，當(dāng)時普林尼描述了裝飾在羅馬貴族房屋墻壁上的人物。在此之前，dag可能不記錄，但在解釋家族史時往往會有描述。

Dag的另一個歷史用例是任務(wù)調(diào)度，動物和人類本能地使用Dag來計算任務(wù)完成的順序。當(dāng)完成一個需要很多任務(wù)的任務(wù)時，比如做晚飯，我們會在腦海中列出任務(wù)的順序。有些任務(wù)在其他任務(wù)完成之前無法啟動，而其他任務(wù)可以隨時啟動——這本身就是一個DAG。

在上面的DAG中，T1可能決定用哪種動物做晚餐，任務(wù)2是捕獵動物，任務(wù)3可以同時完成，就是撿柴火。任務(wù)4是生火。任務(wù)5，烹飪動物，不僅需要燒火，還需要捕獵動物。任務(wù)6是吃晚飯，需要先煮動物。

類似(但更復(fù)雜)的Dag可以用于任何大規(guī)模的任務(wù)，比如建造金字塔、設(shè)計羅馬、策劃戰(zhàn)爭期間的攻擊等等。

Dags的其他用例更現(xiàn)代，有很多與計算機科學(xué)相關(guān)的用途。DAGs用于數(shù)據(jù)處理網(wǎng)絡(luò)、版本歷史和一些數(shù)據(jù)壓縮算法。然而，重要的是要注意，DAGs不是一個新的啟示，而是一個古老的解決問題的機制。達格·哈馬舍爾德圖書館和區(qū)塊鏈圖書館的合并是分布式分類賬能力擴展的一大飛躍。