3

设 G 为 DAG，n 个顶点和 m 个边由邻接矩阵给出。我还需要以矩阵的形式计算它的闭包。我们有一台计算机，每个单词都是 b 位。我需要找到一种算法来计算传递闭包(n^2+nm/b)

我不太确定我理解什么bits意思以及如何使用它

添加寻找 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]
4

2 回答 2

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)

于 2013-01-04T11:37:46.250 回答
0

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

于 2013-01-02T21:42:21.997 回答