Главная arrow Логика arrow Программирование в ограничениях
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Программирование в ограничениях Печать

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

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

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

triangle(X,Y,Z) :-

X>=0, Y>=0, Z>=0, X+Y>=Z, Y+Z>=X, X+Z>=Y.

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

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

Системы CLP включают различные алгоритмы решения задач с ограничениями

для таких вариантов ограничений, которые разрешены к использованию в языке. Например, система, позволяющая использовать линейные неравенства с переменными, имеющими вещественные значения, может включать алгоритм линейного программирования для решения этих ограничений. Кроме того, в системах CLP принят гораздо более гибкий подход к решению запросов стандартного логического программирования. Например, вместо использования поиска в глубину, слева направо, с возвратами, в них может применяться любой из более эффективных алгоритмов, включая эвристическое упорядочение конъюнктов, обратный переход, определение условий формирования множества отсечения и т.д. Поэтому в системах CLP сочетаются элементы алгоритмов удовлетворения ограничений, логического программирования и дедуктивных баз данных.

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