[理工] 矩陣乘法次數

作者: 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)

Links booklink

Contact Us: admin [ a t ] ucptt.com