Programación de restricciones

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

paradigma de programación donde las relaciones entre variables se establecen en forma de limitaciones

La programación de restricciones (CP) es un paradigma para resolver problemas combinatorios que se basa en una amplia gama de técnicas de inteligencia artificial, informática e investigación de operaciones. En la programación de restricciones, los usuarios declaran de forma declarativa las restricciones sobre las soluciones factibles para un conjunto de variables de decisión. Las restricciones se diferencian de las primitivas comunes de los lenguajes de programación imperativos en que no especifican un paso o una secuencia de pasos a ejecutar, sino las propiedades de una solución a encontrar. Además de las restricciones, los usuarios también deben especificar un método para resolver estas restricciones. Esto generalmente se basa en métodos estándar como el retroceso cronológico y la propagación de restricciones, pero puede usar código personalizado como una heurística de bifurcación específica del problema.

La programación de restricciones tiene su origen y se puede expresar en forma de programación lógica de restricciones, que incorpora restricciones en un programa lógico. Esta variante de programación lógica se debe a Jaffar y Lassez, quienes ampliaron en 1987 una clase específica de restricciones que se introdujeron en Prolog II. Las primeras implementaciones de la programación lógica con restricciones fueron Prolog III, CLP(R) y CHIP.

En lugar de programación lógica, las restricciones se pueden combinar con programación funcional, reescritura de términos y lenguajes imperativos. Los lenguajes de programación con soporte incorporado para restricciones incluyen Oz (programación funcional) y Kaleidoscope (programación imperativa). En su mayoría, las restricciones se implementan en lenguajes imperativos a través de juegos de herramientas para resolver restricciones, que son bibliotecas separadas para un lenguaje imperativo existente.

Programación lógica de restricciones

La programación de restricciones es una incorporación de restricciones en un lenguaje principal. Los primeros lenguajes host utilizados fueron lenguajes de programación lógica, por lo que el campo se llamó inicialmente programación lógica de restricción. Los dos paradigmas comparten muchas características importantes, como variables lógicas y retroceso. Hoy en día, la mayoría de las implementaciones de Prolog incluyen una o más bibliotecas para la programación lógica de restricciones.

La diferencia entre los dos radica en gran medida en sus estilos y enfoques para modelar el mundo. Algunos problemas son más naturales (y, por lo tanto, más simples) para escribir como programas lógicos, mientras que otros son más naturales para escribir como programas de restricción.

El enfoque de programación de restricciones consiste en buscar un estado del mundo en el que se satisfagan un gran número de restricciones al mismo tiempo. Por lo general, un problema se plantea como un estado del mundo que contiene una serie de variables desconocidas. El programa de restricciones busca valores para todas las variables.

La programación con restricciones concurrentes temporales (TCC) y la programación con restricciones concurrentes temporales no deterministas (MJV) son variantes de la programación con restricciones que pueden manejar el tiempo.

Problema de satisfacción de restricciones

Una restricción es una relación entre múltiples variables que limita los valores que estas variables pueden tomar simultáneamente.

Definición—Un problema de satisfacción restrictivo en dominios finitos (o CSP) se define por un triplet ${displaystyle ({mathcal {X}},{mathcal {D}},{mathcal {C}})}$ Donde:

${displaystyle {mathcal {X}}={x_{1},dotsx_{n}}}$ es el conjunto de variables del problema;
${displaystyle {mathcal {D}}={{mathcal {D}}_{1},dots{mathcal {D}}_{n}}}$ es el conjunto de dominios de las variables, es decir, para todos ${displaystyle kin [1;n]}$ tenemos ${displaystyle x_{k}in {mathcal {D}}_{k}}$ ;
${displaystyle {mathcal {C}}={C_{1},dotsC_{m}}}$ es un conjunto de limitaciones. Una limitación ${displaystyle C_{i}=({mathcal {X}}_{i},{mathcal {R}}_{i})}$ se define por un conjunto ${displaystyle {mathcal {X}}_{i}={x_{i_{1}},dotsx_{i_{k}}}}$ de variables y relación ${displaystyle {mathcal {R}}_{i}subset {mathcal {D}}_{i_{1}}times dots times {mathcal {D}}_{i_{k}}}$ que define el conjunto de valores permitido simultáneamente para las variables ${displaystyle {mathcal {X}}_{i}}$ :

Existen tres categorías de restricciones:

limitaciones de extensión: limitaciones se definen enumerando el conjunto de valores que los satisfagan;
limitaciones aritméticas: las limitaciones se definen por una expresión aritmética, es decir, utilizando $<math alttext="{displaystyle ,leqgeq=,neq...}" xmlns="http://www.w3.org/1998/Math/MathML">.,■,≤ ≤ ,≥ ≥ ,=,ل ل ,...{displaystyle > = > }<img alt="{displaystyle ,leqgeq=,neq...}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eeaddf2fabe17a627fbecb6b7278cdf2949be72f" style="vertical-align: -0.838ex; width:19.767ex; height:2.676ex;"/>$ ;
limitaciones lógicas: las limitaciones se definen con una semántica explícita, es decir, AllDifferent, AtMost,...

