En la investigación de la satisfacción de restricciones en inteligencia artificial y la investigación de operaciones , los gráficos de restricciones y los hipergráficos se utilizan para representar las relaciones entre las restricciones en un problema de satisfacción de restricciones . Un gráfico de restricción es un caso especial de un gráfico de factores , que permite la existencia de variables libres.
Hipergrafo de restricción
El hipergráfico de restricción de un problema de satisfacción de restricción es un hipergrama en el que los vértices corresponden a las variables y los hipergrafos corresponden a las restricciones. Un conjunto de vértices forma un hipermercado si las variables correspondientes son las que ocurren en alguna restricción. [1]
Una forma sencilla de representar el hipergrama de restricción es mediante el uso de un gráfico clásico con las siguientes propiedades:
- Los vértices corresponden a variables o restricciones,
- un borde solo puede conectar un vértice variable a un vértice de restricción, y
- hay un borde entre un vértice-variable y un vértice-restricción si y solo si la variable correspondiente ocurre en la restricción correspondiente.
Las propiedades 1 y 2 definen un gráfico bipartito . El hipergrafo se recupera definiendo los vértices como los vértices variables y los hipergrafos como los conjuntos de vértices variables conectados a cada vértice de restricción.
Gráfico de restricción primaria
La gráfica de restricción primaria o simplemente gráfica primaria (también la gráfica de Gaifman ) de un problema de satisfacción de restricción es la gráfica cuyos nodos son las variables del problema y un borde une un par de variables si las dos variables ocurren juntas en una restricción. [1]
El gráfico de restricción principal es de hecho el gráfico principal del hipergráfico de restricción.
Gráfico de restricción dual
El conjunto de variables involucradas en una restricción se denomina alcance de restricción . El gráfico de restricción dual es el gráfico en el que los vértices son todos los ámbitos de restricción involucrados en las restricciones del problema, y dos vértices están conectados por una arista si los ámbitos correspondientes tienen variables comunes. [1]
Referencias
- ^ a b c Manual de programación de restricciones , por Francesca Rossi, Peter Van Beek, Toby Walsh (2006) ISBN 0-444-52726-5 , p. 211, 212