Backtracking (vuelta atrás)
Mira cómo se construye el árbol de búsqueda decisión a decisión, dónde se poda y cómo cambia el código si quieres todas las soluciones, una o la mejor.
1// Globales: n objetos, capacidad C, pesos P[1..n],2// beneficios B[1..n] y decisiones x[1..n]3void mochila(int k)4{5 int v;6 for (v = 0; v <= 1; v++) { // hermanos del nivel k7 x[k] = v; // 0: fuera, 1: dentro8 if (peso(k) <= C) { // ¿correcto?9 if (k == n) // ¿solución?10 tratar(x);11 else12 mochila(k + 1); // siguiente objeto13 }14 }15}Llamada inicial mochila(1): decido el objeto 1 de 4. Capacidad 8.
| Objeto | 1 | 2 | 3 | 4 |
| Peso | 3 | 4 | 2 | 5 |
| Beneficio | 8 | 10 | 3 | 12 |
(sin salida todavía)Cada nivel decide un objeto (0 = fuera, 1 = dentro); debajo, el peso acumulado.
Backtracking, o vuelta atrás, es un esquema para problemas cuya solución es una secuencia de decisiones x[1], x[2], …, x[n]. Se prueba una opción para cada decisión y se pasa a la siguiente; cuando no quedan opciones, se vuelve atrás y se prueba otra en la decisión anterior.
Todas las combinaciones forman un árbol de búsqueda: cada nivel es una decisión y cada hoja, una secuencia completa. La clave es podar: si una solución parcial ya no puede ser correcta (en la mochila, porque se pasa de peso), no se exploran sus descendientes.
El mismo esquema da tres variantes. Para todas las soluciones se trata cada hoja válida; para una, se corta la búsqueda al encontrar la primera; y para la óptima se recorren todas guardando la mejor en x_mejor y v_mejor.
Mochila de capacidad 8 con objetos de pesos 3, 4, 2 y 5 y beneficios 8, 10, 3 y 12. ¿Qué objetos se meten para ganar lo máximo?
- Cada x[k] vale 0 (fuera) o 1 (dentro): hay 2⁴ = 16 combinaciones.
- Se poda cualquier rama que supere el peso 8: por ejemplo, meter los objetos 1, 2 y 3 ya pesa 9.
- Entre las válidas, <1 0 0 1> pesa 8 y vale 20; <1 1 0 0> pesa 7 y vale 18; <0 1 1 0> pesa 6 y vale 13.
- La mejor es <1 0 0 1>.
Objetos 1 y 4: peso 8 y beneficio 20
Preguntas frecuentes
¿Qué diferencia hay entre backtracking y fuerza bruta?
La fuerza bruta genera todas las combinaciones y luego comprueba cada una. Backtracking comprueba cada solución parcial y abandona las ramas que ya no pueden llegar a nada, así que suele generar muchos menos nodos.
¿Cuál es la complejidad del backtracking?
En el peor caso, exponencial: el tamaño del árbol, como 2ⁿ en la mochila 0/1. Las podas no cambian ese peor caso, pero en la práctica reducen mucho el trabajo.
¿Por qué la primera solución de la mochila es no meter nada?
Porque en cada nivel se prueba primero x[k] = 0, y la mochila vacía siempre cabe. Si se probara primero el 1, la primera solución sería otra.
¿Para qué sirve la cota del bucle en la descomposición?
for (v = 1; v <= N − suma − (M − k); v++) deja al menos 1 para cada sumando que falta. Así nunca se genera una rama sin solución: es una poda metida en el propio bucle.