¿Cómo entender la solución de programación dinámica en el particionamiento lineal?
Estoy luchando para entender la solución de programación dinámica para el problema de partición lineal. Estoy leyendo el Manual de Diseño del Algoritmo y el problema se describe en la sección 8.5. He leído la sección innumerables veces, pero no lo estoy entendiendo. Creo que es una explicación pobre (lo que he leído hasta ahora ha sido mucho mejor), pero no he sido capaz de entender el problema lo suficientemente bien como para buscar una explicación alternativa. Enlaces a mejores explicaciones ¡bienvenido!
He encontrado una página con texto similar al libro (tal vez de la primera edición del libro): El Problema de la partición.
Primera pregunta: En el ejemplo del libro las particiones se ordenan de menor a mayor. ¿Es sólo una coincidencia? Por lo que puedo ver el orden de los elementos no es significativo para el algoritmo.
Este es mi entendimiento de la recursión:{[16]]}
Vamos a usar la siguiente secuencia y particionarla en 4:
{S1...Sn} = 100 150 200 250 300 350 400 450 500
k = 4
Segunda pregunta: Así es como creo que comenzará la recursión - ¿la he entendido correctamente?
La 1ra recursión es:
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
La segunda recursión es:
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
La tercera recursión es:
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
La cuarta recursión es:
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
La 5a recursión es:
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
La 6a recursión es:
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
La 7a recursión es:
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
La 8a recursión es:
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
La 9a recursión is:
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...
Aquí está el código tal como aparece en el 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 */
}
Pregunta sobre el algoritmo:
- ¿Qué valores se almacenan en
myd? - ¿Qué significa "costo"? ¿Es simplemente el total de los valores de los elementos dentro de una partición? ¿O hay algún significado adicional más sutil?
3 answers
Tenga en cuenta que hay un pequeño error en la explicación del algoritmo en el libro, busque en la errata el texto "(*) Página 297".
Acerca de sus preguntas:
- No, los elementos no necesitan ser ordenados, solo contiguos (es decir, no se pueden reorganizar)
- Creo que la forma más fácil de visualizar el algoritmo es trazando a mano el procedimiento
reconstruct_partition, utilizando la tabla de la derecha en la figura 8.8 como guía - En el libro se afirma que m [i] [j] es "el coste mínimo posible sobre todas las particiones de {s1, s2, ... , si}" en rangos j, donde el costo de una partición es la suma de elementos en una de sus partes". En otras palabras, es el "máximo más pequeño de sumas", si perdonas el abuso de terminología. Por otro lado, d[i] [j] almacena la posición del índice que se utilizó para hacer una partición para un par dado i,j como se define antes
- Para el significado de "costo", ver el anterior respuesta
Editar:
Aquí está mi implementación del algoritmo de partición lineal. Está basado en el algoritmo de Skiena, pero de una manera pitónica; y devuelve una lista de las particiones.
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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-10-31 23:45:46
He implementado el algoritmo Óscar López en PHP. Por favor, siéntase libre de usarlo cuando lo necesite.
/**
* 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);
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-21 13:09:45
La siguiente es una implementación modificada del algoritmo de partición lineal de Skienna en python que no calcula los últimos valores de la columna k excepto la respuesta misma: M[N][K] (un cálculo de celda solo depende del anterior )
Una prueba contra la entrada {1,2,3,4,5,6,7,8,9} (utilizada en el ejemplo de Skienna en el libro ) produce una matriz ligeramente diferente M (dada la modificación anterior) pero devuelve correctamente el resultado final (en este ejemplo, la partición de costo mínimo de s en k rangos es 17, y la matriz D se utiliza para imprimir la lista de posiciones divisores que conducen a este óptimo).
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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-08-25 21:15:44