Programación dinámica - Un tipo de matriz 0-1 equilibrada

Question

Estaba leyendo el artículo de Wikipedia de Programación dinámica Sin embargo, me cuesta entender la explicación que se da en el ejemplo de un tipo de matriz 0-1 equilibrada .

El problema se plantea así:

Consideremos el problema de asignar valores, cero o uno, a las posiciones de una matriz n × n, n par, de modo que cada fila y cada columna contengan exactamente n / 2 ceros y n / 2 unos.

No cito todo el texto porque supongo que no es necesario hacerlo. Sin embargo, no entiendo muy bien la explicación después de " El proceso de creación de subproblemas implica iterar..." en el tercer párrafo de la subsección.

¿Alguien puede explicar mejor ese procedimiento? Por supuesto, un ejemplo de esto en el trabajo sería genial.

Gracias

Answer 1

El algoritmo de programación dinámica utiliza una función recursiva memorizada que resuelve un subproblema más flexible:

La función toma un número k de filas a rellenar, y para cada columna, el número de 1s que tiene que colocar en esas k filas. Tiene que devolver el número de asignaciones posibles de 1s en el bloque de k filas tal que cada fila contenga n/2 1s, y cada columna contenga el número apropiado de 1s indicado en el argumento.

El principio es que :

• si una columna tiene que contener un número negativo de 1s, hay 0 solución.

• si k=0 (y todas las columnas tienen que estar vacías), entonces hay 1 solución.

• en caso contrario, una asignación de un bloque de k filas es una asignación de la 1ª fila + una asignación de un bloque (k-1) filas.

Así que itera sobre las posibles asignaciones de la 1ª fila. Para cada asignación candidata, se pregunta recursivamente por el número de formas de completar las (k-1) filas restantes con la información actualizada sobre el número de 1s que tiene que haber en cada columna.

Si no memoise la función, es exactamente lo que hace el algoritmo de backtracking, esencialmente es n nested extremadamente grandes bucles.

Si memoriza la función, verá que se llama para el mismo k y para las mismas restricciones en la columna un gran número de veces.

Por ejemplo, mientras realizas el algoritmo de backtracking, en algún momento eliges la asignación A1 para la fila 1 y A2 para la fila 2, y procedes a contar cada solución empezando por (A1,A2) con (n-2) bucles anidados. Luego, más adelante en la ejecución, se elige la asignación A2 para la fila 1 y A1 para la fila 2, y se procede a contar todas las soluciones a partir de (A2,A1), de nuevo con (n-2) bucles anidados.

Pero si te fijas bien en el subproblema que tienes que resolver, tiene las mismas restricciones en ambos casos. Una solución en el primer caso es la misma que una solución en el segundo caso, sólo que con las dos primeras filas intercambiadas. Así que estás contando el mismo número dos veces.

Si memorizas tu función recursiva, entonces reconocerá que estos dos subproblemas son equivalentes porque piden las mismas restricciones, y sólo calculará su resultado una vez. En todas las llamadas posteriores volverá directamente con ese mismo resultado, y evitará un recálculo muy costoso.