[理工] 矩陣乘法次數

[TEPLUN (mihanami)]

https://i.imgur.com/5vgH8nd.jpg
不知道是不是我視力欠佳
請問24題有講怎麼用greedy解嗎

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.7.120
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545574535.A.FC4.html
推 f255577:  https://i.imgur.com/2TkPXK4.jpg
→ f255577: 沒有遞迴下去看是否成本最小，所以greedy解會變成單純拆
→ f255577: 兩邊
→ TEPLUN: 不太懂為什麼可以這樣拆欸 大大畫的那張圖剛好最右是1*1
→ TEPLUN:  是純量可以直接提出來 如果是d*d呢？而且這樣比較像divid
→ TEPLUN: e and conquer?
→ TEPLUN: greedy應該是像是 從矩陣左邊開始往右掃 依某種條件比如遇
→ TEPLUN: 到1*1或1*d這種能縮減乘法次數的矩陣就做紀錄 最後直接得
→ TEPLUN: 出這個矩陣乘法的最佳解？
推 f255577: 我的看法是greedy策略在於每一輪儘量切出頭尾剛好是1*1
→ f255577: 的區塊，找不到才切1*d甚至d*d
→ TEPLUN: 我也有這樣想過 不過這樣每次掃都要都要花O(n)的時間來找
→ TEPLUN: 出有1的矩陣項
推 f255577: 掃的迴圈可以和切的迴圈分開的話應該還是O(n)+O(n^2)=O(n
→ f255577: ^2)