En los problemas de retroceso, generalmente desea crear una configuración que satisfaga algunas condiciones dadas (por ejemplo, N reinas, generar todas las permutaciones …). Backtrack funciona construyendo una configuración, paso a paso:
- Divida el problema en N pasos, en cada paso agrega algo a la configuración.
- En el primer paso:
- Pruebe el 1er valor para el i-ésimo paso
- Continúe con el paso i + 1, llamando a la misma función de retroceso, pero aumente el paso en 1
- Ahora estamos de vuelta en el paso i, pero ya probamos todas las configuraciones posibles para el paso i + 1..N
- Pruebe el segundo valor para el i-ésimo paso
- Continúe con el paso i + 1, …
- Volver al paso i otra vez
Veamos un ejemplo en el que desea generar todas las permutaciones de (1, 2, 3, 4):
- En cada paso, agregará 1 número a la permutación actual
Detalles:
- ¿El aprendizaje automático es beneficioso para nosotros en el futuro?
- ¿Pueden las máquinas cometer errores?
- ¿Cuál fue la función principal de los tubos de vacío en las computadoras de primera generación?
- ¿Cuál es la mejor manera de probar el aprendizaje automático?
- ¿Cómo se estructura un virus informático?
- Paso 1:
- Pruebe 1 → su configuración es [1, ???]
- Continúe con el paso 2:
- Prueba 2 → [1, 2, ??]
- Continúe con el paso 3:
- Prueba 3 → [1, 2, 3,?]
- Continúe con el paso 4:
- Prueba 4 → [1, 2, 3, 4]
- De vuelta en el paso 3
- Prueba 4 → [1, 2, 4,?]
- Continúe con el paso 4:
- Prueba 3 → [1, 2, 4, 3]
- De vuelta en el paso 3
- No hay más valor para probar, hecho
- De vuelta en el paso 2
- Prueba 3 → [1, 3, ??]
- Continúe con el paso 3:
- Prueba 2 → [1, 3, 2,?]
- Continúe con el paso 4:
- Prueba 4 → [1, 3, 2, 4]
- De vuelta en el paso 3
- Prueba 4 → [1, 3, 4,?]
- Continúe con el paso 4:
- Prueba 2 → [1, 3, 4, 2]
- No hay más valor para probar, hecho
- De vuelta en el paso 2
- Prueba 4 → [1, 4, ??]
- …
- De vuelta en el paso 1
- Prueba 2 → [2, ???]
- Continúe con el paso 2:
- Prueba 1 → [2, 1, ??]
- …
