Forward Checking - CSP paso a paso
Asigna variables y observa cómo se reducen los dominios de las demás. Si algún dominio se vacía, tocaría hacer backtracking (deshacer la asignación anterior y probar otro valor).
-
Aún no se ha asignado ninguna variable. Empieza por la primera.
- Restricciones: -
- Al asignar un valor, se elimina automáticamente de los dominios de todas las variables con las que tiene restricción.
- Si un dominio queda vacío, no hay solución con esa asignación: hay que hacer backtracking.
El backtracking es un algoritmo completo (siempre encuentra solución si existe) pero, en el peor caso, su coste es exponencial:
O(dn)
-
d= tamaño del dominio (número de valores distintos que puede tomar una variable). -
n= número de variables del problema.
En este escenario: -
Comparación con otros problemas del examen:
| Problema | n | d | Combinaciones (dn) |
|---|---|---|---|
| Coloreado 4 ciudades / 3 colores | 4 | 3 | 81 |
| Mapa 2×2 (4 regiones) / 2 colores | 4 | 2 | 16 |
| 4 reinas | 4 | 4 | 256 |
| 8 reinas | 8 | 8 | 16 777 216 |
| Sudoku 9×9 (81 celdas, 9 dígitos) | 81 | 9 | ≈ 1,97 · 1077 |
Por eso el Forward Checking es tan útil: al reducir los dominios antes de asignar, muchos subárboles se podan sin llegar a explorarlos. El coste teórico sigue siendo exponencial, pero en la práctica se exploran muchísimas menos combinaciones.