[理工] 矩陣乘法次數

看板Grad-ProbAsk作者 (mihanami)時間7年前 (2018/12/23 22:15), 編輯推噓3(3推 0噓 12→)
留言15則, 2人參與, 7年前最新討論串1/1
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
推
12/23 23:59, 7年前 , 1F
12/23 23:59, 1F
→
12/24 00:00, 7年前 , 2F
沒有遞迴下去看是否成本最小，所以greedy解會變成單純拆
12/24 00:00, 2F
→
12/24 00:00, 7年前 , 3F
兩邊
12/24 00:00, 3F
→
12/24 00:26, 7年前 , 4F
不太懂為什麼可以這樣拆欸 大大畫的那張圖剛好最右是1*1
12/24 00:26, 4F
→
12/24 00:26, 7年前 , 5F
是純量可以直接提出來 如果是d*d呢？而且這樣比較像divid
12/24 00:26, 5F
→
12/24 00:26, 7年前 , 6F
e and conquer?
12/24 00:26, 6F
→
12/24 00:31, 7年前 , 7F
greedy應該是像是 從矩陣左邊開始往右掃 依某種條件比如遇
12/24 00:31, 7F
→
12/24 00:31, 7年前 , 8F
到1*1或1*d這種能縮減乘法次數的矩陣就做紀錄 最後直接得
12/24 00:31, 8F
→
12/24 00:31, 7年前 , 9F
出這個矩陣乘法的最佳解？
12/24 00:31, 9F
推
12/24 08:24, 7年前 , 10F
我的看法是greedy策略在於每一輪儘量切出頭尾剛好是1*1
12/24 08:24, 10F
→
12/24 08:24, 7年前 , 11F
的區塊，找不到才切1*d甚至d*d
12/24 08:24, 11F
→
12/24 11:10, 7年前 , 12F
我也有這樣想過 不過這樣每次掃都要都要花O(n)的時間來找
12/24 11:10, 12F
→
12/24 11:10, 7年前 , 13F
出有1的矩陣項
12/24 11:10, 13F
推
12/24 12:18, 7年前 , 14F
掃的迴圈可以和切的迴圈分開的話應該還是O(n)+O(n^2)=O(n
12/24 12:18, 14F
→
12/24 12:18, 7年前 , 15F
^2)
12/24 12:18, 15F
‣ 更多 TEPLUN 的文章
文章代碼(AID): #1S7vY7_4 (Grad-ProbAsk)