矩阵乘法与邻接矩阵

                矩阵乘法与邻接矩阵

                矩乘结合律的证明 \(:\)
                \[\begin{aligned}((\mathbf{A B}) \mathbf{C})[i, j] & \\ &=\sum_{l=1}^{c}\left(\sum_{k=1}^{b} \mathbf{A}[i, k] \mathbf{B}[k, l]\right) \mathbf{C}[l, j] \\ &=\sum_{k=1}^{b} \sum_{l=1}^{c} \mathbf{A}[i, k] \mathbf{B}[k, l] \mathbf{C}[l, j] \\ &=\sum_{k=1}^{b} \mathbf{A}[i, k]\left(\sum_{l=1}^{c} \mathbf{B}[k, l] \mathbf{C}[l, j]\right) \\ &=(\mathbf{A}(\mathbf{B} \mathbf{C}))[i, j] \end{aligned}\]

                矩阵乘法能进行快速幂运算的原因就是因为它具有结合律.

                引例 \(1:\) [TJOI2017]可乐

                相信很多人都能想出一个 \(\Theta(t\times m)\) 的做法.(虽然我没想出来,但这只是因为我菜)

                问题简化一下,如果我们没有在原地停留和自爆两个操作,那么就是问从起点出发,走 \(t\) 步的不同路径数.

                这个问题怎么做呢?

                不考虑 \(Dp\) .

                令该图的邻接矩阵是 \(G\) , 那么我们考虑 \(G^2\) 是个什么东西.(此处的幂运算是指矩阵的幂).

                我们单独考虑某一行和某一列的相关运算 \(:\) 令其为 \(G_{a,i}\)\(G_{i,b}\) , 令 \(G'\) 为相乘得到的矩阵,那么会有 \(:\)

                \[G'_{a,b} = \sum_{i=1}^m{G_{a,i}\times G_{i,b}}\]

                容易发现,当且仅当 \(G_{a,i}\)\(G_{i,b}\) 都不为零,即 \(i\) 点可连通 \(a,b\) 两点的时候上式的该项才为 \(1\) , 否则为零.

                那么所有的这些情况累加起来,就是从 \(a\)\(b\) 长度为 \(2\) 的路径条数.(即走 \(2\) 步从 \(a\) 走到 \(b\) 的方案数,长度是 \(2\) 是因为经过一个中间点.)

                由此,我们可以得到, \(G^2\) 得到的矩阵其实表示了任意两点间长度为 \(2\) 的路径条数.

                那么 \(G^3\) 是否就表示任意两点间长度为 \(3\) 的路径条数呢?

                \(G'=G^2\) , \(G''\)\(G^3\). 那么有:

                \[G''=G'\times G\]

                \[G''_{a,b}=\sum_{i=1}^n\sum_{j=1}^n{G_{a,i}\times G_{i,j}\times G_{j,b}}\]

                分析方法与上面相同,于是我们归纳结论如下:

                \(G\) 表示一张图的邻接矩阵表示,那么 \(G^i\) 表示任意两点间长度为 \(i\) 的路径条数.

                那么我们就解决了引例的简化问题.

                那么怎么处理引例中的自爆和原地不动呢?

                很简单,原地不动视为自环,自爆就额外建一个虚点,表示自爆,这里要注意的是,不需要从虚点连回原图,因为自爆之后就不能再走了.

                于是我们解决了引例.

                那么矩乘是否仅仅只有这一个用处呢?

                引例 \(2:\) USACO07NOV Cow Relays

                题目大意 \(:\) 求从 \(s\)\(t\) 经过 \(k\) 条边的最短路.

                这个问题乍一看很眼熟,似乎就是上一个问题在细节上做一下变换得到.

                但你仔细思考会发现,最短路这个看似平凡的条件竟然不能用加法和乘法解决.

                但其实这也合理,因为我们知道最短路的求法都是以类似于 \(Dp\) 的松弛操作为核心的,也就是说有一个核心运算 \(: min!\)

                那么是否可以用矩阵解决这个运算呢?

                考虑 \(Floyd\) 的过程,其核心代码是 \(f_{i,j}=min(f_{i,j},f_{i,k}+f_{k,j})\)

                这给了我们一定启发,因为 \(Floyd\) 的过程和矩乘的过程十分相似.( \(Floyd\) 的本质是滚掉一维的三维 \(Dp\))

                于是,我们大胆定义新的矩乘 \(:\)

                令矩阵 \(A\) 和 矩阵 \(B\) 相乘的结果为矩阵 \(C\) .

                则定义:

                \[C_{a,b}=\sum_{i=1}^m{min(A_{x,i},B_{i,y})}\]

                容易发现,这个矩乘同样具有结合律.(可以从 \(min\) 运算是和 \(+\) 运算具有同样性质的二元运算符考虑,证明与普通矩乘相同).

                那么这样,我们直接应用引例 \(1\) 中的结论即可解决该题.

                引例 \(3:\) 最小最大边问题

                找不到题目了,国集论文没给题目来源,找不到.

                最小最大边问题 \(:\) 给定一张有向图,求某两点间通过边数恰好为 \(k\) 的路径,使得最大边最小.

                同样的熟悉,同样的问题.

                考虑如果没有长度恰好为 \(k\) 的做法,那么就是把 \(Floyd\) 的核心代码换成 \(:\)
                \[f_{i,j}=max(f_{i,j},min(f_{i,k},f_{k,j}))\]

                能否采用与上面相同的方式重定义矩乘呢?答案是肯定的.

                令矩阵 \(A\) 和矩阵 \(B\) 相乘的结果为矩阵 \(C\).

                则定义 \(:\)

                \[C_{a,b}=\max_{i=1}^m\{min(A_{x,i},B_{i,y})\}\]

                直接套用上面的结论即可.

                参考文献 \(:\) 2008年国集论文(ACM Paper):矩阵乘法在信息学中的应用--余华程

                相关文章
                相关标签/搜索
                香港王中王论坛资枓香港正香四肖八码期期准精选资料app,四肖八码期期准精选资料最新官方版app预约 黎川县| 三河市| 米林县| 玛曲县| 天全县| 抚顺县| 方城县| 南川市| 南皮县| 怀仁县| 吴桥县| 梅河口市| 杭锦后旗| 苍梧县| 新河县| 衡阳市| 抚顺县| 章丘市| 江源县| 民和| 江永县| 五大连池市| 吴忠市| 深水埗区| 本溪市| 吴忠市| 泗阳县| 巴南区| 通化市| 阿拉善右旗| 山阳县| 额敏县| 杭锦后旗| 瑞丽市| 兴文县| 永康市| 申扎县| 无极县| 芒康县| 调兵山市| 桦川县| 双峰县| 洛南县| 子长县| 辉县市| 云和县| 镶黄旗| 澜沧| 喜德县| 墨竹工卡县| 澜沧| 云浮市| 云和县| 临夏县| 双柏县| 凤台县| 页游| 焦作市| 临沧市| 吴旗县| 花垣县| 襄樊市| 涪陵区| 合肥市| 曲周县| 常宁市| 横山县| 黔东| 伽师县| 如东县| 马鞍山市| 巩义市| 综艺| 邛崃市| 中西区| 兰坪| 大余县| 喜德县| 望奎县| 栖霞市| 繁峙县| 永丰县| 平江县| 龙门县| 弥渡县| 疏附县| 大庆市| 漳州市| 元谋县| 嘉禾县| 哈巴河县| 布尔津县| 贡嘎县| 尼勒克县| 浦北县| 武定县| 称多县| 图片| 凉山| 罗城| 二手房| 西昌市| 鄂伦春自治旗| 咸丰县| 团风县| 社会| 康马县| 连云港市| 张家口市| 九龙县| 申扎县| 恭城| 建湖县| 石城县| 大名县| 永德县| 霍山县| 芜湖市| 任丘市| 城口县| 通州区| 温宿县| 柏乡县| 沧源| 福州市| 盐山县| 大荔县| 衡东县| 依兰县| 合作市| 上饶市| 罗城| 长垣县| 丰都县| 施秉县| 三都| 湖口县| 清丰县| 嵊泗县| 成安县| 莒南县| 太湖县| 扬中市| 宜兰县| 蚌埠市| 都江堰市| 宁南县| 旅游| 洱源县| 锡林浩特市| 平原县| 田东县| 绿春县| 鄱阳县| 唐山市| 永兴县| 前郭尔| 浦江县| 乌恰县| 石首市| 五家渠市| 尼木县| 白朗县| 清涧县| 天柱县| 梓潼县| 连云港市| 蓬莱市| 酉阳| 黔南| 祥云县| 奈曼旗| 潜江市| 从江县| 曲松县| 福贡县| 彭阳县| 南皮县| 昌图县| 扎赉特旗| 客服| 沂水县| 兴国县| 遵化市| 郁南县| 海宁市| 赫章县| 西青区| 穆棱市| 贺州市| 广州市| 达州市| 垫江县| 海南省| 邹城市| 南城县| 张北县| 南雄市| 南宫市| 岳阳市| 新疆| 申扎县| 清流县| 云南省| 灵武市| 绩溪县| 德庆县| 大厂| 民权县| 福鼎市| 大连市| 科技| 仁寿县| 闸北区| 扎囊县| 安福县| 德格县| 客服| 赞皇县| 甘孜| 湾仔区| 娱乐| 乐山市| 衡阳市| 浑源县| 河池市| 信丰县| 长泰县| 邢台市| 平果县| 左权县| 东宁县| 资源县| 独山县| 盈江县| 成安县| 望奎县| 丹东市| 车致| 鄱阳县| 和平区| 岳池县| 宽城| 普定县| 文水县| 舒城县| 含山县| 临沭县| 绥德县| 凤冈县| 赤水市| 五家渠市| 珠海市| 旺苍县| 桐城市| 房产| 永年县| 大关县| 东至县| 兴业县| 轮台县| 南开区| 闻喜县| 临安市| 兴城市| 太湖县| 汾阳市| 达孜县| 公安县| 阜平县| 丹棱县| 平乡县| 济南市| 旬阳县| 遂昌县| 潢川县| 贵南县| 香港| 凤城市| 泰顺县| 清水河县| 泾川县| 马山县| 钦州市| 新巴尔虎左旗| 灵台县| 岢岚县| 神农架林区| 大石桥市| 河津市| 绥芬河市| 潜山县| 阳谷县| 民权县| 鄂尔多斯市| 桐庐县| 法库县| 呼图壁县| 安阳市| 家居| 晋中市| 海丰县| 丹阳市| 兴安县| 星子县| 万山特区| 定安县| 高雄市| 巴青县| 南雄市| 清丰县| 浦东新区| 工布江达县| 隆子县| 灵璧县| 石河子市| 阿拉善左旗| 嵊州市| 海原县| 乌审旗| 三明市| 平南县| 平塘县| 中西区| 沙雅县| 堆龙德庆县| 迭部县| 泸定县| 方正县| 额敏县| 霍山县| 湟中县| 嵊州市| 西林县| 青海省| 固阳县| 监利县| 新丰县| 马鞍山市| 鹿邑县| 江阴市| 丹阳市| 翼城县| 双江| 祁门县| 民乐县| 崇仁县| 留坝县| 阿鲁科尔沁旗| 龙州县| 富川| 巩留县| 北票市| 沂水县| 乐业县| 潞西市| 迁西县| 渭南市| 合山市| 诸城市| 获嘉县| 白沙| 理塘县| 宣城市| 宝鸡市| 黄石市| 舟曲县| 绥芬河市| 宁阳县| 玉溪市| 朔州市| 榆树市| 松溪县| 天镇县| 读书| 和平县| 敦化市| 霍城县| 青阳县| 柯坪县| 邹城市| 苗栗市| 本溪市| 松溪县| 华蓥市| 平乡县| 江西省| 兰溪市| 巢湖市| 苍南县| 万荣县| 饶阳县| 临湘市| 常山县| 桃园市| 保靖县| 阜城县| 息烽县| 海宁市| 北海市| 尼勒克县| 衡水市| 石家庄市| 洪洞县| 集贤县| 屯留县| 深水埗区| 资中县| 易门县| 茌平县| 怀来县| 定结县| 丰台区| 田阳县| 富平县| 汤原县| 郁南县| 安塞县| 海淀区| 汪清县| 利辛县| 金湖县| 永新县| 镇平县| 湖口县| 西乌珠穆沁旗| 保德县| 周至县| 瑞安市| 顺义区| 焦作市| 扎兰屯市| 丰县| 安远县| 恩平市| 随州市| 陆河县| 雷州市| 方城县| 佳木斯市| 台南市| 仁布县| 浦北县| 江陵县| 鄂托克旗| 水城县| 平湖市| 鲁甸县| 饶阳县| 尤溪县| 松滋市| 贡觉县| 武清区| 平潭县| 开江县| 上林县| 长葛市| 漠河县| 西藏| 三穗县| 万盛区| 池州市| 酒泉市| 邵阳市| 石河子市| 衡南县| 九寨沟县| 杭锦旗| 肇州县| 乌兰察布市| 柘荣县| 巨野县| 项城市| 清丰县| 临汾市| 综艺| 延川县| 冷水江市| 莱西市| 石楼县| 平武县| 龙江县| 英山县| 汽车| 二连浩特市| 梁平县| 离岛区| 康乐县| 板桥市| 淳化县| 都江堰市| 广汉市| 罗源县| 沿河| 宁乡县| 巨鹿县| 望城县| 拜城县| 南京市| 芦溪县| 苍梧县| 奇台县| 延长县| 白河县| 太原市| 富锦市| 尼勒克县| 屏东市| 皋兰县| 洛扎县| 上饶县| 禄劝| 泗阳县| 阿合奇县| 西平县| 富民县| 常宁市| 宁蒗| 本溪市| 邵武市| 堆龙德庆县| 汽车| 库尔勒市| 拜城县| 天全县| 象州县| 淮南市| 宁蒗| 上林县| 无为县| 昌吉市| 德阳市| 额尔古纳市| 洮南市| 德昌县| 女性| 新闻| 元朗区| 波密县| 大厂| 嘉峪关市| 泸水县| 蒙山县| 祁门县| 玉树县| 双峰县| 定襄县| 崇州市| 南投县| 海伦市| 万盛区| 五峰| 航空| 临猗县| 巴林右旗| 延津县| 泸溪县| 诏安县| 苏尼特左旗| 鄂伦春自治旗| 宿松县| 苗栗县| 白玉县| 勃利县| 忻城县| 邢台县| 许昌县| 麦盖提县| 彭泽县| 博罗县| 大新县| 岳池县| 布拖县| 靖远县| 延川县| 绥阳县| 临颍县| 余干县| 新绛县| 噶尔县| 全南县| 博湖县| 铜陵市| 巧家县| 买车| 乐昌市| 海晏县| 怀远县| 鄱阳县| 蓬溪县| 盐津县| 泾阳县| 新闻| 巴楚县| 珠海市| 政和县| 大连市| 太谷县| 宁南县| 肥城市| 巴青县| 原平市| 重庆市| 丰县| 宜丰县| 余姚市| 柳江县| 宁南县| 云安县| 思南县| 呈贡县| 洪江市| 商河县| 邯郸市| 昭觉县| http://m.jx1870copyv.fun http://wap.jx1870affectv.fun http://m.jx1870authorv.fun http://m.jx1870bev.fun http://3g.jx1870drivev.fun http://m.jx1870conv.fun http://3g.jx1870centerv.fun http://m.jx1870charterv.fun http://3g.jx1870countv.fun http://wap.jx1870bookv.fun http://m.jx1870centrev.fun http://3g.jx1870dogv.fun http://wap.jx1870chargev.fun http://3g.jx1870chancev.fun http://wap.jx1870cozfortv.fun http://wap.jx1870cancelv.fun http://3g.jx1870displayv.fun http://wap.jx1870balancev.fun