Подтвердить что ты не робот

Как понять решение динамического программирования в линейном разбиении?

Я пытаюсь понять решение динамического программирования для задачи линейного разбиения. Я читаю The Руководство по разработке алгоритмов, и проблема описана в разделе 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 */
}

Вопрос об алгоритме:

  • Какие значения хранятся в m и d?
  • Что означает "стоимость"? Это просто общее количество значений элементов внутри раздела? Или есть какой-то еще более тонкий смысл?
4b9b3361

ОТВЕТЫ

Ответ 1

Помните, что небольшая ошибка в объяснении алгоритма в книге, посмотрите в errata для текста" ( *).

О ваших вопросах:

  • Нет, элементы не нужно сортировать, только смежные (т.е. вы не можете их переупорядочить)
  • Я считаю, что самый простой способ визуализировать алгоритм состоит в том, чтобы трассировать вручную процедуру reconstruct_partition, используя самую правую таблицу на рисунке 8.8 в качестве руководства
  • В книге указано, что m [i] [j] - "минимальная возможная стоимость по всем разделам {s1, s2,..., si}" в j диапазонов, где стоимость раздела - это большая сумма элементов в одной из его частей ". Иными словами, это" наименьший максимум сумм ", если вы прощаете злоупотребление терминологией. С другой стороны, d [i] [j] сохраняет позицию индекса, которая была используемый для создания раздела для данной пары i, j, как определено ранее
  • Значение "стоимость" см. в предыдущем ответе

Edit:

Здесь моя реализация алгоритма линейного разбиения. Он основан на алгоритме Лекена, но на питоническом уровне; и он возвращает список разделов.

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)

Ответ 2

Я реализовал алгоритм Оскара Лопеса на PHP. Пожалуйста, не стесняйтесь использовать его, когда вам это нужно.

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