Re: [問題] 請問有關鋸木問題寫成程式比較快的方法

[king19880326 (OK的啦～我都可以接受)]

※ 引述《king19880326 (OK的啦～我都可以接受)》之銘言：
※ [本文轉錄自 C_and_CPP 看板]

作者: king19880326 (OK的啦～我都可以接受) 看板: C_and_CPP
標題: [問題] 請問有關鋸木問題寫成程式比較快的方法
時間: Mon Apr 27 08:51:15 2009

/*** 這是引文 ********
*題目敘述如下
*
*有一個木頭, 長度是 L, 假設位於座標 (0, L)中間, 現給 n 個點 p1, p2...pn
*
*0 <= pi <= L (1 <= i <= n). 希望可以將原本的木頭切成這 n+1 段
*
*現在定義切木頭的cost如下 : 如果木頭長度是 L1, 則切此木頭的 cost 就是L1
*
*(不論切在哪一個點). 試問該用何種順序才能使得切出這 n+1 段的 cost 為最小
*
*  舉例:
*
*  假設木頭位於 (0, 9) 要切的 3 個點 分別為 3, 4, 8
*
*  則如果由右往左切 cost 為 9(0 -> 9 中切 3 這個位置) + 6(3 -> 9中切 4 這
*
*  個位置) + 5(4 -> 9中切 8 這個位置) = 20
*
*  如果是由左往右切 cost 為 9(0 -> 9 中切 8 這個位置) + 8(0 -> 8中切 4 這
*
* 個位置 + 4(0 -> 4中切 3 這個位置) = 21
*
*我的想法如下 :
*
*定義 P(i,j) 為 (1 <= i <= n, 1 <= j <= n)  為 切第 i 刀時, 所切的位置在
*
*j 的 cost 最小.
*
*以下是一個簡單的觀察 : min{P(n,1), P(P,2), ... P(n,n)} = 所求
*
*(因為共要切 n 刀,  而第 n-1 刀有可能是切在 p1, p2, ...pn 這 n 種可能)
*
*P(i, j) = min{P(i-1,1) + 切在 j 的代價, P(i-1, 2) 切在 j 的代價, ...P(i-1,n)
*
* + 切在 j 的代價} (令P(i-1,j) = 負無限大)
*
*P(1, j) = L (1 <= j <= n)
*
*因此用 DP 填表格的方式 共 n * n 格要填
*
*填每一格需要的時間複雜度 為 O(n)
*
*所以時間複雜度是 O(n^3)
*
*這樣的時間複雜度好像有點高 @@>, 請問有什麼方法可以把它的時間複雜度往下降嗎??
*
*感謝感謝
*
*****引文結束*******/
自問自答一下 <(__)>

就像bobju 大大的說法, 之前的 P(i, j) = min{P(i-1,1) + 切在 j 的代價, P(i-1, 2) 切在 j 的代價, ...P(i-1,n)

 + 切在 j 的代價} (令P(i-1,j) = 負無限大) 這個式子並不保證每一格可以在 O(n)

填入. 事實上我也還沒想到簡明的方法去 implement(希望版友如果有想到可以提供

<(__)>)

如果我們從另外一個方向去做 DP, 似乎就顯得好處理多了

方法如下:

假設 input 的長度是 20, 共切 4 刀, 切在 2, 6, 8, 16等處 (將位置排序, O(nlogn))

之前是從"刀數"去做DP, 現在改從"段"去做DP

所以我們可以把整個木頭看成如下這個圖:
  ___________________
 |___|___|___|___|___|
 0   2   6   8   16  20
  \ / \ / \ / \ / \ /
   1   2   3   4   5   <-這是將每"段"木頭編號

我們定義 cut_left[i] = 第 i 段木頭的左端點

         ex. cut_left[1] = 0, cut_left[2] = 2,...cut_left[5] = 16  (O(n))

         cut_right[i] = 第 i 段木頭的右端點

         ex. cut_right[1] = 2, cut_right[2] = 6,...cut_right[5] = 20 (O(n))

且定義 C[i,j] 為 i, i+1, ...j-1, j 這段木頭 切割所需要的最小 cost

現在我們可以有兩個簡單的觀察:

1. C[1,n+1] = 所求 (n 為共需要切割的刀數)

2. C[i,j] = min{ C[i,i]+C[i+1,j], C[i,i+1]+C[i+2,j]...,C[i,j-1]+C[j,j] } +

            cut_right[j] - cut_left[i] (註1)                     (if i < j)

          => min{ C[i,k]+C[k+1,j] } + cut_right[j] - cut_left[i] (if i != j)
           i<=k<=j-1

          = 0                                                 (if i == j)

          = -無限大                                           (if i > j)

