Module: Patrones en Programación Dinámica - 2

Descargo de responsabilidad: el método que se describe a continuación no es universal, pero a menudo puede resolver un problema o ayudarlo a encontrar la solución correcta.

Si necesita verificar la existencia de una permutación en un problema, o encontrar el número de permutaciones que coinciden, o algo similar, entonces debería considerar usar la programación dinámica de subconjuntos.

El parámetro principal será una máscara de bits, que mostrará qué elementos ya se han incluido en la permutación y cuáles no. También suele ser necesario un segundo parámetro que indique qué elemento se incluyó en último lugar.

A menudo, las permutaciones se pueden ver en el contexto de las rutas en los gráficos. En consecuencia, consideremos un ejemplo clásico: el problema del camino hamiltoniano.
Un camino hamiltoniano es un camino simple que pasa por cada vértice del gráfico exactamente una vez. Se puede representar simplemente como una permutación de longitud n, donde n es el número de vértices. El orden dentro de esta permutación indicará el orden en que se recorren los vértices de este camino.

Para verificar la presencia de un camino hamiltoniano en el gráfico, comencemos con la dinámica dp[máscara][último]: ¿hay un camino simple que pase por alto los vértices marcados con unos en la máscara de bits y termine en el último vértice?
Los valores iniciales serán dp[2ⁱ][i] = verdadero, el resto falso, lo que significa que siempre hay un camino vacío que comienza en cualquiera de los vértices.
Teniendo el valor true en dp[mask][last] haremos transiciones hacia adelante, en el sentido de "extender el camino". Es decir, buscaremos el número de vértices que están marcados con cero en la máscara (aún no los hemos visitado en el camino) y al mismo tiempo tal que haya una arista desde el último hasta este vértice (el camino debe extenderse por un borde existente). Es decir, hacemos dp[mask | 2^k][k] = verdadero si dp[máscara][último] = verdadero Y máscara & 2^k = 0 (el vértice k aún no ha sido visitado) Y hay una última arista -> k.
En última instancia, existe una ruta hamiltoniana si hay un valor verdadero en dp para los parámetros de la máscara de bits de todos unos y cualquier último vértice.