作者king19880326 (OK的啦～我都可以接受)
看板Programming
标题Re: [问题] 请问有关锯木问题写成程式比较快的方法
时间Wed Apr 29 16:48:03 2009
※ 引述《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
1F：推 Yshuan:我直觉的看 每刀都要切在中间会是cost最小 有错吗 @@~~! 04/27 09:30
2F：→ a127a127:给楼上 1 2 3 4 5 6 100000 04/27 09:54
3F：→ a127a127:试着把填一格的时间变成均摊的O(1) 04/27 09:55
4F：→ a127a127:一个简单的观察是：P(i,j) i固定,j越大时 切的点的位置.. 04/27 10:01
5F：推 evernever:我也是觉得切中间 (1+100000)/2..最接近 6...先切6 04/27 12:05
6F：推 littleshan:长度10，切割点 4, 5, 6 04/27 13:30
7F：→ king19880326:可以麻烦a127a127说得清楚些吗@@?? 04/27 13:48
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.243.43
8F：推 bobju:就这个例子来看, 我想了解的是: 可允许的切 59.104.186.105 04/27 14:57
9F：→ bobju:法有几种? 除了(3,4,8),(8,4,3)以外, 可不可 59.104.186.105 04/27 14:58
10F：→ bobju:以有其它的排列情形? 总共应有6种才对. 而最 59.104.186.105 04/27 14:58
11F：→ bobju:小成本即是这6种切法当中成本最小的那种. 59.104.186.105 04/27 14:59
12F：→ king19880326:恩 是考虑所有组合 140.112.243.43 04/27 17:37
13F：推 bobju:这个问题恐怕要跑递回,把所有排列情形都跑遍 59.104.186.105 04/27 18:56
14F：→ bobju:,再找出最小成本路径. 59.104.186.105 04/27 18:57
15F：→ bobju:方法我有,只是时间复杂度不知如何估算. 59.104.186.105 04/27 18:57
16F：→ bobju:以n*n格为例,并非每一格都必需透过计算才能 59.104.186.105 04/27 19:04
17F：→ bobju:得值,其中应该有些格的值可以参考自其它格的 59.104.186.105 04/27 19:04
18F：→ bobju:值才对. 59.104.186.105 04/27 19:05
19F：推 operationcow:如果是跑所有组合那就是n!层了140.112.243.192 04/27 20:53
20F：→ operationcow:指数时间@_@140.112.243.192 04/27 20:53
21F：推 bobju:不见得,因为做动态规划,在traversal的过程当 59.104.186.105 04/28 01:33
22F：→ bobju:中,可以蒐集到某些让後面再跑到时会用得着的 59.104.186.105 04/28 01:33
23F：→ bobju:资讯,等於可以简化某些路径,所以未必是n!,可 59.104.186.105 04/28 01:34
24F：→ bobju:以再down一些时间成本. 59.104.186.105 04/28 01:34
25F：推 yoco315:O(nnn)?这题不是很直觉?还是我想的太简单?118.160.108.151 04/28 13:16
26F：推 bobju:如果是O(n^3)那还好,因为我想了想,感觉不太 59.104.191.26 04/28 15:27
27F：→ bobju:像是O(n^3). 即使以n*n个表格的模型来思考, 59.104.191.26 04/28 15:27
28F：→ bobju:似乎也不能证明填上每一格的平均时间是O(n). 59.104.191.26 04/28 15:28
29F：→ bobju:因为每一刀切在某一点上的成本是随着之前的 59.104.191.26 04/28 15:33
30F：→ bobju:截点序列的不同而变,而非一个定值. 59.104.191.26 04/28 15:33
31F：→ bobju:若是O(n^3), 则是多项式时间, 跟老板交差他 59.104.191.26 04/28 15:40
32F：→ bobju:应该要偷笑了. XD 59.104.191.26 04/28 15:40
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.4.234
※ 编辑: king19880326 来自: 140.112.4.234 (04/29 16:51)
33F：推 bobju:先推一下! 换个角度思考果然有差别. 虽说这 59.104.191.26 04/29 19:16
34F：→ bobju:段回文我还没看懂. 不过我想应该就是以逆推 59.104.191.26 04/29 19:17
35F：→ bobju:的方式来思考. 假设木头全部都锯好了, 然後 59.104.191.26 04/29 19:17
36F：→ bobju:组装成原本完整的木头所需花费的最小成本的 59.104.191.26 04/29 19:18
37F：→ bobju:路径吧? 59.104.191.26 04/29 19:18