因此我們可以開始用 DP 填表格的方式, 填一個 n * n 的表格

且填每一格所需的時間為 O(n)

故時間複雜度為 O(n^3)

(註1) C[i,j] 當 i > j時, 表示這段木頭並不是atomic, 即可切割

     因此可以將C[i,j] 切割成 C[i,k], C[k+1,j] (註2)(i<=k<=j-1). 而將 C[i,j]

     劃分成兩塊的 cost 為 cut_right[j]-cut_left[i]

(註2) 為甚麼將 C[i,j] 劃分成的兩段木頭 L1 : i,i+1,...k 及 L2 : k+1,k+2...j

      所切割的 cost (令為L1[i,k],L2[k+1,j]) 必定要是 C[i,k],C[k+1,j](最小

      成本)?

      假設 C[i,j] 劃分出來的兩段 L1, L2 有一邊所切割的 cost 不為最小成本

      因為若其中有一段不是最小成本(設為L1[i,k], 因此 C[i,j] = L1[i,k] +

      C[k+1,j] + cut_right[j] - cut_left[i]),

      則必定有一C'[i,j] = C[i,k] + C[k+1,j] + cut_right[j] - cut_left[i]

      < C[i,j] = L1[i,k] + C[k+1,j] + cut_right[j] - cut_left[i]

      而我們剛剛又假設 C[i,j] 為最小成本, 矛盾 --><--

      故L1[i,k] = C[i,k], L2[k+1,j] = C[k+1,j]

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.192
※ king19880326:轉錄至看板 Prob_Solve                              04/27 08:52
推 Yshuan:我直覺的看 每刀都要切在中間會是cost最小 有錯嗎 @@~~!
→ a127a127:給樓上　1 2 3 4 5 6 100000
→ a127a127:試著把填一格的時間變成均攤的O(1)
→ a127a127:一個簡單的觀察是：P(i,j) i固定,j越大時 切的點的位置..
推 evernever:我也是覺得切中間 (1+100000)/2..最接近 6...先切6
推 littleshan:長度10，切割點 4, 5, 6
→ king19880326:可以麻煩a127a127說得清楚些嗎@@??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.43
推 bobju:就這個例子來看, 我想了解的是: 可允許的切
→ bobju:法有幾種? 除了(3,4,8),(8,4,3)以外, 可不可
→ bobju:以有其它的排列情形? 總共應有6種才對. 而最
→ bobju:小成本即是這6種切法當中成本最小的那種.
→ king19880326:恩 是考慮所有組合
推 bobju:這個問題恐怕要跑遞迴,把所有排列情形都跑遍
→ bobju:,再找出最小成本路徑.
→ bobju:方法我有,只是時間複雜度不知如何估算.
→ bobju:以n*n格為例,並非每一格都必需透過計算才能
→ bobju:得值,其中應該有些格的值可以參考自其它格的
→ bobju:值才對.
推 operationcow:如果是跑所有組合那就是n!層了
→ operationcow:指數時間@_@
推 bobju:不見得,因為做動態規劃,在traversal的過程當
→ bobju:中,可以蒐集到某些讓後面再跑到時會用得著的
→ bobju:資訊,等於可以簡化某些路徑,所以未必是n!,可
→ bobju:以再down一些時間成本.
推 yoco315:O(nnn)?這題不是很直覺?還是我想的太簡單?
推 bobju:如果是O(n^3)那還好,因為我想了想,感覺不太
→ bobju:像是O(n^3). 即使以n*n個表格的模型來思考,
→ bobju:似乎也不能證明填上每一格的平均時間是O(n).
→ bobju:因為每一刀切在某一點上的成本是隨著之前的
→ bobju:截點序列的不同而變,而非一個定值.
→ bobju:若是O(n^3), 則是多項式時間, 跟老闆交差他
→ bobju:應該要偷笑了. XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.234
※ 編輯: king19880326    來自: 140.112.4.234        (04/29 16:51)
推 bobju:先推一下! 換個角度思考果然有差別. 雖說這
→ bobju:段回文我還沒看懂. 不過我想應該就是以逆推
→ bobju:的方式來思考. 假設木頭全部都鋸好了, 然後
→ bobju:組裝成原本完整的木頭所需花費的最小成本的
→ bobju:路徑吧?