如何理解線性分區中的動態規劃解決方案？

我很努力去理解線性分區問題的動態編程解決方案。我正在閱讀The Algorithm Design Manual，問題在第8.5節中描述。我已經讀了無數次的部分，但我只是沒有得到它。我認爲這是一個糟糕的解釋（我現在閱讀的內容已經好多了），但我無法很好地理解這個問題以尋找替代解釋。更好的解釋鏈接歡迎！如何理解線性分區中的動態規劃解決方案？

我發現了一個頁面，其文字與本書相似（可能來自本書的第一版）：The Partition Problem。

第一個問題：在本書的例子中，分區按從小到大的順序排列。這只是巧合嗎？從我所能看到的元素排序對算法來說並不重要。

這是我的遞歸的理解：

讓我們用下面的序列，並將其劃分爲4：

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

第二個問題：我是這樣認爲的遞歸將開始 - 有我的理解是是否正確？

第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

第2遞歸是：

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

等等

下面的代碼，因爲它出現在書：

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？
'成本'是什麼意思？它只是分區內元素值的總和？或者還有一些更微妙的含義？

來源

2011-10-29 Benedict Cohen

順便說一句，即使你不能回答我的問題，我將不勝感激關於源材料質量的評論。我希望得到一些確認，不僅僅是我認爲解釋不好（這讓我感覺相當不舒服）。 –

我不認爲你會發現很多人在這裏能夠回答你的問題，而無需對你需要解決的問題給出一個簡潔的解釋。分區問題有很多種變化，並且粘貼由手動執行的算法的長表並不會讓事情變得更清楚。 – hugomg

請注意，本書中的算法解釋存在一個小錯誤，請在errata中查看「（*）Page 297」文本。

關於你的問題：

沒有，項不需要進行排序，只有連續的（也就是說，你不能重新排列）
我相信以可視化的最簡單的方法算法是通過手工跟蹤reconstruct_partition程序，使用圖8.8中最右邊的表格作爲指南
在書中它指出m [i] [j]是「{s1，s2的所有分區的最小可能成本，...，si}「轉換爲j個範圍，其中一個分區的成本是其中一個部分的元素的總和」換句話說，它是「最小的ma最高限額「，如果你原諒濫用術語。另一方面，d [i] [j]存儲用於對給定對i，j進行分區的索引位置，如前所定義的
對於「成本」的含義，請參閱前面的回答

編輯：

下面是我實現線性分割算法。它基於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)

來源

2011-10-30 02:26:50

謝謝，這有助於我得出結論。不幸的是，我的結論是，它出現在書中的代碼不僅令人難以置信的不清楚，而且也是錯誤的。運行代碼的輸入爲'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'。有可能我錯誤地解釋了輸出。如果是這種情況，我把它歸咎於可怕的寫作，而不是因爲我不想嘗試。鑑於這本書收到了多少好評，我對此感到驚訝。 –

代碼中的索引可能非常難以正確地獲得，但是在處理完畢後，它的工作方式與我一樣廣告 –

如果能發佈您的工作版本，我將非常感激。 –

我在PHP上實現了ÓscarLó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); 
}

來源

2014-01-21 13:09:45 WASD42

如何理解線性分區中的動態規劃解決方案？

回答

相關問題