Re: [問題] 如何解 池塘邊的木頭 問題
我跑出來的結果也是第一組(原始資料) 1500, 第二組(中點排序) 1492,
不過結果序列跟前文當中公布的不太一樣.
Solution: cost=1500:
60,78,130,151,155,224,234,241,246,260,
352,356,394,405,409,412,417,440,446,449,
452,457,464,468,480,487,490,513,520,522,
541,557,573,589,605,621,637,652,667,682,
697,712,722,726,728
Solution: cost=1492:
60,78,130,151,155,224,234,241,246,260,
352,356,394,409,414,417,422,428,451,454,
457,459,464,466,480,487,490,513,520,522,
541,557,573,589,605,621,637,652,667,682,
697,712,722,726,728
其實cost相同, 但結果序列不同是可以預期的, 因為相同cost的結果序列不只
一組而已.
另外, 為什麼排序過的資料跟原始資料的條件相同(位置,長度皆相同), 只是
排列順序不同就產生不同的結果呢? 我猜可能是我們用的演算法是為了簡化問
題的複雜度, 只針對特殊情況求一個大致還可以接受的解, 並沒有真正把所有
的情況都考慮進去.
對於如何解這個問題我是這樣想的:
對於每一個木塊, 都存在一個偏移值, 使得所有的木塊可以兩兩不相重疊.
這個偏移值呢, 是個整數, 其正負隨著木塊往左移或往右移而定, 若木塊不移
動, 則偏移值為0.
如此可以想出, 若將每一個木塊的偏移值依序排開, 應該會是以下這樣:
(D0, D1, D2, ........, D44) , -Zl <= Dn <= Zr , Zl,Zr是整數,其範圍取
決於題目設定的條件: 相鄰的木塊不得重疊(可以相接), 邊界木塊不能跨出河
邊.
由於我們無法預知究竟哪種結果序列可以讓所有木塊可以兩兩不相重疊, 在沒
有公式解之前, 大概是以列舉的方式來思考: 所有情況等於從D0所有可能情況
一路乘到D44的所有可能情況, 可以想像得到這範圍肯定是個天文數字.
要把所有結果序列列舉出來的演算法很容易寫, 就是一個遞迴呼叫函式做深先
搜尋. 以D0為第0層, D1為第1層...逐層傳遞下去(再回傳). 再利用一個迴圈,
從 Zl ~ Zr 的範圍內, 跑遞迴函式把所有情況通通跑完. 演算法像這樣:
triversal(i) {
// your code
for ( Zl[i] to Zr[i] ) {
triversal (i+1)
}
// your code
}
這跑完大概不知是多久以後了, 當然我們也不是要列舉所有情況, 只是在這
個想法的基礎上, 接著引入動態規劃的概念, 計算移動每塊木塊的最小成本.
並且將計算出來的值, 貢獻給後續的運算, 以空間換取時間, 大幅降低上述
演算法的時間複雜度.
(休息一下, 想接著該如何寫..)
接著, 這裏先提出一個假設, 假設這些木塊全部都以'以最左邊的木塊為準,
向左看齊!'的方式來調整彼此的間距, 使得兩兩不互相重疊, 這樣的規則下
去演算, 可以求得最小成本解. 這個假設只是用來方便我們跑程式, 看看跑
出來的解跟運用其它方式跑出來的解互相驗證是否能夠一致.
接著我們再看: 在以上述規則來調整木塊位置的情況下, 為木塊做編號. 因
為'向左看齊'的關係, 所以定義木塊的左端為頭, 右端為尾, 我們描述一
個木塊的位置是以頭的位置為準. 最左邊的木塊為0號, 接著次左的為1號,
再次左的為2號, 由左往右逐次編號, 若有兩塊以上的木塊頭是在同一個位
置, 則隨意編號, 唯一旦編號確定後則不得再改變, 最後一個木塊則為44號.
關於木塊的起始位置以及長度值, 就各別以兩個陣列來存放, 以木塊編號為
索引值.
接下來, 引進'最小成本'的觀念. 在跑程式的過程當中, 只要不與相鄰的木
塊重疊, 木塊是有可以被移動的, 而且可能有很多個位置可以任憑挑選. 當
它被移動時, 產生一個成本: 這個成本是這麼計算的:
木塊[i][位置].成本 = abs(木塊[i].位置 - 木塊[i].起始位置)
我們從木塊[0]開始, 由左向右依序執行移動位置的動作. 輪到木塊[i], 木
塊[i]可動也可不動, 移不移動的依據, 就是不能與其左鄰的木塊重疊, 若是
重疊到, 則必須向右移位, 使其不與左鄰木塊重疊. 木塊[i]定位後, 接著才
能輪到木塊[i+1].
在這個規則下, '擠'出了一個可以用來計算最小成本的重要依據. 也就是對於
一個已經確定位置的木塊[i]而言, 其後的木塊[i+1]到木塊[44]不管怎麼移動
, 它們所產生的成本總和必然為有限, 而且這麼多組成本總和中, 必定存在一
個最小值.
所以對於任意一個木塊[i]而言, 在它所有的可能被安置的位置上, 必然可以
計算出一個'最小成本值'.
木塊[i][位置].最小成本值 =
木塊[i][位置].成本 + min(總成本1(木塊[i+1]..木塊[44]),總2,..,總n)
木塊[i][位置].最小成本值必定是一個定值, 不可能變動. 所以當我們以遞
迴深先拜訪的方式, 從左到右掃過每一個木塊時, 每一個木塊在其可能被移
動到的位置上, 都能夠經由遞迴函式的返回所回傳的最小總成本值, 加上其
本身的成本值而計算出其在該位置上的最小成本值. 這個最小成本值用一個
資料結構記起來, 當稍後在遞迴函式的遊迴歷程中這個木塊在這個位置又被
重複拜訪到(會被重複拜訪到好幾遍)的時候, 其最小成本值只需第一次計算
到, 以後皆可重複使用, 不需再經遞迴歷程計算.. 如此可以有效降低遞迴
函式遊迴的時間複雜度.
(再休息一下, 剩最後一個階段)
當計算每一個木塊在某個位置時所產生的最小成本的方式確定後, 接著就是
將遞迴函式的主體寫出來, 以及一些處理細節的小程序. 它的主要功能是把
"(木塊編號,位置,最小成本)關聯表"建立起來, 以供後段應用.
當"(木塊編號, 位置, 最小成本)關聯表"建立起來以後, 只要
觀察木塊[0]的所有位置所各自對應的最小成本, 再從中取最小值, 就是題
目所要的答案了. 至於展開所有木塊的位置所形成的結果序列, 也是從這個
關聯表下去演算. 能夠符合最小成本的結果序列應該還蠻多組的, 有空有需
要的話再撈看看.
後述:
上述解這個問題所採用的演算法, 未必能夠保證得到的就是最小成本解. 除
了必要的數學證明需要更深厚的功底外, 還有兩個原因是: 一, 我只採用
'向左看齊'去跑(而且還鎖定第0個木塊不移動, 這做了太多限制了), 沒有採
用'向右看齊'去跑, 誰能證明這兩種方式等價呢? 而且又該如何證明其必然
包含木塊的所有移動的情況呢? 二, 同樣的一堆木塊, 因為運算順序不同而
導致算出來的結果不同, 這在實務上大概也無法讓人覺得信服. 所以說, 革
命尚未成功, 同志仍需努力. 相信應該有更完整的solution, 不過我大概已
經沒有戰力再繼續try下去了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.253.114
※ 編輯: bobju 來自: 211.74.253.114 (11/08 02:27)
※ 編輯: bobju 來自: 211.74.253.114 (11/08 02:29)
※ 編輯: bobju 來自: 211.74.253.114 (11/08 07:26)
※ 編輯: bobju 來自: 211.74.253.114 (11/08 08:07)
推
11/13 02:56, , 1F
11/13 02:56, 1F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
問題
7
19