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

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

Гиперграф ограничения

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

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

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

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

Граф первичных ограничений

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

Граф прямых ограничений на самом деле прямой граф гиперграфа ограничений.

Граф двойных ограничений

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

использованная литература