Problema de satisfacción de restricciones

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Conjunto de objetos cuyo estado debe satisfacer límites

Problemas de satisfacción de restricciones (CSP) son cuestiones matemáticas definidas como un conjunto de objetos cuyo estado debe satisfacer una serie de restricciones o limitaciones. Los CSP representan las entidades en un problema como una colección homogénea de restricciones finitas sobre las variables, que se resuelve mediante métodos de satisfacción de restricciones. Los CSP son objeto de investigación tanto en inteligencia artificial como en investigación de operaciones, ya que la regularidad en su formulación proporciona una base común para analizar y resolver problemas de muchas familias aparentemente no relacionadas. Los CSP a menudo exhiben una gran complejidad, lo que requiere una combinación de heurística y métodos de búsqueda combinatorios para ser resueltos en un tiempo razonable. La programación con restricciones (CP) es el campo de investigación que se enfoca específicamente en abordar este tipo de problemas. Además, el problema de satisfacibilidad booleano (SAT), las teorías del módulo de satisfacibilidad (SMT), la programación de enteros mixtos (MIP) y la programación de conjuntos de respuestas (ASP) son campos de investigación que se centran en la resolución de formas particulares del problema de satisfacción de restricciones.

Los ejemplos de problemas que se pueden modelar como un problema de satisfacción de restricciones incluyen:

Tipo de referencia
Ocho reinas puzzle
Mapa problema para colorear
Problema máximo de corte
Sudoku, Crosswords, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato y muchos otros rompecabezas lógicos

A menudo se proporcionan con tutoriales de solucionadores CP, ASP, Boolean SAT y SMT. En el caso general, los problemas de restricciones pueden ser mucho más difíciles y es posible que no se puedan expresar en algunos de estos sistemas más simples. "La vida real" los ejemplos incluyen planificación automatizada, eliminación de ambigüedades léxicas, musicología, configuración de productos y asignación de recursos.

La existencia de una solución para un CSP puede verse como un problema de decisión. Esto se puede decidir encontrando una solución o no logrando encontrar una solución después de una búsqueda exhaustiva (los algoritmos estocásticos generalmente nunca llegan a una conclusión exhaustiva, mientras que las búsquedas dirigidas a menudo lo hacen, en problemas suficientemente pequeños). En algunos casos, se puede saber que el CSP tiene soluciones de antemano, a través de algún otro proceso de inferencia matemática.

Definición formal

Formalmente, un problema de satisfacción restrictiva se define como un triple $langle X,D,Crangle$ , donde

$X={X_{1},ldotsX_{n}}$ es un conjunto de variables,
$D={D_{1},ldotsD_{n}}$ es un conjunto de sus respectivos dominios de valores, y
$C={C_{1},ldotsC_{m}}$ es un conjunto de limitaciones.

Cada variable $X_{i}$ puede asumir los valores en el dominio no vacío $D_{i}$ . Cada limitación $C_{j}in C$ a su vez un par $langle t_{j},R_{j}rangle$ , donde $t_{j}subset X$ es un subconjunto de $k$ variables y $R_{j}$ es un $k$ - Relación en el subconjunto correspondiente de dominios $D_{j}$ . An evaluación de las variables es una función de un subconjunto de variables a un conjunto particular de valores en el subconjunto correspondiente de dominios. Una evaluación $v$ satisfice una restricción ${displaystyle langle t_{j},R_{j}rangle }$ si los valores asignados a las variables $t_{j}$ satisfacer la relación $R_{j}$ .

Una evaluación es consistente si no viola ninguna de las restricciones. Una evaluación es completa si incluye todas las variables. Una evaluación es una solución si es consistente y completa; se dice que tal evaluación resuelve el problema de satisfacción de restricciones.

Solución

Los problemas de satisfacción de restricciones en dominios finitos generalmente se resuelven mediante una forma de búsqueda. Las técnicas más utilizadas son variantes de backtracking, propagación de restricciones y búsqueda local. Estas técnicas también se combinan a menudo, como en el método VLNS, y la investigación actual involucra otras tecnologías como la programación lineal.

El retroceso es un algoritmo recursivo. Mantiene una asignación parcial de las variables. Inicialmente, todas las variables no están asignadas. En cada paso, se elige una variable y se le asignan todos los valores posibles. Para cada valor, se comprueba la consistencia de la asignación parcial con las restricciones; en caso de consistencia, se realiza una llamada recursiva. Cuando se han probado todos los valores, el algoritmo retrocede. En este algoritmo de backtracking básico, la consistencia se define como la satisfacción de todas las restricciones cuyas variables están todas asignadas. Existen varias variantes de retroceso. El backmarking mejora la eficiencia de la verificación de la consistencia. Backjumping permite guardar parte de la búsqueda retrocediendo "más de una variable" en algunos casos. El aprendizaje de restricciones infiere y guarda nuevas restricciones que luego se pueden usar para evitar parte de la búsqueda. La búsqueda anticipada también se usa a menudo en el retroceso para intentar prever los efectos de elegir una variable o un valor, determinando así a veces por adelantado cuándo un subproblema es satisfactorio o insatisfactorio.

Las técnicas de propagación de restricciones son métodos utilizados para modificar un problema de satisfacción de restricciones. Más precisamente, son métodos que imponen una forma de consistencia local, que son condiciones relacionadas con la consistencia de un grupo de variables y/o restricciones. La propagación de restricciones tiene varios usos. Primero, convierte un problema en uno que es equivalente pero generalmente más simple de resolver. En segundo lugar, puede probar la satisfacción o insatisfacción de los problemas. No se garantiza que esto suceda en general; sin embargo, siempre sucede para algunas formas de propagación de restricciones y/o para ciertos tipos de problemas. Las formas más conocidas y utilizadas de coherencia local son la coherencia de arco, la coherencia de hiperarco y la coherencia de ruta. El método de propagación de restricciones más popular es el algoritmo AC-3, que impone la consistencia del arco.

