Búsqueda de retroceso , el retroceso es un método general para encontrar soluciones a un problema que requiere una enumeración completa de todas las opciones posibles en un determinado conjunto M. Como regla general, le permite resolver problemas que hacen preguntas como: "Enumere todas las opciones posibles". ..”, “¿De cuántas formas...”, “¿Hay alguna forma de...?”, “¿Existe un objeto...”, etc.
El término retroceso fue acuñado en 1950 por el matemático estadounidense Derrick Henry Lehmer .
Las modificaciones menores del método de retroceso relacionadas con la representación de datos o las características de implementación tienen otros nombres: método de ramificación y límite , búsqueda en profundidad primero , método de prueba y error , etc. Muchos investigadores inventaron la búsqueda de retroceso casi simultáneamente e independientemente antes de su descripción formal.
La solución del problema por el método de backtracking se reduce a la expansión sucesiva de una solución parcial. Si en el siguiente paso dicha expansión falla, entonces regresan a una solución parcial más corta y continúan la búsqueda. Este algoritmo le permite encontrar todas las soluciones al problema, si existen. Para acelerar el método, intentan organizar los cálculos de tal manera que identifiquen opciones obviamente inadecuadas lo antes posible. A menudo, esto puede reducir significativamente el tiempo para encontrar una solución.
Un ejemplo clásico del uso de un algoritmo de retroceso es el problema de las ocho reinas . Su redacción es la siguiente: "Disponga 8 reinas en un tablero de ajedrez estándar de 64 celdas para que ninguna de ellas sea atacada por otra". Primero, se coloca una reina en el tablero, y luego intentan colocar cada reina siguiente para que no sea derrotada por las reinas ya establecidas. Si en el siguiente paso no se puede hacer tal configuración, retroceden un paso e intentan colocar la reina previamente instalada en otro lugar.
Además, el método de retroceso le permite resolver muchos otros problemas de enumeración. Por ejemplo, usándolo puede obtener todos los subconjuntos , ubicaciones , permutaciones , combinaciones de un conjunto M dado.
El método de retroceso es genérico. Es bastante fácil diseñar y programar algoritmos para resolver problemas utilizando este método. Sin embargo, el tiempo para encontrar una solución puede ser muy largo incluso con pequeñas dimensiones del problema (la cantidad de datos iniciales), y es tan largo (pueden ser años o incluso siglos) que no puede haber dudas sobre la aplicación práctica. . Por lo tanto, al diseñar dichos algoritmos, es necesario estimar teóricamente el tiempo de su trabajo en datos específicos. También hay problemas de selección, para los que puede crear algoritmos únicos y "rápidos" que le permitan obtener rápidamente una solución incluso con grandes dimensiones del problema. El método de retroceso es ineficaz en tales problemas.