График ограничений

В ограничении удовлетворенности исследований в области искусственного интеллекта и исследование операций , ограничения графики и гиперграфы используются для обозначения отношений между ограничениями в задаче удовлетворения ограничений . Ограничение граф является частным случаем из фактор - графа , что позволяет наличие свободных переменных.

Гиперграф ограничения [ править ]

Ограничение Гиперграф проблемы удовлетворения ограничений является гиперграфом , в котором вершины соответствуют переменным, а гиперребра соответствует ограничениям. Набор вершин образует гиперребро, если соответствующие переменные встречаются в некотором ограничении. ^[1]

Простой способ представить гиперграф ограничений - использовать классический граф со следующими свойствами:

1. Вершины соответствуют либо переменным, либо ограничениям,
2. ребро может только соединять переменную вершину с вершиной ограничения, и
3. существует ребро между вершиной переменной и вершиной ограничения тогда и только тогда, когда соответствующая переменная встречается в соответствующем ограничении.

Свойства 1 и 2 определяют двудольный граф . Гиперграф восстанавливается путем определения вершин как переменных-вершин и гиперребер как наборов переменных-вершин, связанных с каждой ограничивающей вершиной.

Граф первичных ограничений [ править ]

Граф прямого ограничения или просто простой граф (также граф Гайфмана ) проблемы удовлетворения ограничений - это граф , узлы которого являются переменными задачи, а ребро соединяет пару переменных, если эти две переменные встречаются вместе в ограничении. ^[1]

Граф прямого ограничения фактически является прямым графом гиперграфа ограничений.

Граф двойного ограничения [ править ]

Набор переменных, участвующих в ограничении, называется областью ограничения . Граф двойных ограничений - это граф, в котором все вершины являются областями ограничений, участвующими в ограничениях задачи, а две вершины соединены ребром, если соответствующие области имеют общие переменные. ^[1]

Ссылки [ править ]