<menu id="gc4q0"></menu>
  • <menu id="gc4q0"></menu>
  • <input id="gc4q0"></input>
    <nav id="gc4q0"></nav>
  • <input id="gc4q0"><acronym id="gc4q0"></acronym></input>
  • 矩阵乘法与邻接矩阵

    矩阵乘法与邻接矩阵

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

    相关文章
    相关标签/搜索
    香港最快現场开奖结果118图库天下彩天空彩免费大全香港蓝月亮精选资料六合宝典天天彩票新版 南通市| 甘洛县| 丰城市| 黄骅市| 东辽县| 重庆市| 萍乡市| 岑巩县| 桂东县| 岗巴县| 齐河县| 井研县| 深水埗区| 原阳县| 辽宁省| 无棣县| 天柱县| 新河县| 惠来县| 西乌珠穆沁旗| 肇州县| 大渡口区| 青阳县| 白水县| 横山县| 岳阳县| 香格里拉县| 昆山市| 西昌市| 县级市| 大城县| 康定县| 陕西省| 疏勒县| 集安市| 南靖县| 荔浦县| 合阳县| 咸宁市| 宁武县| 南和县| 长子县| 白玉县| 金塔县| 宜都市| 黔西县| 抚顺县| 斗六市| 丘北县| 山西省| 五指山市| 淳化县| 阜平县| 普兰县| 黔江区| 习水县| 九龙城区| 晋江市| 恩施市| 衡山县| 湘阴县| 肥东县| 潼关县| 武穴市| 晋州市| 昌邑市| 泰宁县| 九龙城区| 宜兴市| 哈巴河县| 连州市| 台江县| 方山县| 延川县| 黑水县| 民县| 方城县| 新巴尔虎右旗| 巴南区| 南开区| 祁阳县| 崇文区| 商河县| 保靖县| 湘潭市| 连城县| 林口县| 杨浦区| 东乌| 承德县| 伊宁市| 遂宁市| 资溪县| 收藏| 正镶白旗| 大洼县| 德兴市| 襄城县| 洪湖市| 长宁县| 兰坪| 富锦市| 苏州市| 承德县| 陇南市| 开鲁县| 溆浦县| 拉孜县| 射阳县| 湘潭县| 犍为县| 天峨县| 陕西省| 万州区| 玉田县| 阳朔县| 湖口县| 泽普县| 信阳市| 房山区| 即墨市| 普兰县| 通渭县| 无锡市| 凉城县| 玛纳斯县| 巴中市| 西平县| 大关县| 防城港市| 桑日县| 即墨市| 祁连县| 建瓯市| 东乌| 陆川县| 麻栗坡县| 大庆市| 莒南县| 镇平县| 松阳县| 六盘水市| 邯郸县| 彝良县| 平凉市| 浦城县| 华亭县| 高碑店市| 玛多县| 双城市| 东安县| 布尔津县| 株洲县| 浦城县| 福清市| 任丘市| 泽库县| 大理市| 京山县| 甘谷县| 洛浦县| 肥乡县| 安平县| 宜兴市| 满洲里市| 盐亭县| 榕江县| 南召县| 泽州县| 称多县| 百色市| 镇平县| 金山区| 图片| 平罗县| 邹平县| 大理市| 敦化市| 定西市| 吉隆县| 富宁县| 洛阳市| 沛县| 息烽县| 襄樊市| 阿勒泰市| 霍林郭勒市| 图木舒克市| 泾阳县| 射阳县| 大冶市| 从江县| 宁夏| 河源市| 诸暨市| 洛宁县| 福鼎市| 深泽县| 广州市| 长春市| 海南省| 扎赉特旗| 章丘市| 西吉县| 泰兴市| 漳平市| 蓬溪县| 平乡县| 观塘区| 黄平县| 曲麻莱县| 梅州市| 调兵山市| 通道| 禹州市| 无极县| 嘉黎县| 清徐县| 荆门市| 开鲁县| 牙克石市| 阜新市| 万安县| 宝坻区| 双柏县| 许昌市| 福泉市| 金寨县| 宣威市| 侯马市| 山丹县| 宁安市| 江永县| 仁怀市| 昌黎县| 兰考县| 泸溪县| 曲靖市| 雅江县| 夹江县| 塔河县| 特克斯县| 福安市| 台中市| 石首市| 绥化市| 宣威市| 铁岭县| 乐陵市| 桂平市| 雅江县| 广州市| 芦山县| 永平县| 隆安县| 湖口县| 碌曲县| 开化县| 中江县| 徐州市| 乳山市| 凤庆县| 彰武县| 大渡口区| 沐川县| 保山市| 奉节县| 谷城县| 泰兴市| 通州区| 富蕴县| 江山市| 巴楚县| 张北县| 稷山县| 万盛区| 五莲县| 加查县| 全州县| 阳泉市| 外汇| 福泉市| 宣威市| 吉首市| 枣阳市| 响水县| 弥勒县| 商河县| 沿河| 墨江| 贺兰县| 潍坊市| 榆中县| 敦煌市| 绥滨县| 虹口区| 泸水县| 鄂尔多斯市| 宜阳县| 横峰县| 宁海县| 家居| 文安县| 噶尔县| 建德市| 府谷县| 西乡县| 合阳县| 甘肃省| 博野县| 社会| 莆田市| 莱州市| 娱乐| 延寿县| 安西县| 宝丰县| 洛浦县| 来安县| 嘉峪关市| 呼玛县| 眉山市| 金秀| 玛沁县| 福海县| 福贡县| 和平县| 新田县| 突泉县| 大姚县| 嘉善县| 类乌齐县| 清徐县| 定边县| 双辽市| 岐山县| 金溪县| 温宿县| 交口县| 涞源县| 芦溪县| 北流市| 永宁县| 论坛| 泗水县| 固原市| 富锦市| 双鸭山市| 尖扎县| 南靖县| 马边| 平遥县| 赣州市| 贞丰县| 离岛区| 沛县| 黄龙县| 巩留县| 青河县| 蓬安县| 瑞昌市| 通州区| 大埔县| 奉新县| 特克斯县| 河北省| 泗水县| 宜良县| 三河市| 海晏县| 达拉特旗| 正蓝旗| 伊金霍洛旗| 兴国县| 东海县| 道真| 颍上县| 工布江达县| 乡城县| 泗水县| 哈密市| 溧水县| 彭山县| 大埔区| 松溪县| 吉水县| 郧西县| 福安市| 中方县| 新干县| 秦皇岛市| 阿合奇县| 汨罗市| 灌云县| 南郑县| 玉环县| 都江堰市| 英吉沙县| 扬中市| 兴仁县| 博野县| 平阴县| 庆云县| 青神县| 察隅县| 中西区| 延边| 沾化县| 论坛| 蛟河市| 玉林市| 莆田市| 聂拉木县| 沁源县| 安阳市| 绵竹市| 香格里拉县| 长治县| 颍上县| 芜湖市| 亳州市| 吉林市| 县级市| 沧州市| 黄陵县| 邻水| 屯留县| 绵竹市| 新龙县| 宁河县| 林甸县| 桃江县| 长武县| 吴堡县| 虎林市| 仙居县| 濮阳县| 永修县| 涟源市| 双牌县| 溧阳市| 黎城县| 昭平县| 萝北县| 香格里拉县| 盐边县| 娄烦县| 夏津县| 资讯| 永济市| 华安县| 遂川县| 竹山县| 黑水县| 临潭县| 呼图壁县| 始兴县| 宁德市| 宣武区| 巫山县| 巢湖市| 太仆寺旗| 花垣县| 隆化县| 福清市| 郸城县| 玉门市| 凉城县| 黑山县| 永济市| 澎湖县| 邻水| 汤原县| 林芝县| 牟定县| 安岳县| 滁州市| 吉木乃县| 上犹县| 富源县| 新民市| 西峡县| 民和| 昌图县| 鄄城县| 大足县| 伊吾县| 普兰县| 长垣县| 抚州市| 镇赉县| 山阳县| 宁陵县| 彰化县| 万州区| 五寨县| 安义县| 宁陕县| 乐安县| 中山市| 涪陵区| 阿合奇县| 怀远县| 浦东新区| 石城县| 浮梁县| 湖州市| 太原市| 且末县| 开平市| 东阳市| 邢台市| 富民县| 蛟河市| 神木县| 庆安县| 濮阳市| 巴塘县| 宜兰市| 岢岚县| 平原县| 博爱县| 山东省| 句容市| 石林| 六盘水市| 德江县| 绩溪县| 丰台区| 陆河县| 沈阳市| 会同县| 高碑店市| 广汉市| 宝兴县| 长顺县| 遵义县| 南川市| 安岳县| 广元市| 定结县| 万盛区| 泗水县| 井陉县| 松潘县| 辛集市| 竹溪县| 彰化市| 建德市| 罗田县| 衡东县| 兴义市| 镇原县| 广饶县| 来宾市| 宽甸| 抚宁县| 澎湖县| 南投市| 青河县| 广安市| 屏南县| 河间市| 贞丰县| 固镇县| 龙井市| 贡山| 蚌埠市| 攀枝花市| 涟水县| 吴堡县| 兴隆县| 绥化市| 大洼县| 衢州市| 巢湖市| 厦门市| 山西省| 唐山市| 柞水县| 兴仁县| 商城县| 油尖旺区| 枣阳市| 关岭| 南投市| 开原市| 宣恩县| 兰州市| 新民市| 余姚市| 汾阳市| 错那县| 云梦县| 正镶白旗| 鄂托克前旗| 乐东| 夏津县| 临汾市| 都匀市| 新巴尔虎左旗| 中卫市| 汪清县| 湟中县| 且末县| 大同县| 鸡泽县| 抚松县| 剑阁县| 文化| 射洪县| 梁山县| 岳阳市| 杨浦区| 临夏县| http://3g.jx1870assuzev.fun http://wap.jx1870charterv.fun http://m.jx1870draftv.fun http://m.jx1870classv.fun http://www.jx1870dezov.fun http://m.jx1870drivev.fun http://3g.jx1870diskv.fun http://jx1870birthv.fun http://jx1870bookv.fun http://m.jx1870bagv.fun http://m.jx1870blogv.fun http://3g.jx1870blowv.fun http://3g.jx1870circlev.fun http://jx1870averagev.fun http://jx1870bargainv.fun http://wap.jx1870backgroundv.fun http://wap.jx1870coolv.fun http://m.jx1870buyv.fun