[問題] 如何解 池塘邊的木頭 問題
看板Prob_Solve (計算數學 Problem Solving)作者chrisdar (克里斯)時間16年前 (2008/11/05 21:43)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/8 (看更多)
現今有一池塘長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 謝謝各位。
可不可以這樣想
假定存在
只能移動一格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，
只能移動兩格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，
...
只能移動1500格就來完成任務，那麼這時候要怎麼移動才會重疊量最小，
那麼問題就回到 如何在有限的移動額度上化解最多的重疊衝突?
※ 編輯: chrisdar 來自: 123.195.68.196 (11/06 07:44)
※ 編輯: chrisdar 來自: 123.195.68.196 (11/06 07:48)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
