主页
搜索
最近更新
数据统计
赞助我们
申请密钥
系统公告
1
/
1
请查看完所有公告
广义矩阵乘法
最后更新于 2025-05-07 17:31:06
作者
Accoty_AM
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
# 广义矩阵乘法 通常用于优化dp/动态计算dp结果 ## 定义 将传统矩阵乘法的 $×$ 抽象为 $⊗$，$+$ 抽象为 $⊕$，那么矩阵乘法 $AB$ 则变为 $$(AB)_{ij} = ⨁_{k \le p} A_{ik}⊗B_{kj} $$ 考虑新运算是否满足结合律，只需要考虑 $(AB)C$ 是否等于 $A(BC)$ $$((AB)C)_{ij} = ⨁_{t\le q}((⨁_{k \le p}A_{ik}⊗B_{kt})⊗C_{tj})$$ $$(A(BC))_{ij} = ⨁_{k \le p}A_{ik}⊗(⨁_{t \le q}B_{kt}⊗C_{tj}))$$ 观察式子发现，$⊗$ 需要满足结合律，$⊕$ 对 $⊗$ 需要满足分配律即可实现矩阵乘法 ## 单位矩阵 单位矩阵 $X$ 需要保证 $AX = XA = A$ ## 例子 ```cpp for (int i = 1; i <= n; i++) for (int j = 1; k <= m; m++) for (int k = 1; k <= p; k++) c[i][j] = min(c[i][j], a[i][k] + b[k][j]) ``` 对于这个例子，+ 满足结合律，min 对 + 满足分配律，所以可以进行矩阵乘法 其单位矩阵为对角线为0,其余为正无穷的矩阵
正在渲染内容...
点赞
0
收藏
0