Los métodos de búsqueda local son algoritmos de satisfacción incompletos. Pueden encontrar una solución a un problema, pero pueden fracasar incluso si el problema es satisfactorio. Funcionan mejorando iterativamente una asignación completa sobre las variables. En cada paso, se cambia el valor de un pequeño número de variables, con el objetivo general de aumentar el número de restricciones satisfechas por esta asignación. El algoritmo min-conflicts es un algoritmo de búsqueda local específico para CSP y se basa en ese principio. En la práctica, la búsqueda local parece funcionar bien cuando estos cambios también se ven afectados por elecciones aleatorias. Se ha desarrollado una integración de búsqueda con búsqueda local, lo que lleva a algoritmos híbridos.

Aspectos teóricos

Problemas de decisión

Los CSP también se estudian en la teoría de la complejidad computacional y la teoría de modelos finitos. Una pregunta importante es si para cada conjunto de relaciones, el conjunto de todos los CSP que se pueden representar usando solo relaciones elegidas de ese conjunto está en P o NP-completo. Si tal teorema de dicotomía es cierto, entonces los CSP proporcionan uno de los subconjuntos más grandes conocidos de NP que evita los problemas intermedios de NP, cuya existencia fue demostrada por el teorema de Ladner bajo el supuesto de que P ≠ NP. El teorema de la dicotomía de Schaefer maneja el caso cuando todas las relaciones disponibles son operadores booleanos, es decir, para tamaño de dominio 2. El teorema de la dicotomía de Schaefer se generalizó recientemente a una clase más grande de relaciones.

La mayoría de las clases de CSP que se sabe que son manejables son aquellas en las que la hipergrafía de restricciones tiene un ancho de árbol limitado (y no hay restricciones en el conjunto de relaciones de restricción), o donde las restricciones tienen una forma arbitraria pero existen esencialmente no- polimorfismos unarios del conjunto de relaciones de restricción.

Cada CSP también se puede considerar como un problema de contención de consultas conjuntas.

Problemas de funcionamiento

Una situación similar existe entre las clases funcionales FP y #P. Por una generalización del teorema de Ladner, tampoco hay problemas ni en FP ni en #P-completo siempre que FP ≠ #P. Como en el caso de decisión, un problema en el #CSP está definido por un conjunto de relaciones. Cada problema toma una fórmula booleana como entrada y la tarea es calcular el número de asignaciones satisfactorias. Esto se puede generalizar aún más utilizando tamaños de dominio más grandes y asignando un peso a cada asignación satisfactoria y calculando la suma de estos pesos. Se sabe que cualquier problema #CSP ponderado complejo está en FP o #P-hard.

Variantes

El modelo clásico de problema de satisfacción de restricciones define un modelo de restricciones estáticas e inflexibles. Este modelo rígido es una deficiencia que dificulta la representación de problemas con facilidad. Se han propuesto varias modificaciones de la definición básica de CSP para adaptar el modelo a una amplia variedad de problemas.

CSP dinámicos

Los CSP dinámicos (DCSP) son útiles cuando la formulación original de un problema se altera de alguna manera, generalmente porque el conjunto de restricciones a considerar evoluciona debido a la ambiente. Los DCSP se ven como una secuencia de CSP estáticos, cada uno de los cuales es una transformación del anterior en el que se pueden agregar (restricción) o eliminar (relajación) variables y restricciones. La información que se encuentra en las formulaciones iniciales del problema se puede utilizar para refinar las siguientes. El método de resolución se puede clasificar según la forma en que se transfiere la información:

Oráculos: la solución encontrada a anteriores CSPs en la secuencia se utilizan como heurística para guiar la resolución de la actual CSP desde cero.
Reparación local: cada CSP se calcula a partir de la solución parcial del anterior y reparando las restricciones inconsistentes con la búsqueda local.
Grabación limitada: se definen nuevas limitaciones en cada etapa de la búsqueda para representar el aprendizaje de un grupo incoherente de decisiones. Esas limitaciones se aplican a los nuevos problemas del CSP.

CSP flexibles

Los CSP clásicos tratan las restricciones como duras, lo que significa que son imperativas (cada solución debe satisfacerlas todas) e inflexibles (en el sentido de que deben cumplirse por completo o bien se violan por completo). Los CSP flexibles relajan esos supuestos, relajando parcialmente las restricciones y permitiendo que la solución no cumpla con todas ellas. Esto es similar a las preferencias en la planificación basada en preferencias. Algunos tipos de CSP flexibles incluyen:

MAX-CSP, donde se permiten varias restricciones, y la calidad de una solución se mide por el número de limitaciones satisfechas.
CSP ponderado, un MAX-CSP en el que cada violación de una restricción se pondera según una preferencia predefinida. Así se prefiere la restricción satisfactoria con más peso.
Limitaciones de modelo de CSP mareadas como relaciones borrosas en las que la satisfacción de una limitación es una función continua de los valores de sus variables, pasando de estar totalmente satisfecha a violarse completamente.

CSP descentralizados

En los DCSP, se considera que cada variable de restricción tiene una ubicación geográfica separada. Se imponen fuertes restricciones al intercambio de información entre variables, lo que requiere el uso de algoritmos totalmente distribuidos para resolver el problema de satisfacción de restricciones.

Contenido relacionado

Más resultados...