浅谈矩阵加速优化动态规划

· · 题解

浅谈矩阵加速优化动态规划

本文只适用于OI学习

矩阵乘法

给定两个矩阵

A=\begin{bmatrix}1 &2 &3 \\ 4& 0&1\end{bmatrix} B=\begin{bmatrix}1 &2 \\ 2 &0 \\ 3 &1\end{bmatrix}

那么,A \times B=C

C=\begin{bmatrix}1\times1+2\times2+3\times3 & 1\times 2 +2\times0+3\times1 \\ 4\times1+0\times 2 + 1\times3 & 4\times2+0\times 0 +1\times 1\end{bmatrix}

用数学公式表述那就是：

C_{ij}=\sum_{k=1}^{n}A[i][k]*B[k][j]

一般来说，A的行数B的列数，B的行数也等于A的列数，当两个不满足上述条件的矩阵相乘时，我们可以通过补零的方式使他们满足。

由于矩阵乘法满足分配率，结合律（但是不满足交换律！）,所以我们可以通过矩阵快速幂的方法来加速

--- ## Floyd $Floyd$是一种最短路算法，适用于点数较少的图 $Floyd$的本质是**动态规划**,它的状态定义以及转移： > 设$f[i][j]$为$i$到$j$的最短距离 > $f[i][j]=min(f[i][j],f[i][k]+f[k][j])

代码实现：

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

我们魔改一下：

    int C[N][N];
    memset(C,127,sizeof C); // inf
    for(int k=1;k<=n;j++)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                C[i][j]=min(C[i][j],A[i][k]+A[k][j]);
    }
    memcpy(A,C,sizeof C);
$A$:当然不是，floyd是动态规划```f[i][k]+f[k][j]```是已知的最优状态的转移，但是第二种却是两个初始矩阵简单的相乘。 $tips:$这里的矩阵乘法由原来的$C[i][j]=A[i][k]+B[k][i]$,变成了$C[i][j]=\color{red} {min(C[i][j],A[i][k]+A[k][j])}

之所以可以加\color{red} min，是因为min也满足结合律:min(min(a,b),c)=min(a,b,c)=min(a,min(b,c))

那么它代表的意义又是什么呢？ 先放出例题

让我们做下列这个实验： 实验代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int A[1001][1001];
int C[1001][1001];
signed main()
{
    freopen("data.in","r",stdin);
    int n,m;
    scanf("%d %d",&n,&m);
    memset(A,50,sizeof A);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d %d %d", &a,&b,&c);
        A[a][b]=A[b][a]=c;
        A[i][i]=0;
    }
    int tmp=1;// 看这里！！！！！！！！
    while(tmp--)
    {
        memset(C,127 , sizeof C);

        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    C[i][j]=min(C[i][j],A[i][k]+A[k][j]);
        }
        memcpy(A,C,sizeof C);   
    }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                if(A[i][j]<100)
                    printf("%d ",A[i][j]);
                else
                {
                    printf("X ");
                }
            printf("\n");
        }
}

给出一条链：

1-2-3->4-5\dots-10

输入的邻接矩阵A，可以理解成经过一条边的最短路，我们记做A^{1}.

C=A\times A, C= A^{2}$，然后把$A$赋值成为$C$，也就是$A^{2}

容易发现，当tmp=x时，C为A^{2^{x}}

下面是我记录的实验数据:

tmp 邻接矩阵第一行（也就是点1到各个点距离）X为不连通
1 0 1 2 X X X X X X X
2 0 1 2 3 4 X X X X X
3 0 1 2 3 4 5 6 7 8 X

容易发现，{A^{x}}是表示A经过了x条边的最短路。

于是上边的例题就能通过矩阵快速幂轻松解决！