作者TEPLUN (mihanami)
看板Grad-ProbAsk
标题[理工] 矩阵乘法次数
时间Sun Dec 23 22:15:32 2018
https://i.imgur.com/5vgH8nd.jpg
不知道是不是我视力欠佳
请问24题有讲怎麽用greedy解吗
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.160.7.120
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1545574535.A.FC4.html
2F：→ f255577: 没有递回下去看是否成本最小，所以greedy解会变成单纯拆 12/24 00:00
3F：→ f255577: 两边 12/24 00:00
4F：→ TEPLUN: 不太懂为什麽可以这样拆欸 大大画的那张图刚好最右是1*1 12/24 00:26
5F：→ TEPLUN: 是纯量可以直接提出来 如果是d*d呢？而且这样比较像divid 12/24 00:26
6F：→ TEPLUN: e and conquer? 12/24 00:26
7F：→ TEPLUN: greedy应该是像是 从矩阵左边开始往右扫 依某种条件比如遇 12/24 00:31
8F：→ TEPLUN: 到1*1或1*d这种能缩减乘法次数的矩阵就做纪录 最後直接得 12/24 00:31
9F：→ TEPLUN: 出这个矩阵乘法的最佳解？ 12/24 00:31
10F：推 f255577: 我的看法是greedy策略在於每一轮尽量切出头尾刚好是1*1 12/24 08:24
11F：→ f255577: 的区块，找不到才切1*d甚至d*d 12/24 08:24
12F：→ TEPLUN: 我也有这样想过 不过这样每次扫都要都要花O(n)的时间来找 12/24 11:10
13F：→ TEPLUN: 出有1的矩阵项 12/24 11:10
14F：推 f255577: 扫的回圈可以和切的回圈分开的话应该还是O(n)+O(n^2)=O(n 12/24 12:18
15F：→ f255577: ^2) 12/24 12:18