Definición— Una asignación (o modelo) ${mathcal {A}}$ of a CSP ${displaystyle P=({mathcal {X}},{mathcal {D}},{mathcal {C}})}$ se define por la pareja ${displaystyle {mathcal {A}}=({mathcal {X_{mathcal {A}}}},{mathcal {V_{mathcal {A}}}})}$ Donde:

${displaystyle {mathcal {X_{mathcal {A}}}}subset {mathcal {X}}}$ es un subconjunto de variable;
${displaystyle {mathcal {V_{mathcal {A}}}}={v_{{mathcal {A}}_{1}},dotsv_{{mathcal {A}}_{k}}}in {{mathcal {D}}_{{mathcal {A}}_{1}},dots{mathcal {D}}_{{mathcal {A}}_{k}}}}$ es el tuple de los valores tomados por las variables asignadas.

La asignación es la asociación de una variable a un valor de su dominio. Una asignación parcial es cuando se ha asignado un subconjunto de las variables del problema. Una asignación total es cuando se han asignado todas las variables del problema.

Propiedad—Dado ${displaystyle {mathcal {A}}=({mathcal {X_{mathcal {A}}}},{mathcal {V_{mathcal {A}}}})}$ a la asignación (parcial o total) de un CSP ${displaystyle P=({mathcal {X}},{mathcal {D}},{mathcal {C}})}$ , y ${displaystyle C_{i}=({mathcal {X}}_{i},{mathcal {R}}_{i})}$ a limitación $P$ tales como ${displaystyle {mathcal {X}}_{i}subset {mathcal {X_{mathcal {A}}}}}$ , la asignación ${mathcal {A}}$ satisfice la restricción $C_{i}$ si y sólo si todos los valores ${displaystyle {mathcal {V}}_{{mathcal {A}}_{i}}={v_{i}in {mathcal {V}}_{mathcal {A}}{mbox{ tel que }}x_{i}in {mathcal {X}}_{i}}}$ de las variables de la limitación $C_{i}$ pertenece ${displaystyle {mathcal {R}}_{i}}$ .

Definición—Una solución de un CSP es una asignación total que satisface todas las limitaciones del problema.

Durante la búsqueda de las soluciones de un CSP, un usuario puede desear:

encontrar una solución (que satisfaga todas las limitaciones);
encontrar todas las soluciones del problema;
probar la insaciabilidad del problema.

Problema de optimización de restricciones

Un problema de optimización de restricciones (COP) es un problema de satisfacción de restricciones asociado a una función objetivo.

Una solución óptima a un COP de minimización (maximización) es una solución que minimiza (maximiza) el valor de la función objetivo.

Durante la búsqueda de las soluciones de un COP, un usuario puede desear:

encontrar una solución (que satisfaga todas las limitaciones);

encontrar la mejor solución con respecto al objetivo;
probar la optimización de la solución mejor encontrada;
probar la insaciabilidad del problema.

Modelos de perturbación vs refinamiento

Los lenguajes para la programación basada en restricciones siguen uno de dos enfoques:

Modelo de refinamiento: las variables en el problema no se asignan inicialmente, y se supone que cada variable puede contener cualquier valor incluido en su rango o dominio. A medida que avanza la computación, los valores en el dominio de una variable se podan si se muestran incompatibles con los posibles valores de otras variables, hasta que se encuentre un valor único para cada variable.
Modelo de perturbación: las variables en el problema se asignan un único valor inicial. En diferentes momentos una o más variables reciben perturbaciones (cambios a su antiguo valor), y el sistema propaga el cambio tratando de asignar nuevos valores a otras variables compatibles con la perturbación.

La propagación de restricciones en problemas de satisfacción de restricciones es un ejemplo típico de un modelo de refinamiento, y las hojas de cálculo son un ejemplo típico de un modelo de perturbación.

El modelo de refinamiento es más general, ya que no restringe las variables para que tengan un solo valor, puede dar lugar a varias soluciones para el mismo problema. Sin embargo, el modelo de perturbación es más intuitivo para los programadores que usan lenguajes mixtos orientados a objetos con restricciones imperativas.

Dominios

Las restricciones que se utilizan en la programación de restricciones normalmente se aplican a algunos dominios específicos. Algunos dominios populares para la programación de restricciones son:

dominios booleanos, donde sólo se aplican restricciones verdaderas/falsas (problema SAT)
dominios enteros, dominios racionales
dominios de intervalos, en particular para la programación de problemas
dominios lineales, donde sólo se describen y analizan funciones lineales (aunque existen enfoques a problemas no lineales)
dominios finitos, donde las limitaciones se definen sobre conjuntos finitos
dominios mixtos, que implican dos o más de los anteriores

