Расширение Prolog для использования в качестве языка логического программирования в ограничениях

Рассмотрим взаимосвязь между языком Prolog и задачей удовлетворения ограничений. Базовый Prolog сам может рассматриваться как довольно специфический язык удовлетворения ограничений, в котором все ограничения имеют весьма жесткую форму. Они представляют собой ограничения равенства между термами. Эти ограничения равенства проверяются средствами согласования термов языка Prolog.

Хотя ограничения, установленные между параметрами предикатов, также задаются в терминах других предикатов, эти вызовы предикатов в конечном итоге сводятся к согласованию. Prolog может быть расширен до "настоящего" языка CLP путем введения других типов ограничений, кроме согласования. Безусловно, должен быть также усовершенствован интерпретатор Prolog таким образом, чтобы он мог обрабатывать указанные ограничения других типов. Система CLP, способная обрабатывать арифметические ограничения равенства и неравенства, позволяет непосредственно решать задачи составления расписаний, подобные приведенным выше.

Программа с ограничениями интерпретируется примерно таким образом. Во время выполнения списка целей сопровождается множество текущих ограничений CurrConstr. Первоначально это множество является пустым. Цели в списке целей выполняются одна за другой в обычном порядке. Стандартные цели Prolog обрабатываются как обычно. При обработке цели с ограничениями Constr множества ограничений Constr и CurrConstr сливаются, в результате чего создается множество NewConstr. Затем процедура решения задач в ограничениях, предназначенная для работы с областью определения данного типа, пытается удовлетворить ограничение NewConstr. При этом возможны два основных результата: а) обнаруживается, что ограничения NewConstr удовлетворить невозможно, что соответствует недостижению цели и вызывает перебор с возвратами; б) не обнаруживается такая ситуации, что ограничения NewConstr удовлетворить невозможно, и эти ограничения максимально упрощаются процедурой решения задач в ограничениях. Например, два ограничения, X ≤ 3 и X ≤ 2, упрощаются таким образом, что вместо них вводится одно ограничение – X ≤ 2. Степень упрощения зависит от текущего состояния информации о переменных, а также от возможностей конкретной процедуры решения задач в ограничениях. Остальные цели в списке выполняются с множеством текущих ограничений, обновленным таким образом.

Системы CLP различаются по типам областей определения и типам ограничений, которые они способны обрабатывать. Семейства методов CLP упоминаются под именами в форме CLP(X), где X обозначает область определения. Например, в методах CLP(R) областями определения переменных являются действительные числа, а в качестве ограничений применяются операции проверки на равенство и неравенство, а также операции сравнения действительных чисел. К системам CLP(Z), используемым в других областях определения, относятся следующие: CLP(Z) – целые числа, CLP(Q) – рациональные числа, CLP(B) – логические области определения и CLP(FD) – задаваемые пользователем конечные области определения. Доступные области определения и типы ограничений в фактических реализациях в значительной степени зависят от существующих методов решения конкретных типов ограничений.

Например, в системах CLP(R) обычно доступны линейные равенства и неравенства, поскольку существуют эффективные методы обработки ограничений этих типов. С другой стороны, нелинейные ограничения имеют очень узкую область применения.

Вывод

• Задачи удовлетворения ограничений формулируются в терминах переменных, областей определения переменных и ограничений между переменными.

• Задачи удовлетворения ограничений часто представляются в виде сетей ограничений.

• Алгоритмы обеспечения совместимости применяются к сетям ограничений и сокращают области определения переменных.

• Логическое программирование в ограничениях (Constraint Logic Programming – CLP) представляет собой сочетание подхода, связанного с удовлетворением ограничений, и логического программирования.

• Системы CLP различаются по типам областей определения и ограничений. Системы логического программирования в ограничениях классифицируются по типам ограничений следующим образом: CLP(R) – действительные числа; CLP(Q) – рациональные числа; CLP(Z) – целые числа; CLP(FD) – конечные области определения; CLP(B) – логические значения.

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

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

• К типичным областям практического применения систем CLP относятся планирование, снабжение и управление ресурсами.

Дата добавления: 2014-01-07