El proceso iterativo de aplicar restricciones en una red de restricciones para reducir los dominios de las variables eliminando valores que no pueden formar parte de ninguna solución, implementado frecuentemente mediante consistencia de arcos, comprobación adelantada o algoritmos de consistencia generalizados.

Principio

Usar relaciones locales de restricción para inferir y suprimir valores imposibles, reduciendo dominios y exponiendo asignaciones forzadas; la aplicación repetida ajusta el problema y reduce las bifurcaciones combinatorias.

Demostración

En un CSP binario con la restricción X ≠ Y y dominios X = {1,2}, Y = {2,3}, la propagación elimina 2 del dominio de X si Y queda fijado a 2, y la consistencia de arcos puede eliminar iterativamente valores hasta estabilizarse.

Aplicación incorrecta

Una propagación global excesivamente agresiva sin considerar el coste puede malgastar tiempo con poco poda (alto overhead), y una propagación ingenua que ignore dependencias entre restricciones puede producir reducciones de dominio incorrectas si se implementa mal.

Consecuencia

La propagación de restricciones aplicada correctamente reduce sustancialmente la búsqueda al eliminar temprano ramas inviables, convirtiendo a menudo una búsqueda intratable en practicable cuando se combina con heurísticas de búsqueda.

Inversión

Lo inverso es realizar búsqueda sin ninguna propagación (enumeración pura por fuerza bruta), que siempre es correcta pero típicamente mucho menos eficiente por la falta de poda temprana.

Límite

Se aplica a problemas discretos de satisfacción de restricciones y búsqueda combinatoria; dominios continuos requieren técnicas de propagación distintas (aritmética de intervalos, relajación de restricciones) y ciertas restricciones globales exigen propagadores especializados.

Tensión semántica

Existe tensión entre la propagación local (consistencia de arcos) y las nociones de consistencia global: una consistencia más fuerte produce mejor poda pero a mayor coste computacional; la compensación depende del problema.

Síntesis

La propagación de restricciones es la aplicación disciplinada de deducciones locales para podar incrementalmente los dominios de variables, equilibrando el poder de poda con el coste computacional para hacer práctica la búsqueda combinatoria.