Подразделы

Другие разделы

Дата и время

25/06/2026 13:46:48

Авторизация

Логическое программирование

Логическое программирование и язык Пролог Синтаксис. Операторы. Списки Сопоставление Арифметические и логические выражения Семантика программы на языке Пролог Списки. Обработка списков Предикаты для классификации и обработки термов Предикаты для управления процессом доказательства Предикаты для ввода и вывода данных Предикаты для работы с утверждениями Предикаты порождения Отладка программ на языке Пролог Примеры программ на языке Пролог Программирование в ограничениях Логика предикатов. Метод резолюции Верификация программ: основные обозначения и термины Правильность алгоритмов и способ верификации программ Синтез программ

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

GNU Prolog поддерживает *программирование в ограничениях*, когда отношения между переменными указаны в форме ограничений. Мы задаем не последовательность шагов для исполнения, а свойства искомого решения, что делает такое программирование формой декларативного программирования (как и логическое программирование).

*Finite domain (FD)* особый тип значения для неконкретизированной переменной, ограничивающий её возможные значения. Ограничение фиксирует либо диапазон целых чисел от 0 до fd_max_integer (268435455), либо множество возможных значений (по умолчанию в диапазоне 0 до 127, но можно изменить верхнюю границу).

Для установки ограничений используются предикаты сравнения ``X#=Y``, ``X#\=Y``, ``X#<Y``, ``X#>Y``, ``X#>=Y``, ``X#=<Y`` (частичные), ``X#=#Y``, ``X#\=#Y``, ``X#<#Y``, ``X#>#Y``, ``X#>=#Y``, ``X#=<#Y`` (полные), где ``X`` и ``Y`` арифметические выражения, состоящие из переменных, натуральных чисел, операций сложения (``+``), вычитания (``–``), умножения (``*``), деления без остатка (``/``), остатка от деления (``rem``), деления нацело (``//``), возведения в степень (``**``) и математических функций ``max``, ``min``, ``dist`` (модуль разности чисел).

```prolog
?-X#<1000, X rem 10#=0.
X = _#2(0..990)
?-X#<1000, X rem 10#=#0. % полное сравнение
X = _#2(0:10:20:30:40:50:60:70:80:90:100:110:120@)
```

Предикат ``fd_set_vector_max/1`` изменяет диапазон для ограничения в виде множества возможных значений:

```prolog
?-X#\=1000.
X = _#2(0..127@)
?-fd_set_vector_max(5000). % выравнивается до 5055 по размеру слова (64-бит)
yes
?-X#\=1000.
X = _#2(0..999:1001..5055@)
```

Предикат ``fd_domain/3`` ограничивает значение одной переменной или всех переменных из списка в первом аргументе диапазоном, указанном во втором и третьем аргументе. Вызов ``fd_domain(A,1,10)`` эквивалентен ``A#>=1, A#<=10``. Предикат ``fd_domain_bool/1`` ограничивает значение одной переменной или всех переменных из списка диапазоном ``[0..1]``.
Предикат ``fd_domain/2`` ограничивает значение одной переменной или всех переменных из списка в первом аргументе списком возможных значений во втором аргументе.

Предикат ``fd_prime(X)`` ограничивает значение переменной ``X`` простыми числами, а ``fd_not_prime(X)`` -- составными.

Для ограничений булевых значений можно использовать предикаты отрицания (``#\``), эквивалентно (``#<=>``), "исключающее или" (``##``, ``#\<=>``), импликация (``#==>``), "и" (``/\``), "или" (``\/``), как минимум один (``fd_at_least_one/1``), не более одного (``fd_at_most_one/1``),
ровно один (``fd_only_one/1``). Аргументом трех последних предикатов указывается список булевых переменных.

Предикат ``fd_all_different(L)`` обеспечивает, чтобы все переменные в списке ``L`` принимали различные значения.

Предикат ``fd_reified_in(X, Lower, Upper, B)`` записывает в ``B`` результат ``X in [Lower, Upper]``. Предикаты ``fd_element(I, List, X)`` и ``fd_element_var(I, List, X)`` выбирают ``I`` элемент из списка ``List`` (для первого предиката список может содержать только целые числа). Предикат ``fd_relation(List, Vars)`` выбирает один из списков в ``List`` в качестве значения для ``Vars``.

Предикат ``fd_labeling(Vars)`` выбирает конкретизацию для переменных так, чтобы они соответствовали всем ограничениям (при нажатии ``;`` можно получить другой вариант).
Для нахождения оптимального значения можно использовать в комбинации с ``fd_minimize(fd_labeling(...), X)/fd_maximize(fd_labeling(...), X)``, где ``X`` - переменная, значение которой нужно минимизировать/максимизировать

Решение числового ребуса SEND+MORE=MONEY с помощью ограничений:

```prolog
% составление арифметического выражения для числа из элементов списка
number([],R,R).
number([H|T],P,R):-number(T,P*10+H,R).
number([H|T],R):-H#>=1, number(T,H,R). % ограничение для 1-й цифры

?-L=[S,E,N,D,M,O,R,Y], fd_domain(L,0,9), % ограничение для цифр
fd_all_different(L), % все цифры различаются
number([S,E,N,D],SEND),number([M,O,R,E],MORE),number([M,O,N,E,Y],MONEY), % составление выражений
SEND+MORE#=MONEY, % головоломка
fd_labeling(L). % получение всех вариантов решения в обычных числах
```

Головоломка про зебру:

```prolog
adjacent(X, Y) :- (X #= (Y - 1)) #\/ (X #= (Y + 1)).
appendlist([],[]).
appendlist([H|T],L):-appendlist(T,R),append(H,R,L).

?- Nationalities = [English, Spanish, Ukrainian, Norwegian, Japanese],
Colors = [Red, Green, Blue, White, Yellow],
Beverages = [Tea, Coffee, Milk, Juicy, Water],
Cigarettes = [Winston, Kool, Lucky_Strike, Kent, Chesterfield],
Pets = [Dog, Snake, Fox, Horse, Zebra],

fd_domain(Nationalities,1,5), % 1
fd_domain(Colors,1,5),
fd_domain(Beverages,1,5),
fd_domain(Cigarettes,1,5),
fd_domain(Pets,1,5),

fd_all_different(Nationalities),
fd_all_different(Colors),
fd_all_different(Beverages),
fd_all_different(Cigarettes),
fd_all_different(Pets),

English #= Red, % 2
Spanish #= Dog, % 3
Green #= Coffee, % 4,
Ukrainian #= Tea, % 5
adjacent(Green, White), % 6
Winston#=Snake, % 7
Yellow #= Kool, % 8,
Milk #= 3, % 9
Norwegian #= 1, % 10
adjacent(Chesterfield, Fox), % 11
adjacent(Horse, Kool), % 12
Lucky_Strike #= Juicy, % 13
Japanese #= Kent, % 14,
adjacent(Norwegian, Blue), % 15
appendlist([Nationalities,Colors,Beverages,Cigarettes,Pets],Vars),
fd_labeling(Vars).
```

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Логическое программирование

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