programming problems for examples dummies bellman c matrix dynamic-programming

problems - dynamic programming pdf



Programación dinámica-Bloque cuadrado más grande (7)

Aquí hay un boceto de la solución:

Para cada una de las celdas mantendremos un contador de cuán grande se puede hacer un cuadrado usando esa celda como arriba a la izquierda. Claramente, todas las celdas con 0 tendrán 0 como recuento.

Comience a iterar desde la celda inferior derecha y vaya a la esquina inferior izquierda, luego vaya a una fila y repita.

En cada escaneo haz esto:

  1. Si la celda tiene 0 asignar count=0
  2. Si la celda tiene 1 y es una celda de borde (solo borde inferior o derecho), asigne count=1
  3. Para todas las demás celdas, verifique el recuento de la celda a su derecha, derecha, abajo y abajo. Tome el mínimo de ellos y agregue 1 y asigne eso al recuento. Mantenga una variable global max_count para realizar un seguimiento del recuento máximo hasta el momento.

Al final de atravesar la matriz, max_count tendrá el valor deseado.

La complejidad no es más que el costo de atravesar la matriz.

Así es como se verá la matriz después de la travesía. Los valores entre paréntesis son los recuentos, es decir, el cuadrado más grande que se puede hacer usando la celda como arriba a la izquierda.

1(1) 0(0) 1(1) 0(0) 1(1) 0(0) 1(1) 0(0) 1(4) 1(3) 1(2) 1(1) 0(0) 1(1) 1(3) 1(3) 1(2) 1(1) 0(0) 0(0) 1(2) 1(2) 1(2) 1(1) 1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Implementación en Python

def max_size(mat, ZERO=0): """Find the largest square of ZERO''s in the matrix `mat`.""" nrows, ncols = len(mat), (len(mat[0]) if mat else 0) if not (nrows and ncols): return 0 # empty matrix or rows counts = [[0]*ncols for _ in xrange(nrows)] for i in reversed(xrange(nrows)): # for each row assert len(mat[i]) == ncols # matrix must be rectangular for j in reversed(xrange(ncols)): # for each element in the row if mat[i][j] != ZERO: counts[i][j] = (1 + min( counts[i][j+1], # east counts[i+1][j], # south counts[i+1][j+1] # south-east )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges return max(c for rows in counts for c in rows)

Necesito encontrar el cuadrado más grande de 1 en un archivo gigante lleno de 1 y 0. Sé que tengo que usar programación dinámica. Lo estoy almacenando en una matriz 2D. Cualquier ayuda con el algoritmo para encontrar el cuadrado más grande sería genial, ¡gracias!

entrada de ejemplo:

1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1

responder:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Mi código hasta ahora:

int Square (Sq[int x][int y]) { if (Sq[x][y]) == 0) { return 0; } else { return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) ); } }

(asumiendo valores ya ingresados ​​en la matriz)

