作者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/m.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