Листинг 14.4, Решение числового ребуса в системе CLP(FD)

% Программа решения числового ребуса 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

alldif 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. Логическое программирование в ограничениях