¿Qué es el retroceso en algoritmos?

Backtracking = {rastrear la posible solución y devolver si es cierto, de lo contrario volver y así sucesivamente}
En el retroceso, comenzamos con un posible movimiento de muchos movimientos disponibles e intentamos resolver el problema si somos capaces de resolver el problema con el movimiento seleccionado, luego imprimiremos la solución; de lo contrario, retrocederemos y seleccionaremos otro movimiento e intentaremos resuélvelo. Si ninguno, si los movimientos funcionan, alegaremos que no hay solución para el problema.

Algoritmo Generalizado:

Elige un punto de partida.
while (el problema no está resuelto)
Para cada ruta desde el punto de partida.
compruebe si la ruta seleccionada es segura, en caso afirmativo selecciónela
y hacer una llamada recursiva al resto del problema
Si las llamadas recursivas devuelven verdadero, entonces devuelve verdadero.
de lo contrario, deshaga el movimiento actual y devuelva falso.
Fin para
Si ninguno de los movimientos funciona, devuelve false, NO SOLUTON.

Retroceder es uno de los buenos algoritmos, en el que tratamos de encontrar la solución a un problema dado, moviéndonos en varias direcciones (o rutas) y rechazando esas direcciones (o rutas) que encontramos que no nos darían solución requerida

Por ejemplo (el más simple), suponga que el enunciado del problema es encontrar tres números cuya suma de es 10 entre estos números dados (3,2,7,5,6,8). comenzamos con 3 + 2 + 7 = 12, que es mayor que 10. Entonces retrocedemos (significa que retrocedemos un paso), ahora agregamos 3 + 2 + 5 = 10. allí vamos y de esta manera encontramos la solución requerida.

Entonces, retroceder significa rastrear (o mover) hacia atrás para encontrar otra ruta para obtener la solución requerida.

El retroceso es un método de búsqueda exhaustiva que utiliza divide y vencerás.

• a veces lo mejor para un problema es probar todas las posibilidades.
• Esto siempre es lento.
• El retroceso acelera la búsqueda exhaustiva mediante la poda.

Ejemplos:

• Cadenas binarias: generación de todas las cadenas binarias.
• Generación de cuerdas k-ary
• Problema de mochila
• Ciclos hamiltonianos
• Problema de coloración del gráfico

En los algoritmos de retroceso, intenta construir una solución paso a paso. Si en algún paso queda claro que la ruta actual en la que se encuentra no puede conducir a una solución, regrese al paso anterior (retroceso) y elija una ruta diferente. Básicamente, una vez que agota todas sus opciones en un cierto paso, retrocede. El ejemplo clásico para dar marcha atrás es el rompecabezas de las ocho reinas. En esta solución de retroceso, coloca la reina i en la fila i en alguna columna j y verifica que no amenace a una reina en las filas i-1.

reinas = [0,0…, 0]
para i = 1 a maxRows:
para j = 1 a maxRows:
reinas [i] = reinas [i] ++
si queensNotUnderAttack (i) entonces:
descanso
más:
si j == maxRows entonces: i–

No hay solución si me convierto en 0 (era demasiado vago para escribir el código que lo verifica). Sin embargo, N-Queens siempre tiene una solución.

Backtracking es un algoritmo para encontrar soluciones a algunos problemas computacionales. Incrementa gradualmente a los candidatos a las soluciones y rastrea al abandonar cada candidato parcial c tan pronto como determina que c no puede proporcionar una solución válida. Por lo tanto, al retroceder intentamos resolver un subproblema y, si no alcanzamos la solución deseada, deshacemos lo que hicimos para resolver ese subproblema e intentamos resolver otro subproblema. El problema de N-reinas es un problema clásico de retroceso.

Estudie programación con Codingplex.

El retroceso es un refinamiento del enfoque de la fuerza bruta, que busca sistemáticamente una solución a un problema entre todas las opciones disponibles.

Este artículo lo explica mejor: Algoritmos de retroceso

Cuando se puede construir una solución en pasos, y hay más de una opción para completar cada paso, puede probar una de ellas primero, y si algo sale mal / peor, puede volver a este paso para probar otra.