Программирование ограничений
Программирование с ограничениями (CPP) решает проблемы типа Constraint Satisfaction (CSP). CSP — это задача моделирования в виде набора ограничений, накладываемых на переменные, причем каждая из этих переменных принимает свои значения в определенной области.
CSP определяется тройкой (X,D,C,R), такой что:
- Х={Х1,ИКС2,…,ИКСнет} набор переменных задачи;
- D функция, которая связывается с каждой переменной Xя его область определения (множество возможных значений) D(Xя);
- С=С1,ПРОТИВ2,…,ПРОТИВк} набор ограничений.
Решение с помощью программирования с ограничениями
Решение CSP состоит в присвоении значений переменным таким, чтобы все ограничения выполнялись. Для этого нам понадобится точный словарь:
- Присваивание — это экземпляр некоторой переменной по значениям их соответствующих доменов. Отметим, что A={(X1,В1),…} присваивание, которое создает экземпляр переменной X1 по значению V1, так далее;
- Присваивание называется полным, если оно конкретизирует все переменные задачи, в противном случае оно называется частичным;
- Назначение A нарушает ограничение Cк если все переменные Cк инстанцированы в A, и если отношение, определенное Cк не проверяется присваиванием:
- Полное или частичное присвоение является непротиворечивым, если оно не нарушает никаких ограничений, в противном случае оно называется несогласованным;
- Решение CSP представляет собой последовательное общее задание.
В программировании с ограничениями, когда CSP не имеет решения, говорят, что она имеет чрезмерные ограничения. В этом случае можно найти полное задание, которое нарушает наименьшее количество возможных ограничений. Затем мы говорим о max-CSP.
Другая возможность в программировании с ограничениями состоит в том, чтобы присвоить вес каждому ограничению, а затем попытаться минимизировать вес нарушенных ограничений. Затем мы говорим о VCSP (ценном). Max-CSP — это VCSP, в котором все ограничения имеют одинаковый вес.
Когда CSP допускает несколько различных решений, говорят, что он недостаточно ограничен. Если решения не все эквивалентны, то можно установить предпочтения между решениями. Мы добавляем функцию, которая связывает числовое значение с каждым решением, представляющим качество этого решения. Цель состоит в том, чтобы максимизировать эту целевую функцию. Затем мы говорим о CSOP (удовлетворение ограничений). оптимизация проблема).
Пример программирования с ограничениями: проблема n ферзей
Строителю принадлежит участок земли с 16 участками (4 ряда и 4 столбца), образующими шахматную доску. Он хочет расположить ветряки так, чтобы они не соприкасались. Две ветряные турбины находятся в сетке, если они находятся на одной линии, в одном столбце или на одной диагонали.
Программирование ограничений 1
Переменные — это расположение строк и столбцов ветряков на шахматной доске. Каждый ветряк i связан с двумя переменными Lя так далеея соответствующие соответственно строке и столбцу, на котором размещается ветряная турбина. У нас есть следующая модель программирования с ограничениями:
- Переменные:
- Х={Л1, л2, л3, л4, ПРОТИВ1, ПРОТИВ2, ПРОТИВ3, ПРОТИВ4}
- Области :
- Д(Л1)=D(L2)=D(L3)=D(L4)={1,2,3,4}
- ОКРУГ КОЛУМБИЯ1)=D(С2)=D(С3)=D(С4)={1,2,3,4}
- Ограничения:
- ПРОТИВлиния = allDiff({L1, л2, л3, л4}) для получения значений Lя все отличаются друг от друга
- ПРОТИВворотник = allDiff({С1, ПРОТИВ2, ПРОТИВ3, ПРОТИВ4}) для получения значений Cя все отличаются друг от друга
- ПРОТИВдм= {Ся+Lя != Ся+Lя / для всех i и j в {1,2,3,4} и i != j}
- ПРОТИВг= {Ся-Ля != Ся-Ля / для всех i и j в {1,2,3,4} и i != j}
- Это союз их вместе.
Такое моделирование наивно, так как все ограничения рассматриваются без поиска их смысла.
Программирование ограничений 2
Легко заметить, что на каждый столбец шахматной доски (или линию и т. д.) приходится как минимум одна ветряная турбина. Затем программирование ограничений состоит из определения, на какой строке находится ветряная турбина, расположенная в столбце i, переменная будет отмечена Xя :
- Переменные:
- Х={Х1, ИКС2, ИКС3, ИКС4}
- Области :
- Д(Х1)=D(Х2)=D(Х3)=D(Х4)={1,2,3,4}
- Ограничения:
- ПРОТИВлиния = allDiff({X1, ИКС2, ИКС3, ИКС4}) для получения значений Xя все отличаются друг от друга
- ПРОТИВдм= {Хя+ я != Хя+j / для всех i и j в {1,2,3,4} и i != j}
- ПРОТИВг= {Хя-я != Хя-j / для всех i и j в {1,2,3,4} и i != j}
- Это союз их вместе.
Обсуждение
Есть много других способов моделирования проблемы. В таком случае какая модель лучше? Для этого есть три критерия оценки актуальности моделирования: лучше ли оно моделирует проблему? Было ли моделирование тривиальным? Эффективно ли моделирование решает проблему?
Решение CSP
Решение CSP в общем случае является Np-полной задачей. Механизм разрешения состоит из повторения следующих двух шагов:
- уменьшение проблем фильтрацией;
- обход дерева поиска.
Эти два шага требуют таких понятий, как непротиворечивость дуг или распространение ограничений, которые мы не будем развивать в этом курсе. Существует множество решателей CSP, таких как библиотека Google OR-tools.
RU 
FR 
EN 
ES