График ограничений
В удовлетворения ограничений исследованиях в области искусственного интеллекта и операций исследованиях графы и гиперграфы ограничений используются для представления отношений между ограничениями в задаче удовлетворения ограничений . Граф ограничений — это частный случай факторного графа , который допускает существование свободных переменных.
Гиперграф ограничений
[ редактировать ]Гиперграф ограничений задачи удовлетворения ограничений — это гиперграф , в котором вершины соответствуют переменным, а гиперребра соответствуют ограничениям. Набор вершин образует гиперребро, если соответствующие переменные входят в некоторое ограничение. [1]
Простой способ представить гиперграф ограничений — использовать классический граф со следующими свойствами:
- Вершины соответствуют либо переменным, либо ограничениям.
- ребро может соединять только вершину-переменную с вершиной-ограничением, и
- существует ребро между вершиной-переменной и вершиной-ограничением тогда и только тогда, когда соответствующая переменная встречается в соответствующем ограничении.
Свойства 1 и 2 определяют двудольный граф . Гиперграф восстанавливается путем определения вершин как вершин-переменных, а гиперребер - как наборов вершин-переменных, связанных с каждой вершиной-ограничением.
Первичный граф ограничений
[ редактировать ]Первичный граф ограничений или просто первичный граф (также граф Гейфмана ) задачи удовлетворения ограничений — это граф , узлами которого являются переменные задачи, а ребро соединяет пару переменных, если две переменные встречаются вместе в ограничении. [1]
Первичный граф ограничений на самом деле является первичным графом гиперграфа ограничений.
Граф двойных ограничений
[ редактировать ]Набор переменных, участвующих в ограничении, называется областью ограничения . Граф двойных ограничений — это граф, вершинами которого являются все области ограничений, участвующие в ограничениях задачи, а две вершины соединены ребром, если соответствующие области имеют общие переменные. [1]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Справочник по программированию с ограничениями , Франческа Росси , Питер Ван Бик, Тоби Уолш (2006) ISBN 0-444-52726-5 , с. 211, 212