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

Question

我正在努力理解线性分区问题的动态编程解决方案.我正在阅读算法设计手册,问题在8.5节中描述.我已经无数次阅读了这个部分,但我只是没有得到它.我认为这是一个糟糕的解释(我现在读到的内容已经好多了),但是我还没有能够很好地理解这个问题以寻找替代解释.欢迎链接到更好的解释!

我找到了一个页面,其中包含类似于本书的文本(可能来自本书的第一版):分区问题.

第一个问题:在本书的示例中,分区从最小到最大排序.这只是巧合吗？从我可以看出,元素的排序对算法并不重要.

这是我对递归的理解:

让我们使用以下序列并将其分为4:

{S1...Sn} =  100   150   200   250   300   350   400   450   500
k = 4

第二个问题:这就是我认为递归将如何开始 - 我理解正确吗？

第一次递归是:

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

第6次递归是:

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

第7次递归是:

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

第8次递归是:

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

等等...

这是本书中出现的代码:

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. "成本"是什么意思？它只是分区中元素值的总和吗？还是有一些更微妙的含义？

Answer 1

请注意,书中对算法的解释存在一个小错误,请查看"(*)Page 297"文本的勘误表.

关于你的问题:

1. 不,这些项目不需要排序,只是连续(也就是说,你不能重新排列它们)
2. 我相信可视化算法的最简单方法是手动跟踪reconstruct_partition程序,使用图8.8中最右边的表格作为指导
3. 在书中,它指出m [i] [j]是"{s1,s2,...,si}的所有分区的最小可能成本"到j范围,其中分区的成本是大的总和其中一个部分中的元素".换句话说,它是"最小的和",如果你原谅滥用术语.另一方面,d [i] [j]存储用于制作的索引位置如前定义的给定对i,j的分区
4. 有关"费用"的含义,请参阅上一个答案

编辑:

这是我对线性分区算法的实现.它基于Skiena的算法,但是以pythonic的方式; 它返回一个分区列表.

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)