[問題] 如何解 池塘邊的木頭 問題

[chrisdar (克里斯)]

現今有一池塘長730米寬與木材同寬，池塘邊有45根長短不一的等寬木頭高為H，
這些等寬木頭一開始的位置為Yi，由於寬度問題容不下兩根木頭同時處在重疊的
區間內，還有由一開始的位置搬到合適的地方推下去需要耗費人力，所以希望不
要搬離開原始的位置太遠(距離越小越好)，想要請問這些木頭需要搬到哪個位置
才能剛剛好推到池塘內而不互相重疊且搬動的距離越小越好。全變數都是整數

抱歉礙於BBS版面我把座標軸轉了方向：  ↑X
0                                     → Y               730
┌────────────────────────────┐
│　　　　　　　　　　　　　　　　　　　　　　　　　　　　│池塘
└────────────────────────────┘
　　　　　　┌───────┐
　　　　　　└───────┘……………
           Yi[i]    H[i]

Yi[45]={60,78,130,151,155,224,236,238,246,260,352,356,394,409,419,429,430,432,
440,446,452,453,464,464,480,517,523,547,634,709,712,712,712,712,712,712,713,
713,713,713,713,718,724,725,725}

H[45]={13,4,10,4,4,7,7,5,3,4,3,5,2,4,3,5,23,6,3,3,5,2,4,2,7,3,23,7,2,19,16,
16,16,16,16,16,15,15,15,15,15,10,4,2,2}

我的想法：暴力法：使用線性規劃軟體  令 Yo[i] 為新的位置
限制式
        0 <= Yo[0]
        Yo[i] + H[i] <= Yo[i+1]       i = 0~43
        Yo[44] + H[44] <= 730
目標函數
        min = abs(Yo[i]-Yi[i])  i = 0~44
可以解到下列這些值
Yo[45]={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}
這時候的總移動距離為 1500

我想問還有沒有其他的演算法或想法能支援這個問題，如果化成動態規畫呢？
我對於動態規畫的模型僅只於背包問題 XD 謝謝各位。

--
推 WalkingIce:我看不懂高度的影響在哪   囧>
可不可以這樣想

假定存在
只能移動一格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，
只能移動兩格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，
...
只能移動1500格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，

那麼問題就回到  如何在有限的移動額度上化解最多的重疊衝突?
※ 編輯: chrisdar        來自: 123.195.68.196       (11/06 07:45)
※ 編輯: chrisdar        來自: 123.195.68.196       (11/06 07:48)
推 bobju:這個題目我有興趣玩玩看.
→ bobju:唔..想了兩個小時, 有一些想法, 但不如跑線
→ bobju:性規劃來得實際.. XP
→ chrisdar:恩  看來一定要跑動態規畫了
→ Lordaeron:哇, 我連題目在講什麼都看不懂呢.
推 bobju:我還是忍不住寫段code來跑看看..
→ chrisdar:可以參考一下您的CODE嗎
→ chrisdar:http://rafb.net/paste/ 可以貼這裡
推 bobju:我用解8 queen的想法去算,果然要求得最小成
→ bobju:本的過程有如天文數字.重新構思中.
→ bobju:求得'可行解'跟求得'最小成本解'層次不一樣.
→ bobju:我還是先貼上去了. 先註明那是失敗作.
推 bobju:我似乎想到如何用動態規劃求解了.晚點再po心
→ bobju:得.

我把資料又重新排序了  用木頭的中點來排序

Yi[45] = { 60, 78,130,151,155,224,236,238,246,260,352,356,394,409,419,
          429,432,430,440,446,453,452,464,464,480,517,523,547,634,709,
          712,712,712,712,712,712,713,713,713,713,713,718,724,725,725  }
 H[45] = { 13,  4, 10,  4,  4,  7,  7,  5,  3,  4,  3,  5,  2,  4,  3,
            5,  6, 23,  3,  3,  2,  5,  2,  4,  7,  3, 23,  7,  2, 19,
           16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 10,  4,  2,  2  }

Solution: 1492
Yo[45] = { 60, 78,130,151,155,224,234,241,246,260,352,356,394,409,413,
          416,421,427,450,453,456,458,464,466,480,487,490,513,520,522,
          541,557,573,589,605,621,637,652,667,682,697,712,722,726,728  }

同樣的模型 不一樣的順序 值變小了    ( 在其他板上獲得的資訊 )
※ 編輯: chrisdar        來自: 123.195.68.196       (11/07 12:42)
推 bobju:我得到的最小成本是1424,但如何把序列dump出
→ bobju:來還在努力中..-_-!
→ chrisdar:可以問一下解法嗎
推 bobju:很樂意, 要表達出來還需整理一下想法. ^^