Aprende el algoritmo de retroceso

Question

Quiero aprender el algoritmo de retroceso. ¿Puede alguien por favor enseñarme algo de eso? Intenté aprender de algunos sitios web, pero no funcionó. Entonces alguien puede por favor enseñarme. ¡Gracias!

Answer 1

Aunque es independiente del idioma, el tutorial this es bueno y presenta varios ejemplos que pueden proporcionar la intuición necesaria.

Dicho esto, la idea detrás del retroceso no es difícil de entender en absoluto. Un algoritmo de retroceso esencialmente explora todo el espacio de solución al igual que cuando se realiza una fuerza bruta, excepto (y esto lo hace más eficiente) retrocede desde una solución parcial tan pronto como ya que se da cuenta de que no es factible.

Un ejemplo

considerar esta solución parcial para el conocido eight queens problem.

Las reinas en las cuatro primeras columnas ya se han posicionado, pero el último es uno en una plaza válido. Una solución de fuerza bruta continuaría colocando reinas para el resto de las columnas, sin tener en cuenta el hecho de que, independientemente de cómo se aumente esta solución parcial, el resultado no será válido.

El algoritmo de retroceso será "más inteligente": se dará cuenta de que la cuarta reina está mal colocada y "volverá" a considerar otros cuadrados para ello.

Answer 2

Fundamentals Of Computer Algorithms contiene un buen capítulo sobre retroceso. Pero no ha especificado cuánto se familiariza con el texto del algoritmo formal y las estructuras de datos. Puede tener algunos problemas al leer este libro si no está familiarizado con los aspectos algorítmicos básicos como el análisis de complejidad o no sabe qué es un árbol. Me refiero a que en ese caso necesitarás leer el libro desde el principio, el salto directo al capítulo de retroceso no será de mucha ayuda.