如何理解线性分割中的动态规划解决方案？

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

第5次递归是：

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

第七次递归是：

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

- Benedict Cohen

---

顺便说一句，即使您无法回答我的问题，我也会感谢对源材料质量的评论。我希望得到一些确认，证明不仅仅是我发现解释很差（这让我感到相当愚蠢）。 - Benedict Cohen

我认为在这里你不会找到很多人能够回答你的问题，除非你简洁地解释一下你需要解决的问题。划分问题有许多变体，手动粘贴算法执行的长表并不能使事情更加清晰。 - hugomg

Answer 1

请注意，该书中算法的解释中存在一个小错误，请查看勘误表中的文本“（*）第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)

- Óscar López

---

谢谢，这帮助我得出了结论。<抱怨>不幸的是，我的结论是，书中的代码不仅极其不清晰，而且完全错误。使用输入“1,1,1,1,1,1,1,1,1”运行代码的结果是“1,1,1,1,1|1|1,1”，根据文本应该是“1,1,1|1,1,1|1,1,1”。有可能我误解了输出结果。如果是这种情况，我会把责任归咎于糟糕的写作，而不是我没有尝试。考虑到这本书收到了很多好评，我对此感到惊讶。</抱怨> - Benedict Cohen

这个算法允许存在空行。这是算法允许的吗？ - Jonathan Ong

@ÓscarLópez 这个问题有维基百科页面吗？我想了解其他解决方案和复杂度分析。 - nischayn22

我不知道有没有其他的描述。最好的描述在《算法设计手册》中，你可以在问题中找到该章节的链接。 - Óscar López

代码在某些情况下会计算出“错误”的解决方案，如果存在单个的大元素。例如：seq=[20, 20, 20, 110, 15, 7, 10, 20, 20, 10, 20, 10, 20, 20, 10, 15, 20, 15, 7]，k=6。result=[[20], [20, 20], [110], [15], [7, 10, 20, 20, 10, 20, 10], [20, 20, 10, 15, 20, 15, 7]]。在单个的110元素（正确）之后，出现了一个单个的15（错误）。 - Ortwin Gentz

Answer 2

我已经在PHP上实现了Óscar López算法，请随时使用它。

 /**
 * Example: linear_partition([9,2,6,3,8,5,8,1,7,3,4], 3) => [[9,2,6,3],[8,5,8],[1,7,3,4]]
 * @param array $seq
 * @param int $k
 * @return array
 */
protected function linear_partition(array $seq, $k)
{
    if ($k <= 0) {
        return array();
    }

    $n = count($seq) - 1;
    if ($k > $n) {
        return array_map(function ($x) {
            return array($x);
        }, $seq);
    }

    list($table, $solution) = $this->linear_partition_table($seq, $k);
    $k = $k - 2;
    $ans = array();

    while ($k >= 0) {
        $ans = array_merge(array(array_slice($seq, $solution[$n - 1][$k] + 1, $n - $solution[$n - 1][$k])), $ans);
        $n = $solution[$n - 1][$k];
        $k = $k - 1;
    }

    return array_merge(array(array_slice($seq, 0, $n + 1)), $ans);
}

protected function linear_partition_table($seq, $k)
{
    $n = count($seq);

    $table = array_fill(0, $n, array_fill(0, $k, 0));
    $solution = array_fill(0, $n - 1, array_fill(0, $k - 1, 0));

    for ($i = 0; $i < $n; $i++) {
        $table[$i][0] = $seq[$i] + ($i ? $table[$i - 1][0] : 0);
    }

    for ($j = 0; $j < $k; $j++) {
        $table[0][$j] = $seq[0];
    }

    for ($i = 1; $i < $n; $i++) {
        for ($j = 1; $j < $k; $j++) {
            $current_min = null;
            $minx = PHP_INT_MAX;

            for ($x = 0; $x < $i; $x++) {
                $cost = max($table[$x][$j - 1], $table[$i][0] - $table[$x][0]);
                if ($current_min === null || $cost < $current_min) {
                    $current_min = $cost;
                    $minx = $x;
                }
            }

            $table[$i][$j] = $current_min;
            $solution[$i - 1][$j - 1] = $minx;
        }
    }

    return array($table, $solution);
}

- WASD42

Answer 3

以下是Skienna的线性分割算法的修改实现，使用Python语言，除了答案本身的M[N][K]值外，不计算最后的k列值：（一个单元格的计算仅依赖于先前的计算）。

对输入{1,2,3,4,5,6,7,8,9}（在Skienna的书中使用）进行测试，使用上述修改会得到略有不同的矩阵M，但正确返回最终结果（在此示例中，将s分成k个范围的最小成本分区为17，矩阵D用于打印导致此最优解的分隔符位置列表）。

import math   
    
def partition(s, k):
    # compute prefix sums

    n = len(s)
    p = [0 for _ in range(n)]
    m = [[0 for _ in range(k)] for _ in range(n)]
    d = [[0 for _ in range(k)] for _ in range(n)]

    for i in range(n):
        p[i] = p[i-1] + s[i]

    # initialize boundary conditions
    for i in range(n):
        m[i][0] = p[i]

    for i in range(k):
        m[0][i] = s[0]

    # Evaluate main recurrence
    for i in range(1, n):
        """
          omit calculating the last M's column cells 
          except for the sought minimum cost M[N][K]
        """
        if i != n - 1:
            jlen = k - 1
        else:
            jlen = k

        for j in range(1, jlen):

            """
            - computes the minimum-cost partitioning  of the set {S1,S2,.., Si} into j partitions .
            - this part should be investigated more closely .
            
            """
            #
            m[i][j] = math.inf

            # This loop needs to be traced to understand it better
            for x in range(i):
                sup = max(m[x][j-1], p[i] - p[x])
                if m[i][j] > sup:
                    m[i][j] = sup
                    # record which divider position was required to achieve the value s
                    d[i][j] = x+1

    return s, d, n, k


def reconstruct_partition(S, D, N, K):
    if K == 0:
        for i in range(N):
            print(S[i], end="_")
        print(" | ", end="")
    else:
        reconstruct_partition(S, D, D[N-1][K-1], K-1)
        for i in range(D[N-1][K-1], N):
            print(S[i], end="_")
        print(" | ", end="")

# MAIN PROGRAM

S, D, N, K = partition([1, 2, 3, 4, 5, 6, 7, 8, 9], 3)

reconstruct_partition(S, D, N, K)

- mabbessi