动态规划：线性分区。请帮神交 [英] Dynamic programming: Linear Partitioning. Please help grok
问题描述
我努力理解动态规划的解决方案，以线性划分问题。我读的算法设计手册的问题在第8.5节所述。我读过的部分无数次，但我只是没有得到它。我认为这是一个贫穷的解释（在我读过到现在已经好多了），但我没能理解这个问题不够好，找了另一种解释。链接到更好的解释欢迎！
I'm struggling to understand the dynamic programming solution to linear partitioning problem. I am reading the The Algorithm Design Manual and the problem is described in section 8.5. I've read the section countless times but I'm just not getting it. I think it's a poor explanation (the what I've read up to now has been much better), but I've not been able to understand the problem well enough to look for an alternative explanation. Links to better explanations welcome!
更新：我发现有类似文字的书（也许从本书的第一版）页：的The划分问题
Update: I've found a page with text similar to the book (maybe from the first edition of the book): The Partition Problem
第一个问题：在这个例子中，在书的分区下令从最小到最大。这只是巧合吗？从我所看到的元素的顺序并不显著的算法。
First question: In the example in the book the partitions are ordered from smallest to largest. Is this just coincidence? From what I can see the ordering of the elements is not significant to the algorithm.
这是我对递归的理解：
让我们用下面的顺序和分割成4：
Lets use the following sequence and partition it into 4:
{S1...Sn} = 100 150 200 250 300 350 400 450 500
k = 4
第二个问题：这是我怎么想的递归将开始 - 有我理解正确的话
Second question: Here's how I think the recursion will begin - have I understood it correctly?
第1递归是：
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 200 250 300 | 350 | 400 | 450 | 500 //done
第二递归是：
The 2nd recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 200 250 | 300 350 | 400 | 450 | 500 //done
第三递归是：
The 3rd recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 200 | 250 300 350 | 400 | 450 | 500 //done
第四递归是：
The 4th recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 150 | 200 250 300 350 | 400 | 450 | 500 //done
第五递归是：
The 5th recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 350 | 400 | 450 | 500 //1 partition to go
100 | 150 200 250 300 350 | 400 | 450 | 500 //done
第6递归是：
The 6th recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 150 200 250 | 300 | 350 400 | 450 | 500 //done
第七递归是：
The 7th recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 150 200 | 250 300 | 350 400 | 450 | 500 //done
第八递归是：
The 8th recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 150 | 200 250 300 | 350 400 | 450 | 500 //done
第9递归是：
The 9th recursion is:
100 150 200 250 300 350 400 450 | 500 //3 partition to go
100 150 200 250 300 350 400 | 450 | 500 //2 partition to go
100 150 200 250 300 | 350 400 | 450 | 500 //1 partition to go
100 | 150 200 250 300 | 350 400 | 450 | 500 //done
等等...
etc...
这里的code，因为它出现在书：
Here's the code as it appears in the book:
partition(int s[], int n, int k)
{
int m[MAXN+1][MAXK+1]; /* DP table for values */
int d[MAXN+1][MAXK+1]; /* DP table for dividers */
int p[MAXN+1]; /* prefix sums array */
int cost; /* test split cost */
int i,j,x; /* counters */
p[0] = 0; /* construct prefix sums */
for (i=1; i<=n; i++) p[i]=p[i-1]+s[i];
for (i=1; i<=n; i++) m[i][3] = p[i]; /* initialize boundaries */
for (j=1; j<=k; j++) m[1][j] = s[1];
for (i=2; i<=n; i++) /* evaluate main recurrence */
for (j=2; j<=k; j++) {
m[i][j] = MAXINT;
for (x=1; x<=(i-1); x++) {
cost = max(m[x][j-1], p[i]-p[x]);
if (m[i][j] > cost) {
m[i][j] = cost;
d[i][j] = x;
}
}
}
reconstruct_partition(s,d,n,k); /* print book partition */
}
有关算法问题：
1.什么样的价值观被存储在 M 和 D ？
2.什么是成本是什么意思？它是对一个分区中的元素值，简直是总？或者是有一些其他更微妙的含义？
Question about the algorithm:
1. What values are being stored in the m and d?
2. What does 'cost' mean? Is it simply the total of the elements values within a partition? Or is there some additional more subtle meaning?
我可能会在很短的，而更多的问题。
I'll probably have more questions in a short while.
推荐答案
请注意，有一个小错误，在算法书中的解释，看在的errata 文本（*），页297。
Be aware that there's a small mistake in the explanation of the algorithm in the book, look in the errata for the text "(*) Page 297".
关于你的问题：
- 否，项目不需要进行排序，只有连续的（也就是说，你不能重新排列它们）
- 我相信，以可视化的算法，最简单的方法是用手工跟踪
reconstruct_partition操作，使用最右边的表图8.8为指导 - 在书它指出米[Ⅰ] [j]的是最小的可能成本比的所有分区成为{S1，S2，...，SI}成J个范围，其中一个分区的成本是拉尔在其部分之一的元素的总和。换句话说，它是最小的最大的总和，如果你赦免术语的滥用。另一方面，D [I] [j]的存储这是索引位置用于制造为给定的一对I，J分区如前定义
- 对于成本的含义，见previous答案
- No, the items don't need to be sorted, only contiguous (that is, you can't rearrange them)
- I believe the easiest way to visualize the algorithm is by tracing by hand the
reconstruct_partitionprocedure, using the rightmost table in figure 8.8 as a guide - In the book it states that m[i][j] is "the minimum possible cost over all partitionings of {s1, s2, ... , si}" into j ranges, where the cost of a partition is the larges sum of elements in one of its parts". In other words, it's the "smallest maximum of sums", if you pardon the abuse of terminology. On the other hand, d[i][j] stores the index position which was used to make a partition for a given pair i,j as defined before
- For the meaning of "cost", see the previous answer
编辑：
下面是我实现线性分割算法。它是基于Skiena的算法，但在Python的方式;和它返回分区列表
Here's my implementation of the linear partitioning algorithm. It's based on Skiena's algorithm, but in a pythonic way; and it returns a list of the partitions.
from operator import itemgetter
def linear_partition(seq, k):
if k <= 0:
return []
n = len(seq) - 1
if k > n:
return map(lambda x: [x], seq)
table, solution = linear_partition_table(seq, k)
k, ans = k-2, []
while k >= 0:
ans = [[seq[i] for i in xrange(solution[n-1][k]+1, n+1)]] + ans
n, k = solution[n-1][k], k-1
return [[seq[i] for i in xrange(0, n+1)]] + ans
def linear_partition_table(seq, k):
n = len(seq)
table = [[0] * k for x in xrange(n)]
solution = [[0] * (k-1) for x in xrange(n-1)]
for i in xrange(n):
table[i][0] = seq[i] + (table[i-1][0] if i else 0)
for j in xrange(k):
table[0][j] = seq[0]
for i in xrange(1, n):
for j in xrange(1, k):
table[i][j], solution[i-1][j-1] = min(
((max(table[x][j-1], table[i][0]-table[x][0]), x) for x in xrange(i)),
key=itemgetter(0))
return (table, solution)
这篇关于动态规划：线性分区。请帮神交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
