Jak rozumieć rozwiązanie do programowania dynamicznego w liniowym partycjonowaniu?

Question

Staram się zrozumieć rozwiązanie programowania dynamicznego na problem partycjonowania liniowego. Czytam The Algorithm Design Manual, a problem jest opisany w rozdziale 8.5. Czytałem tę sekcję niezliczoną ilość razy, ale po prostu jej nie dostaję. Myślę, że to kiepskie wytłumaczenie (to, co przeczytałem do tej pory, było znacznie lepsze), ale nie byłem w stanie zrozumieć problemu wystarczająco dobrze, aby szukać alternatywnego wyjaśnienia. Linki do lepszych wyjaśnień zapraszamy!

Znalazłem stronę z tekstem podobnym do książki (może z pierwszego wydania książki): The Partition Problem.

Pierwsze pytanie: W przykładzie w książce partycje są sortowane od najmniejszej do największej. Czy to tylko zbieg okoliczności? Z tego, co widzę, uporządkowanie elementów nie ma znaczenia dla algorytmu.

To jest moje rozumienie rekursji:

Pozwala wykorzystać następującą sekwencję i podzielić ją na 4:

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

Drugie pytanie: Oto, jak myślę, że rekurencja zacznie - nie zrozumiałem prawidłowo?

The 1st rekurencji jest:

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 

The 2nd rekurencji jest:

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 

The 3rd rekurencji jest:

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 

4th rekurencji jest:

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 

5th rekurencji jest:

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 

na 6. rekurencji jest:

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. rekurencji jest:

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 

8th rekurencji jest:

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 

The 9th rekurencji jest:

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 

etc ...

Oto kod zamieszczony w książce:

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

pytanie o algorytm:

1. Co wartości są przechowywane w m i ?
2. Co oznacza "koszt"? Czy jest to po prostu suma wartości elementów w partycji?Czy jest jakieś dodatkowe, bardziej subtelne znaczenie?

Answer 1

Należy pamiętać, że jest tam mały błąd w objaśnieniu algorytmu w książce, spojrzeć w errata dla tekstu „(*) Page 297”.

O pytania:

1. Nie, elementy nie muszą być klasyfikowane, tylko przyległe (czyli nie można ich zmienić)
2. wierzę, najprostszy sposób na wizualizację algorytm polega na ręcznym śledzeniu procedury reconstruct_partition, przy użyciu prawej skrajnej tabeli na rysunku 8.8 jako wskazówki.
3. W książce stwierdza się, że m [i] [j] to "minimalny możliwy koszt na wszystkich partycjach {s1, s2 , ..., si} "w zakresach j, gdzie koszt partycji jest największą sumą elementów w jednej z jej części." Innymi słowy, jest to "najmniejsza ximum kwot ", jeśli wybaczycie nadużycie terminologii. Z drugiej strony, d [i] [j] przechowuje pozycję indeksu, która została użyta do utworzenia partycji dla danej pary, j, jak zdefiniowano przed
4. Znaczenie "kosztu", patrz poprzednia odpowiedź

Edit:

Oto moja implementacja algorytmu dzielącego liniowej. Jest oparty na algorytmie Skieny, ale w sposób pytonowy; i zwraca listę partycji.

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

Zaimplementowałem algorytm Óscar López na PHP. Zachęcamy do korzystania z niego w dowolnym momencie.

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