手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

世界今日讯！min 与 + 运算转换成类似于矩阵乘法的推导过程

2023-03-30 13:10:44 来源：博客园

记录下由 $\min$ 与 $+$ 运算转换成类似于矩阵乘法的推导过程，有错误请在评论区指出 qwq。

(资料图片仅供参考)

我们先简单证明一下矩阵乘法的结合律。设有矩阵 $A_{n \times m}$，$B_{m \times p}$，$C_{p \times q}$，要证明 $(AB)C = A(BC)$。等价于证 $\left({(AB)C}\right)_{i,j} = \left({A(BC)}\right)_{i,j}$，其中 ${A}_{i,j}$ 表示矩阵 $A$ 的第 $i$ 行第 $j$ 列的元素。

$$\begin{align*}\left({(AB)C}\right)_{i,j} &= \sum_{u=1}^{p}{(AB)_{i,u}} \times C_{u,j} \\&= \sum_{u=1}^{p} \left( {\sum_{k=1}^{m}{A_{i,k} \times B_{k,u}}} \right) \times C_{u,j} \\&= \sum_{u=1}^{p} \left( {\sum_{k=1}^{m}{A_{i,k} \times B_{k,u} \times C_{u,j}}} \right) \\&= \sum_{k=1}^{m} \left( {\sum_{u=1}^{p}{A_{i,k} \times B_{k,u} \times C_{u,j}}} \right) \\&= \sum_{k=1}^{m}{A_{i,k} \times \left( \sum_{u=1}^{p}{B_{k,u} \times C_{u,j}} \right)} \\&= \sum_{k=1}^{m}{A_{i,k} \times (BC)_{k,j}} \\&= \left({A(BC)}\right)_{i,j}\end{align*}$$

因此根据矩阵乘法的结合律，对于 $\overbrace{A \cdots A}^{n}$ 可以写成 $A^n$，并假设 $n = 2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}$，其中 $k = \left\lfloor \log{x} \right\rfloor$，$\forall i \in [0,k], \ b_i \in \{ {0,1} \}$，利用结合律我们就可以通过 $O(\log{n})$ 的复杂度来计算得到

$$A^n = A^{2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}} = A^{2^{b_k}} \times A^{2^{b_{k-1}}} \times \cdots \times A^{2^{b_0}}$$

其中上面的证明过程用到的运算包括 $+$ 与 $\times$ 以及对应的交换律、结合律和分配律。对于矩阵乘法

$$(AB)_{i,j} = \sum_{k=1}^{m}{A_{i,k} \times B_{k,j}}$$

为了更一般化，我们用运算符 $\oplus$ 和 $\otimes$ 来代替上面的加法与乘法，得到：

$$(AB)_{i,j} = \bigoplus_{k=1}^{m}{A_{i,k} \times B_{k,j}}$$

其中 $\oplus$ 和 $\otimes$ 满足交换律：

$$\begin{array}{center}a \oplus b = b \oplus a \\a \otimes b = b \otimes a\end{array}$$

结合律：

$$\begin{array}{center}(a \oplus b) \oplus c = a \oplus (b \oplus c) \\(a \otimes b) \otimes c = a \otimes (b \otimes c) \\\end{array}$$

$\otimes$ 对 $\oplus$ 的分配律：

$$a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)$$

很明显矩阵乘法中的加法 $+$ 和 $\times$ 就分别对应于 $\oplus$ 和 $\otimes$。同时发现把 $\min$ 代入 $\oplus$，$+$ 代入 $\otimes$ ，也满足上面定义的一般形式，只需验证这三个性质均成立即可。

交换律：

$$\begin{array}{center}\min \{ a,b \} = \min \{ b,a \} \\a + b = b + a\end{array}$$

结合律：

$$\begin{array}{center}\min \left\{ \min\{ a,b \}, c \right\} = \min \left\{ a,\min\{ b,c \} \right\} \\(a+b)+c = a+(b+c)\end{array}$$

$+$ 对 $\min$ 的分配律：

$$a + \min \{ b,c \} = \min \{ a+b, a+c \}$$

因此有

$$(AB)_{i,j} = \min_{1 \leq k \leq m} \left\{ A_{i,k} + B_{k,j} \right\}$$

因此对于由 $\min$ 与 $+$ 所构成的运算是具有结合律的，因此对于 $\overbrace{A \cdots A}^{n}$ 同样可以写成 $A^n$，并且有

$$A^n = A^{2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}} = A^{2^{b_k}} \times A^{2^{b_{k-1}}} \times \cdots \times A^{2^{b_0}}$$

注意这里的 $A \times B$ 是指两个矩阵间的运算，不是一般意义的矩阵乘法。对于 $\min$ 和 $+$ 有

$$(A \times B)_{i,j} = \min_{1\leq k \leq m} \left\{ A_{i,k} + B_{k,j} \right\}$$

而一般意义的矩阵乘法是

