Здесь tj и Lj описывают элементы агрегатора: tj – терм, Lj – литерал. Если литерал пустой, а терм не пустой, то двоеточие не используется. Func – имя функции, которая будет применена к термам. Функция может отсутствовать. Ограничения «s1 <1» и «<2 s2» могут отсутствовать. При этом «<1» и «<2» по умолчанию означают «<=». Значения «s1» и «s2» определяют нижнюю и верхнюю границы.
Поддерживаемые функции: #count (количество атомов в группе), #sum (сумма значений всех термов), #sum+ (сумма всех положительных значений термов-весов), #min (минимальное значение термов-весов), #max (максимальное значение термов-весов).
В результате использования агрегатора формируется набор ответов, соответствующий заданным условиям:
10 #sum{8: course(db); 4: course(web); 6:
course(ai)}.
Результаты:
Answer: 1 course(db) course(web)
Answer: 2 course(ai) course(web) course(db) Answer: 3 course(ai) course(db)
Answer: 4 course(ai) course(web)
Вычисление сумм при этом происходит при использовании следующих значений: 10 <= #sum{8; 4; 6}. Во всех случаях сумма весов получалась больше либо равна 10. Исключим равенство суммы термов-весов 10.
10 < #sum{8: course(db); 4: course(web); 6:
course(ai)}.
При этом в наборе ответов встретятся только первые три ответа. Рассмотрим пример для #count:
2 #count{1: course(db); 2: course(web); 3:
course(ai)} 2.
Результаты:
Answer: 1 course(web) course(db)
Answer: 2 course(ai) course(web)
Answer: 3 course(ai) course(db)
Вприведённом примере количество атомов в ответе должно быть равно
2.То же самое можно записать следующим образом:
#count{1: course(db); 2: course(web); 3: course(ai)}
= 2.
11
Вычисление при этом представляет собой определение количества
#count{1; 2; 3} = 2.
Рассмотренные варианты агрегаторов могут использоваться как в голове, так и в теле правил:
a.
cnt(X) :- X = #count{ -2 : a; 3 : a }. sum(X) :- X = #sum { -2 : a; 3 : a }. pos(X) :- X = #sum+{ -2 : a; 3 : a }. min(X) :- X = #min { -2 : a; 3 : a }.
max(X) :- X = #max { -2 : a; 3 : a }.
Результат наглядно демонстрирует применение функций:
Answer: 1 a cnt(2) sum(1) pos(3) min(-2) max(3)
Рассмотрим программу с суммированием:
#sum{ 3 : cost(1,2,3); 3 : cost(2,3,3) } = 3.
Её результаты:
Answer: 1 cost(1,2,3)
Answer: 2 cost(2,3,3)
Answer: 3 cost(2,3,3) cost(1,2,3)
Следует отметить, что использованы одинаковые термы-веса, в то же время ASP ожидает, что они будут уникальны, именно поэтому в результате появился ответ № 3. Эту программу можно изменить следующим образом.
#sum{ 3,a : cost(1,2,3); 3,b : cost(2,3,3) } = 3.
Тогда результат будет следующий:
Answer: 1 cost(1,2,3)
Answer: 2 cost(2,3,3)
В данном случае получились уникальные термы 3,a и 3,b, а суммирование выполняется только по первым числам.
Использование сокращений
Если необходимо задать ограничение на количество результирующих атомов, допустима запись, в которой опущено указание на функцию #count и не приводятся термы-веса:
{course(db); course(web); course(ai)} = 2.
Результат:
Answer: 1 course(web) course(db)
Answer: 2 course(ai) course(web)
12
Answer: 3 course(ai) course(db)
Атомы, сгенерированные агрегаторами, могут отфильтровываться с помощью ограничений целостности:
{course(db); course(web); course(ai)} = 2.
:- course(web).
Результат:
Answer: 1 course(db) course(ai)
Рассмотрим программу «сваха»:
male(tom;alex). female(mary;liza). {couple(X, Y)} :- male(X), female(Y). :- couple(X, Y), couple(X, Z), Y != Z.
:- couple(X, Y), couple(Z, Y), X != Z.
В предложенной программе первая строка задаёт перечень представителей мужского и женского пола. Вторая строка с использованием агрегатора описывает все возможные супружеские пары. Ограничения целостности в третьей и четвёртой строке – запрещают многоженство и многомужество. Результаты:
Answer: 1 ...
Answer: 2 ... couple(alex,mary)
Answer: 3 ... couple(tom,liza)
Answer: 4 ... couple(alex,mary) couple(tom,liza) Answer: 5 ... couple(alex,liza)
Answer: 6 ... couple(tom,mary)
Answer: 7 ... couple(tom,mary) couple(alex,liza)
Приведённый пример демонстрирует следующие особенности использования механизма агрегаторов в ASP.
1.Использование агрегаторов в голове правила. При этом генерируются значения, но нет возможности задать нижнюю и верхнюю границы или использовать функции.
2.Создание с использованием агрегатора новых фактов в программе.
3.Исключение с использованием ограничений целостности результатов, созданных агрегатором, но не удовлетворяющим данному ограничению.
1.7. Оптимизация
Использование оптимизации позволяет не просто найти набор ответов, а найти оптимальный набор ответов. Предусмотрена линейная оптимизация с
13
получением минимальных (#minimize) и максимальных (#maximize) значений оптимизируемого параметра:
#minimize{w1@p1,t1 : L1, ... , wn@pn,tn : Ln}
В данном описании @pj – приоритет (необязательное значение), wj – вес, который будет минимизироваться среди истинных литералов Lj
(1 ≤ j ≤ n).
Оптимизацию называют мягким ограничением. Для решения задачи минимизации существует альтернативная запись.
: ~noisy. [ 1@3 ]
#minimize { 1@3 : noisy }.
Приведённые две записи с точки зрения ASP полностью идентичны. Рассмотрим следующую программу.
{ hotel(1..5) } = 1. star(1,5). cost(1,170). star(2,4). cost(2,140). star(3,3). cost(3,90).
star(4,3). cost(4,75). main_street(4). star(5,2). cost(5,60).
noisy :- hotel(X), main_street(X). #maximize{Y@1,X : hotel(X), star(X,Y)}.
#minimize{Y/Z@2,X : hotel(X), cost(X,Y), star(X,Z)}.
#minimize{1@3 : noisy}.
Дано пять отелей, определена их «звёздность», стоимость и шумность. Последнее ограничение говорит, что не нужен шумный отель. В первую очередь требуется максимизировать звёздность, во вторую – минимизировать отношение стоимости на звездность. Из программы видно, что под требование минимизации подходят два отеля № 3 и № 5, но у отеля № 3 выше «звёздность». Результат:
Answer: 1 ... hotel(1)
Optimization: 0 34 12
Answer: 2 ... hotel(3)
Optimization: 0 30 14
OPTIMUM FOUND
14
1.8. Дополнительные возможности ASP
Комментарии начинаются с символа «%», для многострочных комментариев используется символ открытия «%*» и символ закрытия «*%» комментариев.
Директива #show ограничивает результаты вывода. Для примера с отелями (раздел 1.7):
#show hotel/1.
При использовании данной директивы в качестве результата будут вы-
ведены только hotel(1) и hotel(3).
Директива #const позволяет задавать константы, которые могут изменяться в командной строке:
#const x = 42.
#const y = f(x,z).
p(x,y).
Результат:
p(42,f(42,z))
Замена константы:
clingo.exe --text -c x="2+2*2" -c z=7 1.lp
Результат:
p(6,f(6,7)).
Рассмотрим вычисление чисел Фибоначчи: x(n) = x(n-1) + x(n-2).
#const n=4. num(1..n).
fib(0, 1). fib(1, 1).
fib(N, X1 + X2) :- num(N), N > 1, fib(N - 1, X1), fib(N - 2, X2).
#show fib/2.
Результат:
fib(0,1) fib(1,1) fib(2,2) fib(3,3) fib(4,5)
1.9.Упражнения
1.Задан набор фактов, описывающих числа:
#const n = 5.
4{num(1..n)}.
15