% Программа решения числового ребуса DONALD+GERALD=ROBERT средствами CLP(FD)
solve С [D, О,H,A, L,D], [G, E,R,A,L,D], [R, 0, В, E, R, Г]):-
Vars =,0,N,A,L,G,E,R,B,T], % Переменные, необходимые для решения задачи
| domain [ Vars, 0, 9), all_dif ferent I Vars), 1000C0*D + 10000*0 + 100D00*G + 10000*E + 100000*R + 10000*0 + labeling £ [], Vars). |
| % % |
Все эти переменные обозначают- десятичные цифры Все эти переменные - разные
1000*N + 100*A + 10*L + D + 1000*R + 100*A + 10*L + D # = 1000*B + 1D0*E + 10*R + T,
В листинге 14.5 приведена программа CLP(FD) для решения знакомой задачи с восемью ферзями. В качестве указания по составлению подобных программ следует отметить, что обе программы (и для решения числовых ребусов, и для решения задачи с восемью ферзями) имеют следующую основную структуру: вначале задаются области определения переменных, затем налагаются определенные ограничения и в конечном итоге предикат разметки находит конкретные решения. Это — обычная структура программ CLP(FD),
Часть II. Применение языка Prolog в области искусственного интеллекта
Листинг 14,5. Программа CLP(FO) для задачи с восемью ферзями
% Программа решения задачи с восемью ферзями средствами CLP(FD)
solution С Ys);- % Ys - список координат Y ферзей
Ys = [_,_,_,_, _г _,_,_], * Количество ферзей равно 8
domain (Ys, 1, В), % Все координаты имеют область определения 1..8
all dif ferent! Ys), % Все координаты - разные, что позволяет
% предотвратить взаимные нападения по горизонтали
safe! Ys), % Ограничение, с помощью которого предотвращаются
% нападения по диагонали
labeling! [J, Ys). I Найти конкретные значения для Ys
safe С П) ■
safe! [Y | Ys]):-
no attack (Y, Ys, 1), 4 1 - расстояние по горизонтали между ферзем Y
% и ферзями из списка Ys
safet Ys).
% no_attack(Y, Ys, D):
% ферзь, который определен переменной Y, не нападает ни на одного из ферзей
h в списке Ys;
I D - расстояние по горизонтали между первым ферзем и остальными ферзями
no_attack(Y, [],_).
no_attack(Yl, [Y2 | Ys], D):-D #\= Y1-Y2, D #\=Y2-Yl, Dl is D+l, no_attack(Yl, Ys, Dl).
Наконец, рассмотрим процедуру решения с помощью системы CLP(FD) задач оптимизации, таких как минимизация времени завершения при составлении расписаний. Для решения задач оптимизации удобно применять следующие встроенные предикаты CLP(FD): minimize! Goal, X) и maximize; Goal, X)
Эти предикаты находят такое решение Goal, которое минимизирует (максимизирует) значение X. Как правило, Goal - это цель предиката indomain или предиката разметки, например, как показано ниже.
?- х in 1..20, V # = X*(20-Х), maximize (indomain (X), V), X = 1 0, V = 100
Простую задачу планирования (см. рис. 14.1) можно решить с помощью следующего запроса:
?.- StartTimes = [Та, ТЬ, Тс, Td,Tf ], % Tf - время завершения domain< StartTimes, 0, 20), Та #>= 0,
Та + 2#=<ТЬ, % Задание а предшествует заданию Ь
Та + 2#=<Тс, % Задание а предшествует заданию с
ТЬ + 3 #=< Td, % Задание b предшествует заданию d
Тс + 5#=<Tf, % Задание с завершается ко времени завершения Tf
Td + 4 #=< Tf,
minimize! labeling([ ], StartTiraes], Tf).
StartTimes = [0,2,2,5,9]
В данном случае вырабатывается только одно оптимальное решение.
Глава 14. Логическое программирование в ограничениях
