El retroceso es un algoritmo para encontrar soluciones mediante la exploración sistemática de candidatos, descartando aquellos que no cumplen con los requisitos del problema. Se implementa típicamente mediante una búsqueda en profundidad (DFS), a menudo usando recursividad.

Ejemplo: Generación de números de dos dígitos

Imprimir todos los números de dos dígitos (incluyendo aquellos con un dígito, rellenando con ceros a la izquierda). Esto se puede lograr con dos bucles anidados.

#include <iostream>

int main() {
    for (int decena = 0; decena < 10; ++decena) {
        for (int unidad = 0; unidad < 10; ++unidad) {
            std::cout << decena << unidad << ' ';
        }
    }
    return 0;
}

Ejemplo: Generación de números en base 3 con n dígitos

Generar todos los números en base 3 con hasta n dígitos, rellenando con ceros a la izquierda hasta completar la longitud. Esto se resuelve de forma elegante con retroceso recursivo.

#include <iostream>
#include <vector>

void explorar(int profundidad_maxima, std::vector<int>& estado_actual) {
    if (estado_actual.size() == profundidad_maxima) {
        for (int digito : estado_actual) {
            std::cout << digito;
        }
        std::cout << ' ';
        return;
    }
    for (int opcion = 0; opcion < 3; ++opcion) {
        estado_actual.push_back(opcion);
        explorar(profundidad_maxima, estado_actual);
        estado_actual.pop_back();
    }
}

int main() {
    int n;
    std::cout << "Ingrese n: ";
    std::cin >> n;
    std::vector<int> estado_actual;
    explorar(n, estado_actual);
    return 0;
}

Generalizaciones:

1. Generar números en base m (cambiar el límite del bucle de 3 a m).
2. Incluir representaciones con ceros a la izquierda como secuencias válidas (el código anterior ya lo hace, por ejemplo, para n=2 y m=2 genera: 00, 01, 10, 11, que corresponden a 0, 1, 2, 3).

Componentes esenciales del retroceso

1. Estado (Camino): Las decisiones tomadas hasta el momento. La operación de retroceder se encarga de deshacer la última decisión para explorar otras ramas.
2. Condición de terminación: El punto en el que se ha construido una solución completa o se sabe que no se puede avanzar más.
3. Procesamiento de solución: La lógica aplicada cuando se alcanza la condición de terminación (ej., imprimir o almacenar la solución).
4. Opciones (Hijos): El conjunto de decisiones válidas disponibles en el estado actual.
5. Recursión (Exploración): La inovcación recrusiva que explora cada opción, avanzando en el árbol de decisiones.

En muchos problemas, se aplica poda antes de explorar todas las opciones, para descartar ramas que con certeza no llevarán a una solución válida, reduciendo así el espacio de búsqueda.

Complejidad temporal

La complejidad teórica es O(LP), donde L es el número de opciones en cada nivel y P es la profundidad del árbol de decisiones. La poda efectiva puede reducir drásticamente el tiempo de ejecución en la práctica.

Definición formal

El algoritmo de retroceso (o backtrack) construye soluciones de forma incremental. En cada paso, elige una opción entre las disponibles. Si la opción elegida lleva a una solución (o promete alcanzarla), avanza recursivamente. Si se determina que la elección actual es inviable, se retrocede (se deshace la última elección) y se prueba con la siguiente opción disponible. Es fundamentalmente un recorrido en profundidad de un árbol de decisiones implícito.