int main() { int Sq[5][6]; //5,6 = bottom right conner int X = Square(Sq[5][6]); }

¿Cómo sigo desde allí?

Deje N ser la cantidad de celdas en la matriz 2D. Existe un algoritmo muy eficiente para listar todos los rectángulos vacíos máximos. El cuadrado vacío más grande está dentro de uno de estos rectángulos vacíos, y fundarlo es trivial una vez que se ha calculado la lista de los rectángulos vacíos máximos. Puede encontrar un documento que presente un algoritmo O (N) para crear dicha lista en www.ulg.ac.be/telecom/rectangles , así como en el código fuente (no optimizado). Tenga en cuenta que existe una prueba (ver el artículo) de que el número de rectángulos vacíos más grandes está limitado por N. Por lo tanto, seleccionar el cuadrado vacío más grande se puede hacer en O (N) y el método general también es O (N). En la práctica, este método es muy rápido. La implementación es muy fácil de hacer, ya que el código completo no debe ser más de 40 líneas de C (el algoritmo para enumerar todos los rectángulos vacíos máximos toma alrededor de 30 líneas de C).

El primer algoritmo que me viene a la mente es:

  1. ''&&'' columna / fila 1 con columna / fila 2 si, es decir, hacer una operación ''&&'' entre cada entrada y su entrada correspondiente en la otra columna / fila.
  2. Verifique la columna resultante, si hay alguna longitud 2 1 eso significa que golpeamos un cuadrado de 2x2.
  3. Y la siguiente columna con el resultado de los dos primeros. Si hay una longitud de 3 1, hemos alcanzado un cuadrado de 3x3.
  4. Repita hasta que todas las columnas hayan sido utilizadas.
  5. Repite del 1 al 4 comenzando en la columna 2.

No le mostraré la implementación ya que es bastante sencillo y su problema parece una tarea. Además, es probable que haya maneras mucho más eficientes de hacerlo, ya que será lento si la entrada es muy grande.

La clave aquí es que puede realizar un seguimiento de la raíz del área en lugar del área real, utilizando programación dinámica.

El algoritmo es el siguiente:

Almacene una matriz 2D de enteros llamada max-square, donde un elemento en el índice i, j representa el tamaño del cuadrado en el que está i, j es la esquina inferior derecha. (si max [i, j] = 2, significa que el índice i, j es la esquina inferior derecha de un cuadrado de tamaño 2 ^ 2 = 4)

Para cada índice i, j:

si en i, j el elemento es 0, entonces establezca max-square i, j en 0.

más:

Encuentre el mínimo de max-square [i - 1, j] y max-square [i, j - 1] y max-square [i - 1] [j -1]. establezca max-square [i, j] en 1 + el mínimo de 3. Inductivamente, terminará llenando la matriz de máximo cuadrado. Encuentre / o haga un seguimiento del valor máximo en el proceso, devuelva ese valor ^ 2.

Eche un vistazo a estas soluciones que la gente ha propuesto: https://leetcode.com/discuss/questions/oj/maximal-square?sort=votes

Let input matrix es M : nxm

T[i][j] es una matriz DP que contiene el lado cuadrado más grande con cuadrados en ángulo recto (i,j) .

Regla general para llenar la tabla:

if (M[i][j] == 1) { int v = min(T[i][j-1], T[i-1][j]); v = min(v, T[i-1][j-1]); T[i][j] = v + 1; } else T[i][j] = 0;

El tamaño del cuadrado resultante es el valor máximo en T

Rellenar T[i][0] y T[0][j] es trivial.

No estoy seguro de si este algoritmo puede usarse para su gran archivo , pero no es necesario que almacene toda la matriz T sino solo las líneas actuales y anteriores.

Las siguientes notas pueden ayudar a entender una idea general:

  • todos los cuadrados con ángulos inferiores derechos (i-1, j), (i, j-1), (i-1, j-1) con tamaño s están dentro del cuadrado con ángulo inferior derecho (i, j) con tamaño s +1.
  • si hay un cuadrado de tamaño s + 1 con la esquina inferior derecha en (i, j), entonces el tamaño del cuadrado máximo con los ángulos inferiores derechos (i-1, j), (i, j-1), (i-1, j-1) es al menos s.
  • Opuesto también es verdad. Si el tamaño de al menos un cuadrado con ángulos rectos inferiores en (i-1, j), (i, j-1), (i-1, j-1) es menor que s, entonces el tamaño del cuadrado con la esquina inferior derecha at (i, j) no puede ser mayor que s + 1.

OK, la forma más ineficiente pero simple sería:

  1. seleccionar el primer artículo. compruebe si 1, si es así, tiene un cuadrado de 1x1.

  2. marque uno abajo y uno a la derecha, si es 1, luego verifique la fila 2 col 2, si es 1, 2x2 cuadrados.

  3. verifique la fila 3 col 1, col 2 y col 3, más la fila 1 col 3, fila 2 col 3, si 1, 3x3.

  4. Así que, básicamente, sigues expandiendo la fila y el col juntos y verificas todas las celdas dentro de sus límites. En cuanto alcanzas un 0, está roto, por lo que te mueves a lo largo de 1 punto en una fila y comienzas de nuevo.

  5. Al final de la fila, pasar a la siguiente fila.

  6. hasta el final.

Probablemente puedas ver cómo encajan esos en bucles while, etc., y cómo && s se puede usar para verificar los 0, y cuando lo mires, quizás también notes cómo se puede acelerar. Pero como la otra respuesta se acaba de mencionar, suena un poco como la tarea, así que le dejaremos el código real.

¡Buena suerte!

LSBRA(X,Y) significa "Cuadrado más grande con abajo a la derecha en X, Y"

Pseudocódigo:

LSBRA(X,Y): if (x,y) == 0: 0 else: 1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

(Para celdas de borde, puede omitir la parte MIN y solo devolver 1 si (x, y) no es 0.)

Trabaja en diagonal a través de la cuadrícula en "ondas", como la siguiente:

0 1 2 3 4 +---------- 0 | 1 2 3 4 5 1 | 2 3 4 5 6 2 | 3 4 5 6 7 3 | 4 5 6 7 8

o alternativamente, trabaje de izquierda a derecha, de arriba hacia abajo, siempre y cuando complete las celdas de borde.

0 1 2 3 4 +---------- 0 | 1 2 3 4 5 1 | 6 7 8 9 . 2 | . . . . . 3 | . . . . .

De esta forma, nunca se encontrará con un cómputo en el que no haya calculado previamente los datos necesarios, por lo que todas las "llamadas" de LSBRA() son solo búsquedas de tabla de sus resultados de cálculo previos (de ahí el aspecto de programación dinámica).

Por qué funciona

Para tener un cuadrado con una esquina inferior derecha en X, Y, debe contener los cuadrados superpuestos de una dimensión menos que toque cada una de las otras 3 esquinas. En otras palabras, tener

XXXX XXXX XXXX XXXX

también debes tener ...

XXX. .XXX .... .... XXX. .XXX XXX. .... XXX. .XXX XXX. .... .... .... XXX. ...X

Siempre y cuando tengas esos 3 (cada uno de los controles LSBRA) cuadrados N-size más el cuadrado actual también "ocupado", tendrás un cuadrado (N + 1) de tamaño.