矩阵乘法与邻接矩阵

              矩阵乘法与邻接矩阵

              矩乘结合律的证明 \(:\)
              \[\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):矩阵乘法在信息学中的应用--余华程

              相关文章
              相关标签/搜索
              香港蓝月亮精选免费资料大全管家婆王中王鉄算盘开奖结果2019开奖记录结果查询香港马会开奖结果历史纪录在线查询 普洱| 潮州市| 子洲县| 陇西县| 中超| 玉林市| 青冈县| 县级市| 东山县| 凤山县| 兴仁县| 临高县| 广元市| 商水县| 通化市| 哈巴河县| 云南省| 土默特左旗| 博乐市| 东明县| 上林县| 海林市| 嘉禾县| 延长县| 大荔县| 恭城| 连云港市| 眉山市| 泰州市| 岐山县| 金乡县| 衡水市| 桑日县| 西城区| 桑植县| 兰考县| 勐海县| 油尖旺区| 阿城市| 蓬安县| 新野县| 垦利县| 蛟河市| 临泉县| 东乌| 万宁市| 惠州市| 大洼县| 普安县| 太谷县| 潢川县| 清水县| 拜泉县| 海门市| 若尔盖县| 南昌市| 汝城县| 盐池县| 贺州市| 荥阳市| 武川县| 承德县| 芦溪县| 弥勒县| 卢龙县| 孝昌县| 民乐县| 绥棱县| 定结县| 泾川县| 象州县| 江阴市| 专栏| 积石山| 九龙坡区| 子洲县| 民权县| 万盛区| 禄劝| 蒙山县| 紫阳县| 永清县| 河曲县| 浦东新区| 昌宁县| 昌都县| 广昌县| 富裕县| 乌鲁木齐市| 民和| 襄城县| 孟连| 巴青县| 南乐县| 连州市| 百色市| 那曲县| 尖扎县| 巴彦淖尔市| 云阳县| 汉寿县| 万全县| 桐梓县| 泰和县| 南开区| 祁阳县| 仁怀市| 昂仁县| 家居| 长沙县| 贵阳市| 察哈| 枞阳县| 平度市| 社旗县| 高唐县| 永丰县| 吴江市| 沙田区| 瑞丽市| 邵武市| 循化| 小金县| 沛县| 宜君县| 乌兰县| 邯郸县| 安溪县| 闵行区| 安阳市| 封开县| 成都市| 响水县| 手游| 阿拉善盟| 福清市| 芷江| 晋中市| 安阳县| 密云县| 呼和浩特市| 衡南县| 克拉玛依市| 宝山区| 绩溪县| 固始县| 济宁市| 郓城县| 安西县| 德保县| 化州市| 拉萨市| 石城县| 河津市| 米泉市| 通城县| 哈密市| 大名县| 英超| 綦江县| 中卫市| 乐至县| 舞阳县| 南涧| 保亭| 扎兰屯市| 灌阳县| 漳州市| 宽甸| 库尔勒市| 阿巴嘎旗| 阿巴嘎旗| 阿巴嘎旗| 锡林浩特市| 民县| 大港区| 怀远县| 黑龙江省| 吴忠市| 应用必备| 宜都市| 瑞安市| 乌兰县| 易门县| 长汀县| 龙陵县| 屏东市| 萝北县| 德格县| 潢川县| 筠连县| 桃园市| 浮山县| 汉中市| 饶平县| 宁化县| 云霄县| 明星| 辽阳县| 汶川县| 霍林郭勒市| 会宁县| 鹰潭市| 安化县| 汕头市| 芷江| 福泉市| 曲水县| 蓬安县| 三都| 安远县| 石台县| 正蓝旗| 贵定县| 通榆县| 华池县| 二连浩特市| 凤庆县| 清流县| 班戈县| 和硕县| 阿克苏市| 会同县| 新余市| 许昌县| 泰兴市| 克什克腾旗| 平湖市| 林甸县| 松原市| 奇台县| 慈利县| 渭南市| 晋州市| 松滋市| 康马县| 都兰县| 银川市| 灵石县| 石林| 尚志市| 遂川县| 汤原县| 故城县| 静乐县| 读书| 阿勒泰市| 绥化市| 自治县| 集贤县| 江津市| 元氏县| 惠安县| 毕节市| 清涧县| 家居| 镇远县| 昂仁县| 镇原县| 织金县| 清远市| 依兰县| 嘉黎县| 五河县| 紫阳县| 南漳县| 溧阳市| 静宁县| 屏南县| 阿克陶县| 新龙县| 和田县| 抚顺县| 灵璧县| 沭阳县| 奉新县| 东乌珠穆沁旗| 洮南市| 屏南县| 科技| 虎林市| 安康市| 厦门市| 揭西县| 拜城县| 东台市| 吉林省| 许昌市| 中牟县| 钦州市| 闽侯县| 广丰县| 绍兴县| 蚌埠市| 神池县| 龙里县| 依兰县| 靖州| 曲麻莱县| 高邑县| 南通市| 黔江区| 罗江县| 城固县| 沙田区| 平谷区| 通州区| 岳普湖县| 双牌县| 民权县| 伊金霍洛旗| 高淳县| 金川县| 博湖县| 宿松县| 富顺县| 容城县| 合肥市| 丹寨县| 伊通| 安龙县| 长寿区| 玉林市| 南召县| 垣曲县| 和政县| 临泽县| 揭东县| 涞源县| 天等县| 汤原县| 双峰县| 兴文县| 古浪县| 鄂托克前旗| 浦北县| 吴堡县| 临泽县| 尉犁县| 紫阳县| 盐亭县| 镇宁| 上思县| 临泉县| 嫩江县| 旺苍县| 光泽县| 若羌县| 叶城县| 怀宁县| 乐山市| 清原| 陆河县| 南溪县| 江油市| 石门县| 津市市| 德安县| 江西省| 铜山县| 历史| 双辽市| 桐梓县| 建昌县| 巫溪县| 临江市| 米易县| 酒泉市| 张家口市| 多伦县| 固始县| 从江县| 大理市| 织金县| 新和县| 乌什县| 莫力| 胶州市| 吉木乃县| 昆山市| 蓬溪县| 城市| 乌鲁木齐市| 永德县| 九江市| 汶川县| 青铜峡市| 怀安县| 农安县| 四平市| 兰坪| 永兴县| 兰西县| 伽师县| 湘阴县| 安泽县| 新野县| 高阳县| 文登市| 酒泉市| 包头市| 中牟县| 南充市| 波密县| 澳门| 濉溪县| 京山县| 宁德市| 枞阳县| 西城区| 梁平县| 五寨县| 西青区| 怀集县| 姜堰市| 千阳县| 南召县| 防城港市| 龙里县| 鸡东县| 华容县| 营山县| 丹巴县| 礼泉县| 永寿县| 嘉鱼县| 阿拉善左旗| 河津市| 济源市| 体育| 阿拉善右旗| 乌鲁木齐市| 峨眉山市| 疏附县| 大连市| 临颍县| 崇左市| 龙陵县| 台北市| 谢通门县| 楚雄市| 九龙坡区| 桂阳县| 珲春市| 封开县| 遂川县| 方山县| 龙州县| 苏尼特左旗| 吴堡县| 绩溪县| 儋州市| 西和县| 武邑县| 闵行区| 慈溪市| 嘉兴市| 绍兴县| 九江县| 宿迁市| 突泉县| 苍溪县| 连州市| 安新县| 丰顺县| 唐山市| 高唐县| 洛扎县| 云梦县| 鲁甸县| 都兰县| 大名县| 芷江| 南岸区| 伊吾县| 旬邑县| 伊宁市| 于田县| 洪江市| 新巴尔虎右旗| 黄骅市| 玛纳斯县| 城口县| 平定县| 兖州市| 商洛市| 桦甸市| 含山县| 石渠县| 永善县| 会宁县| 新乐市| 武安市| 轮台县| 清涧县| 德州市| 额尔古纳市| 蒙城县| 科技| 安泽县| 芒康县| 集安市| 岳池县| 玛沁县| 上虞市| 咸宁市| 西宁市| 专栏| 仲巴县| 盈江县| 资阳市| 仪陇县| 沅陵县| 青冈县| 阿瓦提县| 通海县| 政和县| 蒙自县| 绩溪县| 桃江县| 类乌齐县| 聂拉木县| 乌苏市| 二手房| 临汾市| 双江| 静宁县| 托克逊县| 宁城县| 民和| 永定县| 台安县| 正宁县| 十堰市| 乌拉特前旗| 东台市| 马关县| 鄂托克旗| 社旗县| 龙山县| 措勤县| 温泉县| 桓台县| 宜丰县| 桃江县| 醴陵市| 遂川县| 阿巴嘎旗| 运城市| 三原县| 高密市| 安阳县| 灵武市| 满洲里市| 徐闻县| 剑河县| 牙克石市| 镇江市| 夏津县| 沙洋县| 武冈市| 阆中市| 枣阳市| 宁武县| 宜川县| 波密县| 平利县| 闵行区| 阳曲县| 堆龙德庆县| 荥阳市| 南郑县| 盘锦市| 赣州市| 民权县| 徐闻县| 黄冈市| 郁南县| 错那县| 日土县| 西乡县| 新田县| 阳谷县| 吴江市| 科技| 金溪县| 昌江| 吉安县| 个旧市| 杭锦后旗| 东源县| 且末县| 通州市| 渭源县| 朔州市| 江山市| 泰安市| 松溪县| 临泉县| 双城市| 乌鲁木齐县| 隆尧县| 石屏县| 金寨县| 榆林市| 鹰潭市| 内丘县| 应城市| 油尖旺区| 井冈山市| 东安县| 吴川市| 文昌市| 会昌县| 安仁县| http://wap.bfkcwd.fit http://wap.bm1961xountz.fit http://wap.bm1961longz.fit http://www.jdylsl.fit http://www.aeyxap.fit http://wap.jmipms.fit http://m.mnffwe.fit http://wap.xtinkz.fit http://wap.weepqx.fit http://ecigax.fit http://wap.acwxhc.fit http://bm1961naxez.fit http://www.gnytex.fit http://ijebhfit http://www.hjdyni.fit http://mfjxmv.fit http://www.punpsk.fit http://ijrtpz.fit