Главная arrow книги arrow Копия Глава 9. Логический вывод в логике первого п arrow Логическое программирование в ограничениях
Логическое программирование в ограничениях

В приведенном выше описании прямого логического вывода (раздел 9.3) было показано, как можно представить задачи удовлетворения ограничений (Constraint Satisfaction Problem— CSP) в виде определенных выражений. Стандартный язык Prolog позволяет решать подобные задачи точно таким же способом, как и алгоритм поиска с возвратами, приведенный в листинге 5.1.

Поскольку поиск с возвратами предусматривает полный перебор областей определения переменных, он может применяться только для решения задач CSP с конечными областями определения. В терминах Prolog это можно перефразировать таким образом, что для любой цели с несвязанными переменными должно существовать конечное количество решений. (Например, цель diff (q, sa), которая определяет, что штаты Квинсленд и Южная Австралия должны быть окрашены в разные цвета, имеет шесть решений, если допускается применение трех цветов.) Задачи CSP с бесконечными областями определения (например, с целочисленными или вещественными переменными) требуют применения совсем других алгоритмов, таких как распространение пределов или линейное программирование.

Приведенное ниже выражение выполняется успешно, если подставленные в него три числа удовлетворяют неравенству треугольника.

Если системе Prolog передан запрос triangle (3 , 4, 5), он будет выполнен безукоризненно. С другой стороны, после передачи запроса triangle (3 , 4, Ζ) решение не будет найдено, поскольку подцель Z>=0 не может быть обработана системой Prolog. Возникающая при этом сложность состоит в том, что переменные в системе Prolog должны находиться только в одном из двух состояний: несвязанные или связанные с конкретным термом.

Связывание переменной с конкретным термом может рассматриваться как крайняя форма ограничения, а именно как ограничение равенства. Логическое программирование в ограничениях (Constraint Logic Programming — CLP) позволяет ограничивать, а не связывать переменные. Решением для программы в логике ограничений является наиболее конкретное множество ограничений, налагаемых на переменные запроса, которое может быть определено с помощью базы знаний. Например, решением запроса triangle (3, 4, Ζ) является ограничение. Программы в стандартной логике представляют собой частный случай программ CLP, в которых ограничения решения должны быть не ограничениями сравнения, а ограничениями равенства, т.е. связываниями.