% Назначаем произвольный цвет каждому узлу (стране)
1 {color(X, C) : colors(C) } 1 :- countries(X). % Соседние страны (узлы) не могут иметь один цвет
:- color(X1, C), color(X2, C), neighbour(X1,X2). % Удаление симметричных решений
:- color(germany, red).
:- color(france, red).
#show color/2.
В результате будет получено 4 набора ответов следующего вида:
color(belgium,red) color(netherlands,green)
color(france,green) color(germany,blue)
color(denmark,red)
Следует отметить, что ограничения целостности, удаляющие симметричные решения, не являются обязательными. Без их использования получается 12 симметричных решений.
2.4. Задача о максимальной клике
Кликой в графе называется набор узлов, в которых есть дуга между каждой парой узлов. Задача о максимальной клике подразумевает поиск в графе клики максимального размера.
% Исходные данные с двумя кликами (1,2,4) and (3, 5)
edge(1, (1;2;4)). edge(2, (1;2;4)).
edge(4, (1;2;4)). edge(3, (3;5)). edge(5, (3;5)). % Вершина графа node
node(X) :- edge(X,Y).
node(Y) :- edge(X,Y).
% Минимальный размер клики
#const n = 2.
% in - входит в клику (с учётом минимума n)
n {in(X) : node(X)}. % Критерии клики
:- in(X), in(Y), node(X), node(Y), X!=Y, not
edge(X,Y), not edge(Y,X).
% Поиск максимальной клики
#maximize { 1,X : in(X), node(X)}.
#show in/1.
21
В результате будет следующий набор ответов:
Answer: 1 in(3) in(5)
Optimization: -2
Answer: 2 in(1) in(2) in(4)
Optimization: -3
OPTIMUM FOUND
2.5.Судоку
Взадаче судоку дано поле 9×9, которое поделено на 9 групп клеток 3×3.
Вкаждую клетку может быть записана цифра от 1 до 9. При этом должны выполняться условия: каждая цифра должна ровно один раз встретиться в каждой строке, в каждом столбце и в каждой группе клеток. Первоначально в судоку заполнены часть клеток цифрами.
% Исходные данные для задачи x(1, 4, 7). x(1, 5, 9).
x(2, 3, 5). x(2, 4, 8). x(2, 6, 1). x(2, 7, 6). x(2, 8, 7).
x(3, 1, 3). x(3, 6, 6).
x(4, 2, 9). x(4, 3, 3). x(4, 5, 6). x(4, 7, 5). x(5, 1, 6). x(5, 6, 5). x(5, 7, 3). x(5, 9, 1). x(6, 6, 9). x(6, 9, 4).
x(7, 1, 7). x(7, 4, 1). x(7, 6, 3). x(7, 7, 8). x(9, 4, 6). x(9, 6, 8).
% Значения, которые могут записываться в клетки val(1..9).
% Границы групп клеток border(1;4;7).
% Проверка уникальности цифр в группе клеток
1 { x(X,Y,N) : val(X), val(Y), X1<=X, X<=X1+2, Y1<=Y, Y<=Y1+2 } 1 :- val(N), border(X1), border(Y1).
% Проверка уникальности цифр по строкам и столбцам
1 { x(X,Y,N) : val(N) } 1 :- val(X), val(Y). 1 { x(X,Y,N) : val(X) } 1 :- val(N), val(Y). 1 { x(X,Y,N) : val(Y) } 1 :- val(N), val(X).
%Альтернативы
%:- 2 { x(X,Y,N) : val(N) }, val(X), val(Y).
22
%:- 2 { x(X,Y,N) : val(X) }, val(N), val(Y).
%:- 2 { x(X,Y,N) : val(Y) }, val(N), val(X).
В результате получается один набор ответов.
2.6.Упражнения
1.Напишите программу вычисления чисел Фибоначчи: x(n) = x(n-1) + x(n-2). Вычислите сумму всех чётных элементов, не превышающих 1 миллион.
2.У посетителя ресторана 1505 рублей. Стоимости блюд заданы следующими фактами:
price(mixed_fruit,215). price(french_fries,275). price(side_salad,335). price(mozzarella_sticks,420).
price(samples_place,580). price(host_wings,355).
Необходимо написать программу, которая позволит купить блюда ровно на имеющуюся сумму.
3.Напишите программу, которая вычислит, какое наименьшее количество монет нужно, чтобы можно было оплатить любую одну покупку стоимостью до 1 рубля? Доступные монеты 1, 2, 5, 10, 20 и 50 копеек.
4.Если сложить все числа меньшие 10, которые без остатка делятся на 3
ина 7, то получится 25 (числа 3, 6, 9 и 7). Напишите программу, которая вычислит сумму всех чисел, которые без остатка делятся на 3 и на 7, меньшие
500.
5.Напишите программу, которая восстановит номер телефона, если да-
ны четыре номера: (946) 215 78 30, (860) 439 12 57, (164) 029 78 53, (682) 431 90 75. Известно, что в каждом из них четыре цифры стоят на правильных местах.
6.В вечеринке участвовали Betty, Chris, Donald, Fred, Gary, Mary и Paul,
они хотят сфотографироваться и у них есть следующие предпочтения:
– Betty хочет стоять рядом с Gary и Mary;
– Chris хочет стоять рядом с Betty и Gary;
– Fred хочет стоять рядом с Mary и Donald;
– Paul хочет стоять рядом с Fred и Donald.
Все ограничения не могут быть одновременно удовлетворены. Необходимо найти решение, которое максимизирует количество удовлетворённых ограничений.
23
7. В банк привезли несколько сумок с золотыми монетами. В сумках было 16, 17, 23, 24, 39 и 40 монет. Грабители украли несколько сумок. В сумме недосчитались 100 золотых монет. Необходимо написать программу, которая вычислит, сколько сумок было украдено.
3. Программирование с использованием ограничений
3.1. Использование ограничений в ASP
Программирование с использованием технологии ограничений реализовано в clingcon. ASP поддерживает только линейные ограничения. Для подключения вычислений с использованием ограничений необходимо включить модуль csp командой #include <csp>.
Ограничение на пространство значений задаются с использованием директивы &dom, при этом вывод результатов осуществляется с помощью &show. Важно, что дополнительные директивы clingcon принимают параметры не в круглых, а в фигурных скобках.
Минимальная программа может выглядеть следующим образом:
#include <csp>.
&dom {2..4;8} = x.
&show {x}.
Получаются следующие наборы ответов:
Answer: 1 x=8
Answer: 2 x=4
Answer: 3 x=3
Answer: 4 x=2
Вданном случае было сгенерировано необходимое количество термов x
сзаданными значениями. Можно добавить ограничения на результат сумми-
рования с помощью &sum:
#include <csp>.
&dom {2..4;8} = x.
&sum {x} > 3.
&show {x}.
Результирующие наборы ответов:
Answer: 1 x=8
Answer: 2 x=4
Или для нескольких значений:
24
#include <csp>.
&dom {2..4;8} = x.
&sum {x;(-1)} > 3.
&show {x}.
После вычитания единицы только одно значение больше 3:
Answer: 1 x=8
В данном случае &sum – линейное ограничение, которое поддерживает следующие сравнения: <=,=,>=,<,>,!=. При задании ограничений возможно использование фактов программы.
#include <csp>. v(a,4).
v(b,5).
&dom {2..M} = x(I) :- v(I,M). &sum {x(a);x(b)} > 7.
&show {x(a);x(b)}.
Результирующие наборы ответов.
Answer: 1 v(a,4) v(b,5) x(a)=4 x(b)=5
Answer: 2 v(a,4) v(b,5) x(a)=4 x(b)=4
Answer: 3 v(a,4) v(b,5) x(a)=3 x(b)=5
Присваивание значений из заданного домена осуществляется в данном примере, в котором использован составной терм, а ограничение максимального значения задаётся вторым параметром факта v.
Дополнительно к линейным ограничениям в следующем примере предусмотрена директива для минимизации &minimize.
#include <csp>. v(a,4).
v(b,5).
&dom {2..M} = x(I) :- v(I,M). &dom {2..M*2} = h :- v(I,M). &sum {x(a);x(b)} > h. &minimize {-h}.
&show {x(a);x(b);h}.
Результирующие наборы ответов.
Answer: 1 v(a,4) v(b,5) x(a)=4 x(b)=5 h=8
Optimization: -8
OPTIMUM FOUND
25