Описание тега clpfd

Описание тега Вопросы с тегом
CLP(FD), что означает Программирование логических ограничений в конечных доменах, реализует декларативную целочисленную арифметику в системах Prolog. Это чистая и общая замена арифметических предикатов нижнего уровня, позволяющая эффективно решать комбинаторные задачи, такие как задачи планирования, составления расписаний и распределения.

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

Почти все современные реализации Prolog включают решатель CLP(FD), который либо уже является неотъемлемой частью системы (примеры: GNU Prolog и B-Prolog), либо доступен в виде библиотеки (примеры: SICStus Prolog, SWI-Prolog, YAP)..

Основное использование ограничений CLP(FD) - вычисление целочисленных выражений. Например:

?- X #= 3+5.
X = 8.

В отличие от предикатов более низкого уровня, ограничения CLP(FD) могут использоваться во всех направлениях. Например:

?- 8 #= 3+X.
X = 5.

Ограничения CLP(FD) также могут использоваться, если конкретное значение еще не может быть выведено. Вот пример использования ограничений конечной области в SWI-Prolog после загрузкиlibrary(clpfd) (введя use_module(library(clpfd)).на интерактивном верхнем уровне). Мы просим положительные целые числаX а также Y сумма которых равна 15:

?- X + Y #= 15, X #> 0, Y #> 0.

Решатель ограничений отвечает следующим образом:

X in 1..14,
X+Y#=15,
Y in 1..14.

В этом случае решающая программа CLP(FD) пришла к выводу, что обе переменные должны быть целыми числами от 1 до 14.

При привязке одной из переменных к конкретным целым числам с помощью встроенного предиката indomain/1, решатель ограничений автоматически выводит привязку для другой переменной, чтобы все ограничения были выполнены:

?- X + Y #= 15, X #> 0, Y #> 0, indomain(X).
X = 1, Y = 14 ;
X = 2, Y = 13 ;
X = 3, Y = 12 ;
etc.

Чтобы использовать его, вам необходимо импортировать эту библиотеку (в SWI Prolog):

:- use_module(library(clpfd)).

Реализации