[理工] 矩阵乘法次数 TEPLUN PTT批踢踢实业坊

楼主: TEPLUN (mihanami) 2018-12-23 22:15:32

https://i.imgur.com/5vgH8nd.jpg
不知道是不是我视力欠佳
请问24题有讲怎么用greedy解吗

作者: f255577 (沈大妈) 2018-12-23 23:59:00

https://i.imgur.com/2TkPXK4.jpg没有递回下去看是否成本最小，所以greedy解会变成单纯拆两边

楼主: TEPLUN (mihanami) 2018-12-24 00:26:00

不太懂为什么可以这样拆欸大大画的那张图刚好最右是1*1是纯量可以直接提出来如果是d*d呢？而且这样比较像divide and conquer?greedy应该是像是从矩阵左边开始往右扫依某种条件比如遇到1*1或1*d这种能缩减乘法次数的矩阵就做纪录最后直接得出这个矩阵乘法的最佳解？

作者: f255577 (沈大妈) 2018-12-24 08:24:00

我的看法是greedy策略在于每一轮尽量切出头尾刚好是1*1的区块，找不到才切1*d甚至d*d

楼主: TEPLUN (mihanami) 2018-12-24 11:10:00

我也有这样想过不过这样每次扫都要都要花O(n)的时间来找出有1的矩阵项

作者: f255577 (沈大妈) 2018-12-24 12:18:00

扫的循环可以和切的循环分开的话应该还是O(n)+O(n^2)=O(n^2)

继续阅读