布尔矩阵乘法算法

Question

这是我关于 Whosebug 的第一个问题。我一直在解决来自 Tamassia 的 Goodrich "Algorithm design" 的一些练习。但是，我对这个问题一无所知。不确定从哪里开始以及如何进行。任何建议都会很棒。问题是：

布尔矩阵是每一项都是0或1的矩阵，矩阵乘法是用AND代表*，OR代表+。假设我们给定了两个 NxN 的随机布尔矩阵 A 和 B，这样任意一个条目出现的概率在任一是 1，是 1/k。证明如果 k 是常数，则存在 A 和 B 相乘的算法，其预期运行时间为 O(n^2)。如果k是n呢？

Answer 1

使用标准迭代方法的矩阵乘法是 O(n³)，因为您必须迭代 n 行和 n 列，并且对每个元素执行向量乘法其中一行和一列，需要 n 次乘法和 n-1 次加法。

将矩阵 a 乘以矩阵 b 并存储在矩阵 c 中的伪代码:

for(i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
    {
        int sum = 0;
        for(m = 0; m < n; m++)
        {
            sum += a[i][m] * b[m][j];
        }
        c[i][j] = sum;
    }
}

对于问题中指定的布尔矩阵，AND 用于乘法和 OR 代替加法，所以它变成这个：

for(i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
    {
        boolean value = false;
        for(m = 0; m < n; m++)
        {
            value ||= a[i][m] && b[m][j];
            if(value)
                break; // early out
        }
        c[i][j] = value;
    }
}

这里要注意的是，一旦我们的布尔值 "sum" 为真，我们就可以停止计算并提前退出最内层循环，因为对任何后续值与真进行或运算都会产生真，所以我们可以马上知道最后的结果是真的

对于任何常量 k，我们可以尽早执行此操作之前的操作次数（假设值是随机的）将取决于 k 并且不会随着 n 的增加而增加。在每次迭代中，循环将有 (1/k)² 的机会终止，因为我们需要两个 1 才能发生，并且每个条目为 1 的机会为 1 /k。终止前的迭代次数将遵循 Geometric distribution，其中 p 为 (1/k)²，以及 "trials"（迭代）之前的预期次数 "success"（跳出循环）不依赖于 n（除了作为试验次数的上限）所以对于给定的 k，最内层的循环以恒定时间（平均）运行，使得整个算法为 O (n²)。几何分布公式应该让您对 k = n 时会发生什么有一些了解。请注意，在维基百科上给出的公式中，k 是试验次数。

布尔矩阵乘法算法

Boolean matrix multiplication algorithm

algorithm

boolean

matrix

sparse-matrix

strassen