Come comprendere la soluzione di programmazione dinamica nel partizionamento lineare?

Question

Non riesco a comprendere la soluzione di programmazione dinamica per il problema del partizionamento lineare. Sto leggendo il Algorithm Design Manual e il problema è descritto nella sezione 8.5. Ho letto la sezione innumerevoli volte ma non lo capisco. Penso che sia una spiegazione scarsa (quello che ho letto fino ad ora è stato molto meglio), ma non sono stato in grado di capire il problema abbastanza bene da cercare una spiegazione alternativa. Link a migliori spiegazioni benvenuto!

Ho trovato una pagina con testo simile al libro (forse dalla prima edizione del libro): The Partition Problem.

Prima domanda: nell'esempio nel libro le partizioni sono ordinate dal più piccolo al più grande. È solo una coincidenza? Da quello che posso vedere l'ordinamento degli elementi non è significativo per l'algoritmo.

Questa è la mia comprensione della ricorsione:

Consente di utilizzare la seguente sequenza e la partizione in 4:

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

Seconda domanda: Ecco come penso che la ricorsione avrà inizio - ho capito correttamente?

Il 1 ° ricorsione è:

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 

Il 2 ° ricorsione è:

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 

Il 3 ° ricorsione è:

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 

Il 4 ° ricorsione è:

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 

Il 5 ° ricorsione è:

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 

Il 6 ° ricorsione è:

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 

Il 7 ° ricorsione è:

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 

L'8 ° ricorsione è:

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 

Il 9 ricorsione è:

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 

ecc ...

Ecco il codice così come appare nel libro:

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 */ 
} 

Domanda sul dell'algoritmo:

1. Cosa i valori vengono memorizzati nello m e nello d?
2. Che cosa significa "costo"? È semplicemente il totale dei valori degli elementi all'interno di una partizione?O c'è qualche altro significato più sottile?

Answer 1

Si noti che c'è un piccolo errore nella spiegazione dell'algoritmo nel libro, guarda nello errata per il testo "(*) Pagina 297".

Circa le vostre domande:

1. No, gli elementi non hanno bisogno di essere ordinati, solo contigui (vale a dire, non si possono riorganizzare)
2. Credo che il modo più semplice per visualizzare la l'algoritmo è tracciando a mano la procedura reconstruct_partition, usando la tabella più a destra nella figura 8.8 come guida
3. Nel libro si afferma che m [i] [j] è "il costo minimo possibile su tutte le partizioni di {s1, s2 , ..., si} "in intervalli j, in cui il costo di una partizione è la somma più grande di elementi in una delle sue parti". In altre parole, è il "più piccolo ma ximum of sum ", se perdonate l'abuso della terminologia. D'altra parte, d [i] [j] memorizza la posizione dell'indice che è stata usata per creare una partizione per una data coppia i, j come definito prima
4. Per il significato di "costo", vedere la risposta precedente

Edit:

Ecco la mia implementazione dell'algoritmo di partizionamento lineare. È basato sull'algoritmo di Skiena, ma in modo pititico; e restituisce una lista delle partizioni.

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) 

Answer 2

Ho implementato l'algoritmo Óscar López su PHP. Sentiti libero di usarlo quando ne hai bisogno.

/** 
* 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); 
}