Problema de satisfacción de restricciones

Los CSP son el tema de una intensa investigación en Inteligencia Artificial e Investigación de operaciones, dado que la generalidad en su formulación provee un principio básico para analizar y resolver problemas de distintos tipos.Los CSP a menudo muestran gran complejidad, requiriendo una combinación de métodos heurísticos y búsqueda combinatoria para ser resueltos en un tiempo razonable.Las técnicas más usadas son variantes de búsqueda con retroceso cronológico (backtracking), propagación de restricciones, y búsqueda local.Por cada valor, la consistencia de la asignación parcial es chequeada con respecto a las restricciones; en caso de consistencia, un llamado recursivo es hecho.En este algoritmo básico con retroceso cronológico, la consistencia es definida como la satisfacción de todas las restricciones donde las variables estén asignadas.Backmarking mejora la eficiencia del chequeo de consistencia.Look-ahead es también a menudo usado en backtracking para intentar prever el efecto de seleccionar una variable o un valor, por lo tanto, determinar a veces con anticipación cuándo es satisfasible o insatisfasible un subproblema.Primero, cambia el problema en otro que es equivalente pero usualmente más simple de resolver.Segundo, puede probar la satisfacibilidad o la insatisfacibilidad de problemas.En la práctica, búsqueda local parece funcionar bien cuando estos cambios son también afectados por una selección aleatoria.CSPs son estudiados también en Teoría de la complejidad computacional.Si el teorema Dicotomía es verdadero, entonces CSPs provee uno de los subconjuntos más grandes conocidos de NP los que evitan problemas NP-intermedio, cuya existencia fue demostrada por el teorema de Ladner bajo la suposición que P ≠ NP.El teorema de Schaefer sobre dicotomía maneja el caso cuando todas las relaciones disponibles son operadores booleanos, eso es para dominio de tamaño 2.[1]​ Una situación similar existe entre las clases funcionales FP y #P. Por una generalización del teorema de Ladner, también hay problemas que no son FP ni #P-completo tan grande como FP ≠ #P. Como en el caso de decisión, un problema en el #CSP es definido por un conjunto de relaciones.Cada problema toma una fórmula booleana como entrada y la tarea es computar el número de asignaciones que satisfacen las restricciones.Esto puede ser generalizado usando tamaño de dominios grandes y fijar un peso asignación que satisface y computando la suma de estos pesos.Es conocido que cualquier problema complejo con peso #CSP está en FP o #P-hard.Este modelo rígido es un defecto que lo hace difícil para representar problemas fácilmente.Varias modificaciones a la definición básica de CSP han sido propuestas para adaptar el modelo a una amplia variedad de problemas.[3]​ los DCSP son vistos como una secuencia de CSP estáticos, cada uno es una transformación del anterior en el que variables y restricciones pueden ser adicionadas (restriction) o eliminadas (relaxation).La información encontrada en la formulación inicial del problema puede ser usada para refinar los siguientes.El método de solución puede ser clasificado acorde a la forma en que la información es transferida: Los CSP clásicos tratan las restricciones como fuertes, significan que son inviolables (cada solución las debe satisfacer por completo) e inflexible (en este sentido las restricciones deben ser completamente cumplidas o por el contrario son completamente violadas).Los CSP flexibles relajan estas suposiciones, relajan parcialmente las restricciones y permiten a la solución no cumplir con exactamente todas las restricciones.