我正在努力理解线性分区问题的动态编程解决方案。我正在阅读《算法设计手册》 ,该问题在第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!
我找到了一个页面,该页面的文字与该书相似(也许来自该书的第一版):分区问题。
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?
第一个递归是:
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第二次递归是:
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第三次递归是:
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第四次递归是:
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第五次递归是:
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第六次递归是:
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第七次递归是:
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第八次递归是:
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次递归是:
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等...
这是本书中显示的代码:
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 */ }关于算法的问题:
推荐答案
请注意,其中存在一个小错误有关本书中算法的说明,请在勘误中查找文本(*)页面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".
关于您的问题:
编辑:
这是我对线性分区算法的实现。它基于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)更多推荐
如何理解线性分区中的动态编程解决方案?
发布评论