$$(A \times B)_{i,j} = \sum_{k=1}^{m}{A_{i,j} \times B_{j,k}}$$

我们通过Floyd求最短路这道题目对这个性质进行运用。

这里我们不用传统 Flody 的 dp 状态定义，而是定义状态 $f(k,i,j)$ 表示从 $i$ 到 $j$ 且经过不超过 $k$ 条边的所有路径所构成的集合中最短的路径长度。

对于任意两点 $(v, w)$ 间的距离，答案就是 $f(n-1, v, w)$，这是因为题目保证没有负环，因此任意两点间的最短路径不会超过 $n-1$ 条边。

根据从 $i$ 到 $j$ 的路径中所经过的点 $u$ 来把路径分成两段，其中前面一段 $i \to \cdots \to u$ 经过不超过 $k-1$ 条边，后面一段 $u \to \cdots \to j$ 经过不超过 $1$ 条边。这样就得到状态转移方程：

$$f(k,i,j) = \min_{1 \leq u \leq n} \{ f(k-1,i,u) + f(1,u,j) \}$$

这种做法的时间复杂度为 $O(n^4)$。这个时候就可以利用上面的性质来进行优化了。

我们把 $f(k,i,j)$ 看成是矩阵 $F^{k}_{n \times n}$ 第 $i$ 行第 $j$ 的元素，因此上面的状态转移方程就变成了

$$F^{k}_{i,j} = \min_{1 \leq u \leq n}\left\{ F^{k-1}_{i,u} + F^{1}_{u,j} \right\}$$

矩阵间的运算就是 $F^{k} = F^{k-1} \ F^{1}$，通过递推可以发现有 $F^k = \left( F^1 \right)^k$，而我们最终要求的矩阵就是 $F^{n-1} = \left( F^1 \right)^{n-1}$。

这里的 $F^k$ 是一个 $n \times n$ 的矩阵，里面的每一个元素 $F^{k}_{i,j}$ 表示从 $i$ 到 $j$ 经过不超过 $k$ 条边的最短路径。

这里就可以用快速幂来求 $F^1$ 的 $n-1$ 次方来得到 $F^{n-1}$，要注意是由 $\min$ 与 $+$ 所构成的运算规则。

同时根据定义知道矩阵 $F^0$ 中任意一个元素 $F^{0}_{i,j}$ 表示 $i$ 到 $j$ 不经过任何边的最短路径，因此有

$$F^0 = \begin{bmatrix} 0 & \infty & \cdots & \infty \\ \infty & 0 & \cdots & \infty \\ \vdots & \vdots & \ddots & \vdots \\ \infty & \infty & \cdots & 0 \end{bmatrix}$$

$F^{n-1} = F^0 \ \left( F^1 \right)^{n-1}$。

这样时间复杂度就降到了 $O(n^3 \log{n})$，虽然还是不如传统的 Flody 算法，但这种做法给了我们很多启示，比如魔法和牛站就是利用这种思想实现的。

$O(n^3 \log{n})$ 做法的 AC 代码如下：

1 #include  2 using namespace std; 3  4 const int N = 210, INF = 0x3f3f3f3f; 5  6 int n, m, k; 7 int f[N][N], g[N][N], tmp[N][N]; 8  9 void mul(int c[][N], int a[][N], int b[][N]) {10     memset(tmp, 0x3f, sizeof(tmp));11     for (int i = 1; i <= n; i++) {12         for (int j = 1; j <= n; j++) {13             for (int k = 1; k <= n; k++) {14                 // 类似于矩阵乘法的c[i][j] = sum(a[i][k] * b[k][j])15                 // 对于min和+运算有c[i][j] = min{a[i][k] + b[k][j]}16                 tmp[i][j] = min(tmp[i][j], a[i][k] + b[k][j]);17             }18         }19     }20     memcpy(c, tmp, sizeof(tmp));21 }22 23 int main() {24     scanf("%d %d %d", &n, &m, &k);25     // 一开始g=F^026     for (int i = 1; i <= n; i++) {27         for (int j = 1; j <= n; j++) {28             f[i][j] = g[i][j] = INF;29         }30         f[i][i] = g[i][i] = 0;31     }32     // 一开始f=F^133     while (m--) {34         int v, w, wt;35         scanf("%d %d %d", &v, &w, &wt);36         f[v][w] = min(f[v][w], wt);37     }38     m = n - 1;  // 快速幂求F^{n-1}39     while (m) {40         if (m & 1) mul(g, g, f);41         mul(f, f, f);42         m >>= 1;43     }44     // 这时有g=F^{n-1}45     while (k--) {46         int v, w;47         scanf("%d %d", &v, &w);48         if (g[v][w] > INF >> 1) printf("impossible\n");49         else printf("%d\n", g[v][w]);50     }51     52     return 0;53 }

参考资料

矩阵乘法笔记：https://www.cnblogs.com/wangruidong03/p/15891893.html

关键词：