[理工] 矩陣乘法次數 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)

繼續閱讀