Los dominios finitos son uno de los dominios más exitosos de la programación de restricciones. En algunas áreas (como la investigación de operaciones), la programación con restricciones a menudo se identifica con la programación con restricciones sobre dominios finitos.

Propagación de restricciones

Las condiciones de coherencia local son propiedades de problemas de satisfacción de restricciones relacionadas con la consistencia de subconjuntos de variables o restricciones. Se pueden utilizar para reducir el espacio de búsqueda y hacer que el problema sea más fácil de resolver. Se aprovechan varios tipos de condiciones de coherencia local, incluida la coherencia de nodo, la coherencia de arco y la coherencia de ruta.

Cada condición de coherencia local se puede aplicar mediante una transformación que cambia el problema sin cambiar sus soluciones. Tal transformación se llama propagación de restricciones. La propagación de restricciones funciona reduciendo dominios de variables, fortaleciendo restricciones o creando otras nuevas. Esto lleva a una reducción del espacio de búsqueda, haciendo que el problema sea más fácil de resolver por algunos algoritmos. La propagación de restricciones también se puede utilizar como un verificador de insatisfacción, incompleto en general pero completo en algunos casos particulares.

Resolución de restricciones

Existen tres técnicas algorítmicas principales para resolver problemas de satisfacción de restricciones: búsqueda retroactiva, búsqueda local y programación dinámica.

Búsqueda retrospectiva

Búsqueda retrospectiva es un algoritmo general para encontrar todas (o algunas) soluciones a algunos problemas computacionales, especialmente problemas de satisfacción de restricciones, que crea candidatos para las soluciones de manera incremental y abandona un candidato ("backtracks") tan pronto como determine que el candidato posiblemente no se puede completar a una solución válida.

Búsqueda local

La búsqueda local es un método incompleto para encontrar una solución a un problema. Se basa en mejorar iterativamente una asignación de las variables hasta que se satisfagan todas las restricciones. En particular, los algoritmos de búsqueda local suelen modificar el valor de una variable en una asignación en cada paso. La nueva asignación está cerca de la anterior en el espacio de asignación, de ahí el nombre búsqueda local.

Programación dinámica

La programación dinámica es tanto un método de optimización matemática como un método de programación informática. Se refiere a simplificar un problema complicado dividiéndolo en subproblemas más simples de manera recursiva. Si bien algunos problemas de decisión no se pueden separar de esta manera, las decisiones que abarcan varios puntos en el tiempo a menudo se separan recursivamente. Del mismo modo, en informática, si un problema se puede resolver de manera óptima dividiéndolo en subproblemas y luego recursivamente encontrando las soluciones óptimas a los subproblemas, entonces se dice que tiene una subestructura óptima.

Ejemplo

La sintaxis para expresar restricciones sobre dominios finitos depende del idioma anfitrión. El siguiente es un programa de Prolog que resuelve el rompecabezas alfamético clásico ENVIAR+MÁS=DINERO en la programación lógica de restricciones:

% Este código funciona tanto en YAP como en SWI-Prolog utilizando el entorno suministrado% CLPFD biblioteca de control de restricciones. Puede requerir modificaciones menores al trabajo% en otros entornos Prolog o usando otros solvers de restricciones.:- use_module()biblioteca()clpfd)).sendmore()Digits) :- Digits = [S,E,N,D,M,O,R,Y] % Crear variables Digits ins 0,9, % Dominios asociados a variables S #= 0, % Constraint: S debe ser diferente de 0 M #= 0, all_different()Digits), % todos los elementos deben tomar diferentes valores 1000*S + 100*E + 10*N + D % Otras limitaciones + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y, etiqueta()Digits). % Iniciar la búsqueda

El intérprete crea una variable para cada letra del rompecabezas. El operador ins se utiliza para especificar los dominios de estas variables, de modo que oscilen entre el conjunto de valores {0,1,2,3,..., 9}. Las restricciones S#=0 y M#=0 significan que estas dos variables no pueden tomar el valor cero. Cuando el intérprete evalúa estas restricciones, reduce los dominios de estas dos variables quitándoles el valor 0. Entonces, se considera la restricción all_ different(Digits); no reduce ningún dominio, por lo que simplemente se almacena. La última restricción especifica que los dígitos asignados a las letras deben ser tales que "ENVIAR+MÁS=DINERO" se mantiene cuando cada letra es reemplazada por su dígito correspondiente. A partir de esta restricción, el solucionador infiere que M=1. Todas las restricciones almacenadas relacionadas con la variable M se despiertan: en este caso, la propagación de la restricción en la restricción all_ different elimina el valor 1 del dominio de todas las variables restantes. La propagación de restricciones puede resolver el problema al reducir todos los dominios a un solo valor, puede probar que el problema no tiene solución al reducir un dominio al conjunto vacío, pero también puede terminar sin probar la satisfacción o la insatisfacción. Los literales label se utilizan para realizar la búsqueda de una solución.

Contenido relacionado

Más resultados...