Применение метода CLP для поддержки конечных областей определения - CLP(FD)

Система CLP, предназначенная для работы с конечными областями определения, реализована на основе некоторых специальных механизмов. Их работа будет показа­на а настоящем разделе на типичных примерах с использованием синтаксиса и неко­торых предикатов из библиотеки CLP(FD) версии SICStus Prolog. В данном разделе рассматривается лишь небольшое подмножество этих предикатов, которое требуется для решения приведенных здесь примеров.

В качестве областей определения переменных будут использоваться множества целых чисел. Для указания области определения переменной применяется предикат in/2, что записывается следующим образом: х in Set

В данном случае Set может быть одним из следующих.

• (lntegerl, Integer2,,,. }, Множество заданных целых чисел.

• Terml,.Term2. Множество целых чисел между Terml итегт2.

• Setl \/ Set2. Объединение множеств Set 1 и Set2.

• Setl A Set2. Пересечение множеств Setl и Set2.

• \Setl. Дополнение множества Setl.
Арифметические ограничения имеют следующую форму:

Expl Relation Ex_P2

где Expl и Ехр2 - арифметические выражения, a Relation может представлять со­бой одно из следующих.

• #=. Равно.

• #\=. Не равно.

• #<. Меньше.

• #>. Больше.

• #=<, Меньше или равно.

• #>=. Больше или равно.

В качестве примера рассмотрим следующие вопросы:

?- X in 1..5, Y in 0. Л,

X #< Y, Z #= X+Y+1.

X in l..3

Y in 2.. 4

Z in 3. .1

?- X in 1..5, X in \{4}.

X in (1..3) \/ {5}

Предикат indomair. (X) назначает с помощью перебора с возвратами возможные значения переменной X, например, следующим образом:

?- X in 1..3, indomainK). X - 1; X = 2; 5С = 3

Ниже показаны некоторые полезные предикаты, которые определены на списках переменных.

• domain! L, Min, Max]. Этот предикат означает, что все переменные в списке
L имеют области определения Min..Max,

Глава 14. Логическое программирование в ограничениях

• alldiff etent { L). Этот предикат означает, что все переменные в списке В
должны иметь разные значения.

• labeling(Options, L). Этот предикат вырабатывает возможные конкрет­
ные значения переменных в списке:_. Параметр Options представляет собой
список опций, касающихся того порядка, в каком осуществляется разметка
("labelling"; отсюда и имя предиката) переменных в списке L. Если параметр'
Options = [ ], то по умолчанию переменные размечаются слева направо; при'
этом возможные значения берутся из списка один за другим, от меньшего к
большему. Эта простейшая стратегия разметки является подходящей для всех'
примеров настоящей главы, хотя она не всегда оказывается наиболее эффек-J
тивной. Ниже приведены некоторые примеры.

?- domain ([X, Y], 1, 2), labeling{ [], [X,Y])

Х-1, У-1;

Х-1, Y-2;

Х-2, Y=l;

Х=2, Y=2

1, 2), all_different t L), labeling; [], L).

?- L - IX,Y], domain! L,

L- [1,2], X - 1, Y = 2;

L = [2, 1], X = 2, Y = 1

С помощью этих примитивов можно легко решать числовые ребусы. Рассмотрим' следующую задачу:

DONALD + GERALD

ROBERT

Каждая буква в приведенном выше ребусе должна быть заменена отличной от других десятичной цифрой таким образом, чтобы эти цифры составляли правильное арифметическое выражение. В листинге 14.4 показана программа CLP(FD) для реше­ния этой задачи. Ниже приведен запрос к этой программе.

?- solve [ N1, N2, КЗ). N1 = [5,2,6,4,8,5] N2 = [1,9,7,4,3,5] N3 = [1, 2, 3,9, 4,0]