如何理解线性分区中的动态编程解决方案？

本文介绍了如何理解线性分区中的动态编程解决方案？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在努力理解线性分区问题的动态编程解决方案。我正在阅读《算法设计手册》 ，该问题在第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 */ }

关于算法的问题：

m 和 d ？

费用是什么意思？它仅仅是分区中元素值的总和吗？还是还有其他更微妙的含义？

推荐答案

请注意，其中存在一个小错误有关本书中算法的说明，请在勘误中查找文本（*）页面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".

关于您的问题：

不，不需要对项目进行排序，只需对其进行连续排序（即，您不能对其进行重新排列）

我相信，可视化算法的最简单方法是通过跟踪使用图8.8中最右边的表作为指南，执行 reconstruct_partition 过程

在书中指出m [i] [ j]是在{s1，s2，...，si}的所有分区上的最小可能成本到j范围内，其中分区的成本是其一部分中元素的总和。换句话说，如果您原谅滥用术语，那就是最小的总和。一方面，d [i] [j]存储索引位置，该位置用于为给定对i，j进行分区，如先前所定义

对于成本的含义，查看上一个答案

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_partition procedure, 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)