¿Qué es el retroceso en un diseño de algoritmo?

Me gustaría explicarlo con un algoritmo clásico de resolución de rompecabezas de N-Queens .

Problema: dado un tablero de ajedrez NxN (supongamos que 8 × 8 por ahora), debes colocar N reinas en él para que no se ataquen dos. (Supongo que sabes cómo se mueve la reina en el ajedrez).

El retroceso funciona creando una “solución candidata” de forma incremental. En el caso de un problema de N-Queens, las reinas se colocan de forma incremental y se aseguran de que no haya dos reinas que se ataquen entre sí. Es decir, coloca a la primera reina en alguna posición, digamos P1. Si la primera reina está en la posición P1, ¿cómo puedes colocar la segunda mientras satisfaces las condiciones? Piénsalo para la tercera, cuarta y finalmente la enésima reina.

Si la solución candidata no cumple las condiciones en algún momento, entonces ” se borran los cambios en algunos pasos anteriores” y se prueban otros candidatos. Recuerda que todo N! las permutaciones no son soluciones para N-Queens, pero el algoritmo intenta todo eso. Muchos de ellos fallan.

Si desea visualizar la ejecución, piense en el árbol de llamadas recursivas. Cuando caminas por el árbol eligiendo alguna rama, haces ciertos cambios. Esos cambios se ” deshacen” cuando subes por el árbol para probar alguna otra rama.

def n_queens (k):
si k es (N + 1), entonces la solución es válida. Imprímelo.
para i: = 1 a N:
si colocar kth queen en (fila k, col i) es seguro:
colocar reina en (fila k, col i)
n_queens (k + 1)
eliminar reina de (fila k, col i)

Eso es todo. Haga cambios antes de hacer una llamada recursiva. Deshacer los cambios después de esa llamada.

Backtracking es un paradigma de diseño de algoritmos. Por paradigma me refiero a un enfoque para la resolución de problemas. Es una familia de algoritmos realmente. Es una forma de agotar sistemáticamente un espacio de búsqueda cuando el problema en cuestión requiere búsqueda. Entonces, esto es una especie de prueba de que una solución de retroceso es correcta porque busca en todo el espacio de estados. Como consecuencia, el tiempo de ejecución de su algoritmo dependerá del tamaño del espacio de búsqueda.

La recursión es útil cuando desea aplicar el retroceso para resolver un problema. Llamo a mi función de backtrack y backtrack y toma un state como entrada. El estado depende del problema, podría ser un tablero de ajedrez parcialmente lleno, parte de una permutación, etc. Lo primero que hago es verificar si el estado de entrada es un goal state , final state o lo que quieras nombrar, esto responde a la pregunta: ¿es el estado una solución al problema? Si ese es el caso, entonces proceso ese estado (podría ser: imprimir algo, incrementar un contador, etc.). Si este no es el caso, entonces tengo que continuar la búsqueda y la forma en que lo hago es tener una función que generate candidate states desde el estado de entrada y luego recursively call backtrack a los estados recién generados. Esto nos acerca un paso más a una solución (si la hay).

Esto es como la primera búsqueda en profundidad, excepto que la estructura del gráfico es implícita. La creatividad en una solución de retroceso no es el algoritmo en sí, es mecánico; la creatividad está en cómo va a representar a los estados y cómo va a generar estados candidatos. Dependiendo de la representación que use, su algoritmo puede terminar tomando enormes cantidades de tiempo para terminar o tomar solo unos segundos para terminar (también depende del tamaño del problema).

Por favor, eche un vistazo a este artículo. Creo que esto te ayudará. 🙂

Explicación recursiva hacia atrás