利用机器字来计算有向无环图的传递闭包的算法？

Question

假设有一个由邻接矩阵表示的包含n个节点和m条边的有向无环图（DAG）。我需要计算出其闭包的矩阵形式。我们有一台计算机，每个单词占据b个比特位。我需要找到一种算法，在(n^2+nm/b)的时间复杂度下计算其传递闭包。

我不太确定什么是“比特位”，以及如何使用它。

以下是查找DAG传递闭包的算法：

TransitiveForDAG (Graph G)
int T[1...n,1...n] ={0,...,0}
List L <- TopologicalSort(G)
For each v in reverse(L)
   T[v,v]<-1
    For each u in Adj[v]
       for j<-1,...,n do
         T[v,j]<-T[v,j] or T[u,j]

- Anna

---

我不确定你是否完成了。 - Ivaylo Strandjev

谢谢。你的问题实际上是一个很好的问题，如果你像这样提出它，我相信它不会被投下反对票。我给你点赞。 - Ivaylo Strandjev

(n^2+nm/b) 是指时间（算法步骤）还是空间（内存使用）？ - Ted Hopp

@TedHopp 的算法步骤...基本上我们学习到 DAG 上的传递闭包是 n^2+nm，但我仍然不明白这些比特是什么意思。 - Anna

@templatetypedef 我没有找到任何链接，但我现在已经将它添加到我的问题中了（从我的书上复制）。 - Anna

Answer 1

你说你不知道什么是位，那我们就从这里开始。

• 位是数字信息的最小单位 - 0或1
• 字是计算机一次处理的数据单元。处理器不会处理单个位，而是处理它们的小块。大多数今天的计算机架构使用32位或64位的字。

现在，如何处理二进制数据的字？在大多数编程语言中，您将使用数字数据类型来存储数据。为了操作它们，大多数语言提供按位运算符 - 按位或（|）是其中之一。

那么，如何使您的算法更快？看看T矩阵。它只能具有0或1的值 - 一个位就足以存储该信息。您正在逐个处理矩阵的字段；每次处理算法的最后一行时，您只使用来自第v行和第u行的一个位。

如前所述，处理器必须读取整个字才能读取和处理每个位。这是低效的；大多数情况下，您不会关心这样的细节，但在这里它处于关键位置 - 最后一行位于最内部循环中，并且将被执行很多次。

现在，如何更有效？改变存储数据的方式 - 使用一个具有单词长度的类型作为矩阵的数据类型。将原始矩阵中的b值存储在新矩阵的每个值中 - 这称为打包。由于算法的工作方式，您将希望按行存储它们 - 第i行中的第一个值将包含原始矩阵的第i行中的前b个值。

除此之外，您只需要更改算法的最内部循环 - 该循环将迭代单词而不是单个字段，并且在其中使用位或一次处理整个单词。

T[v,j]<-T[v,j] | T[u,j]

循环是算法时间复杂度的产生者。现在您已经少迭代了b次，所以复杂度变成了(n^2+nm/b)。

- voidengine

Answer 2

对于简单图，邻接矩阵中的每个条目都是0或1，并且可以用一个比特表示。这允许通过将 b 个条目打包到每个计算机字中来紧凑表示矩阵。然后，挑战就是使用正确的位操作符实现矩阵乘法（以计算闭包）。

- Ted Hopp

---

我认为挑战在于如何使用打包的字来实现矩阵乘法。由于要优化的是运行时，因此您可能希望以某种方式使用单个字的操作来并行地执行多个位上的操作。 - templatetypedef

Ted，谢谢你的回答，但不幸的是，我仍然不明白如何将其用于实现矩阵乘法。 - Anna

@Anna，我猜一个简单的例子就是常规矩阵乘法。这是怎么做的？A行1 * B列1 = Cr1c1，对吗？（当然要将元素相加）。在DAG中，元素只能是1或0。因此，可能的结果只能是1或0（仅当两个元素都为1时才为1）。这相当于逻辑AND，对吗？现在，为了快速执行整个行*列的操作，您可以看到它等同于所涉及的行和列的按位AND（在求和之前）。您能看到如何将X次乘法转换为1个长度为X位的AND吗？ - im so confused

Ted和Template试图告诉您，通过紧凑的位表示实现这些常规矩阵操作是此算法所代表的唯一挑战。 - im so confused