Как понять решение динамического программирования в линейном разбиении?
Я изо всех сил пытаюсь понять динамическое программирование решения проблемы линейного разбиения. Я читаю Руководство по разработке алгоритма, и проблема описана в разделе 8.5. Я прочитал раздел бесчисленное количество раз, но я просто не понимаю. Я думаю, что это плохое объяснение (то, что я прочитал до сих пор, было намного лучше), но я не смог понять проблему достаточно хорошо, чтобы искать альтернативное объяснение. Ссылки на лучшие объяснения приветствуются!
Я нашел страницу с текстом, похожим на книгу (возможно, из первого издания книги): Проблема с разделами.
Первый вопрос: в примере, приведенном в книге, разделы упорядочены от наименьшего к наибольшему. Это просто совпадение? Из того, что я вижу, порядок элементов не имеет значения для алгоритма.
Это мое понимание рекурсии:
Давайте использовать следующую последовательность и разбить ее на 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
Вторая рекурсия это:
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
3-я рекурсия это:
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
Шестая рекурсия это:
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
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? - Что означает "стоимость"? Это просто сумма значений элементов в разделе? Или есть какой-то дополнительный, более тонкий смысл?
3 ответа
Имейте в виду, что в объяснении алгоритма в книге есть небольшая ошибка, поищите в опечатках текст "(*) Страница 297".
О ваших вопросах:
- Нет, элементы не нужно сортировать, только смежные (то есть вы не можете их переставлять)
- Я считаю, что самый простой способ визуализировать алгоритм - это отследить вручную
reconstruct_partitionПроцедура, используя крайнюю правую таблицу на рисунке 8.8 в качестве руководства - В книге говорится, что m[i][j] - это "минимально возможная стоимость по всем разбиениям {s1, s2, ..., si}" на j диапазонов, где стоимость раздела - это большая сумма элементы в одной из его частей ". Другими словами, это" наименьший максимум сумм ", если вы простите за злоупотребление терминологией. С другой стороны, d[i][j] хранит позицию индекса, которая использовалась для раздел для заданной пары i,j, как определено ранее
- Значение слова "стоимость" см. В предыдущем ответе.
Редактировать:
Вот моя реализация алгоритма линейного разбиения. Это основано на алгоритме Скиены, но питонским способом; и возвращает список разделов.
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)
Я реализовал алгоритм Оскара Лопеса на 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);
}
Ниже приведена модифицированная реализация алгоритма линейного разделения Skienna в python, который не вычисляет последние значения k столбца, кроме самого ответа: M[N][K] (вычисление ячейки зависит только от предыдущего)
Проверка на входные данные {1,2,3,4,5,6,7,8,9} (используется в примере Скиенны в книге) дает несколько иную матрицу 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)