Satisfacción de restricciones

Introducción

Una de las tareas importantes de la inteligencia artificial (IA) es el problema de satisfacción de restricciones . La teoría UR ofrece un aparato conveniente y un esquema formal simple para representar y resolver problemas de IA combinatoria.

El objetivo de resolver el problema de RO es encontrar los valores de las variables que satisfacen las restricciones dadas.

El problema de la existencia de soluciones al problema PR es NP-completo .

Estrechamente relacionada con la teoría RO está la programación de restricciones , que es un paradigma de programación para la descripción declarativa y la solución eficiente de problemas combinatorios. Muchos problemas combinatorios clásicos, como el famoso teorema de Fermat , el Problema de Satisfacción (SAT) de la lógica proposicional, el problema de coloración de grafos y el problema de isomorfismo de grafos de la teoría de grafos, pueden formularse como problemas VR (SLT). Detengámonos con más detalle en uno de los problemas de larga data en matemáticas: el problema de colorear un gráfico , un caso especial del cual es el conocido problema de colorear un mapa . La formulación del problema de coloración en forma de problema RO asigna variables a los vértices del gráfico a colorear, los colores posibles son dominios (dominios) de variables, y las restricciones de desigualdad entre vértices adyacentes son las restricciones del problema.

Por supuesto, aquí es imposible describir en detalle todos los aspectos y direcciones de la teoría de la satisfacción de restricciones y programación en restricciones, por lo tanto, se puede encontrar información y bibliografía más completa en la monografía traducida por Russell S., Norvig P., que cubre los temas de SR y en la revisión de O.A. Shcherbina.

Ushakov y Telerman (2000) ofrecen una revisión de las principales áreas de programación restringida antes del año 2000.

Historia

Veamos primero la terminología y la historia del surgimiento de los métodos UR. Montanari sugirió usar modelos VR para describir una serie de problemas combinatorios que surgen en el procesamiento de imágenes por computadora, y llamó a estos problemas VR "redes de restricciones" (redes de restricciones). Esto se debe al hecho de que el sistema de restricciones se puede representar como un gráfico no dirigido con vértices y aristas variables que corresponden a restricciones entre dos variables. Según Dechter, las redes de restricciones son una representación gráfica utilizada para encontrar estrategias para resolver problemas de LR. Rápidamente, este enfoque se utilizó para resolver una clase de problemas mucho más amplia. La literatura científica utiliza ambos términos, redes de restricciones y problemas de satisfacción de restricciones.

Más formalmente, el problema de satisfacción de restricciones (CR) es una tupla , donde es el conjunto de variables, es el conjunto de dominios de valores variables y es el conjunto de restricciones.

Ejemplos de problemas de satisfacción de restricciones

Demos una serie de ejemplos que ilustran la formulación de problemas de ER en otras áreas de las matemáticas.

Problemas de optimización y problemas de RO

La solución del problema de optimización se puede reducir a la solución de una secuencia de problemas OE de la siguiente manera. Se encuentra una solución factible, luego de lo cual se agrega una restricción correspondiente a la función objetivo, que expresa la condición de que el valor de la función objetivo debe ser mejor que para esta solución. Ajustes sucesivos a este valor umbral, realizados hasta que el problema se vuelve irresoluble, nos permiten encontrar la solución óptima.

Ejemplo 1. El ejemplo algebraico más trivial del problema EC es el problema de resolver un sistema de ecuaciones. Dado un sistema de ecuaciones lineales sobre un campo finito . ¿Tiene ella una solución? Está claro que en este ejemplo, cada ecuación individual es una restricción, con las variables de la ecuación formando un rango y el conjunto de todas las tuplas correspondientes a las soluciones de la ecuación formando una relación de restricción.

Ejemplo 2. El problema estándar de 3 satisfacciones proposicionales (3-SAT) se define dando una fórmula lógica proposicional que consta de una conjunción de cláusulas, cada cláusula contiene 3 literales (un literal es una variable o su negación), y respondiendo a la pregunta si hay valores de las variables que hacen que la fórmula sea verdadera. Sea tal fórmula, donde son cláusulas . El problema de factibilidad para puede expresarse como un problema SR , donde es el conjunto de todas las variables en la fórmula, y es el conjunto de restricciones , donde cada restricción se construye de la siguiente manera: es la lista de variables incluidas en , y consta de todas tuplas que hacen verdadera la cláusula .

Las soluciones a este problema de RO son asignar valores a las variables que hacen que la fórmula sea verdadera. Por lo tanto, cualquier problema de 3-satisfacibilidad puede expresarse como un problema SR.

El problema de RO también se puede convertir en un problema de factibilidad de SAT. Para un ZUO dado, construimos el problema de satisfacibilidad del SAT de la siguiente manera. Introduzcamos variables. Las variables se establecen en verdadero si y solo si el valor se asigna a la variable. Para cada variable, se agregan cláusulas (disyuntivas) para todos los pares de valores de la misma variable para garantizar que la variable no pueda tener dos valores diferentes al mismo tiempo. Se agrega una cláusula para garantizar que se asigne al menos un valor a la variable.

Ejemplo 3. Cualquier tarea específica de la MA se puede expresar de forma lógica. De hecho, usando la correspondencia estándar entre relaciones y predicados, uno puede reescribir el problema RO como una fórmula de primer orden, donde predicados sobre y significa el predicado aplicado a la tupla de variables. La pregunta es si esta fórmula es factible. Esta tarea se usa comúnmente en la teoría de bases de datos porque corresponde a la evaluación de una consulta conjunta, como se muestra en el siguiente ejemplo.

Ejemplo 4 Una base de datos relacional se puede ver como un conjunto finito de tablas. Una tabla consta de un esquema y datos específicos, donde el esquema es un conjunto finito de atributos, cada atributo tiene un conjunto correspondiente de valores posibles, denominado dominio. Los datos concretos son un conjunto finito de filas, donde cada fila es una asignación que asigna cada atributo de esquema a un valor de su dominio. Una tarea estándar para las bases de datos relacionales es el problema de evaluación de consultas conjuntivas, que pregunta si la solución tiene una consulta conjuntiva, es decir, consulta de la forma , donde están las fórmulas atómicas. Una consulta conjunta sobre una base de datos relacional corresponde a un ejemplo específico de un problema de LR, que se logra mediante un simple reemplazo de términos: "atributos" se reemplazan por "variables", "tablas" por "restricciones", "esquema" por " rango", "datos específicos" por "relación de restricción" y "cadenas" por "tuplas". Por lo tanto, una consulta conjuntiva equivale a un ejemplo específico de una tarea de RO cuyas variables son atributos de consulta. Para cada fórmula atómica en la consulta, existe una restricción de modo que el rango de restricción es una lista de variables de fórmula y la relación de restricción es un conjunto de modelos.

Literatura