Дополните программу таким образом, чтобы был только один набор ответов, в котором игнорируется число 2. Единственный набор ответов для n=5:
num(1) num(3) num(4) num(5)
2. Задан набор фактов, описывающих генеалогическое дерево:
person(tom; bob; alex; liza; sam; mary; lucy).
parent(tom,(bob;alex)). parent(bob,(liza;sam)).
parent(sam,(mary;lucy)).
male(tom;bob;alex;sam).
female(liza;mary;lucy).
Напишите программу «есть сестра», которая отобразит только тех, у кого есть сестра. Правильный ответ для приведённой программы:
havesister(sam) havesister(lucy) havesister(mary)
3. Для набора фактов, описывающих генеалогическое дерево из упражнения (2):
Напишите программу «есть тетя», которая отобразит только тех, у кого есть тетя. Правильный ответ для программы из упражнения (2):
haveaunt(mary) haveaunt(lucy)
4. Дан набор фактов для вычисления факториала: x(n) = x(n-1) * n.
#const n=5.
num(1..n). fact(1, 1).
#show fact/2.
Необходимо дополнить программу, чтобы она вычисляла факториал. Единственный набор ответов для n=5:
fact(1,1) fact(2,2) fact(3,6) fact(4,24) fact(5,120)
5. Дан набор фактов, описывающих числа:
#const n = 12.
num(2..n).
#show prime/1.
Необходимо дополнить программу, чтобы в наборе ответов были только простые числа, меньшие n. Единственный набор ответов для n=12:
prime(2) prime(3) prime(5) prime(7) prime(11)
6. Дан набор фактов, описывающих числа:
#const n = 30.
num(2..n).
16
#show prime6/2.
Необходимо дополнить программу, чтобы в наборе ответов были только пары простых чисел X и Y, меньшие n, отличающиеся на 6. Единственный набор ответов для n=30:
prime6(5,11) prime6(7,13) prime6(11,17)
prime6(13,19) prime6(17,23) prime6(23,29)
7. Задан набор фактов, описывающих решетку 5 на 5:
#const n = 5.
1 { grid(1..n, 1..n) } n*n.
Напишите программу, которая сформирует маршрут из позиции grid(1,1) в grid(5,5). Пример правильного ответа:
move(1,1) move(2,1) move(3,1) move(4,1) move(4,2)
move(4,3) move(4,4) move(4,5) move(5,5)
Для упрощения решения можете исключить из ответа move(1,1) и/или move(5,5).
2.Подходы к решению задач
2.1.Задача о расстановке ферзей
Шахматная фигура ферзь бьёт по горизонтали, по вертикали и по обеим диагоналям. В классической постановке задачи о расстановке ферзей необходимо на доске 8×8 расставить 8 ферзей так, чтобы они не били друг друга. Эта задача может решаться для доски размера n×n.
#const n = 8.
{ queen(1..n,1..n) }. :- { queen(I,J) } != n.
:- queen(I,J), queen(I,X), J != X. :- queen(I,J), queen(X,J), I != X.
:- queen(I,J), queen(X,Y), (I,J) != (X,Y), I-J == X-
Y.
:- queen(I,J), queen(X,Y), (I,J) != (X,Y), I+J == X+Y.
В программе строка 1 – размер доски 8×8. Строка 2 – все возможные варианты расстановки ферзей. Строка 3 – количество ответов равно 8. Строки 4
и5 – запрет нахождения ферзей на одной вертикали и горизонтали. Строки 6
и7 – запрет нахождения на одной диагонали.
17
В результате получается 92 набора ответов следующего вида:
queen(5,1) queen(2,2) queen(4,3) queen(6,4) queen(8,5) queen(3,6) queen(1,7) queen(7,8)
queen(5,1) queen(7,2) queen(4,3) queen(1,4)
queen(3,5) queen(8,6) queen(6,7) queen(2,8)
Возможен другой вариант решения задачи о расстановке ферзей:
#const n = 8. number(1..n).
1 { queen(X,Y) : number(Y) } 1 :- number(X). { queen(1..n,Y) } = 1 :- Y = 1..n.
:- queen(I,J), queen(X,Y), I < X, J+I == Y+X. :- queen(I,J), queen(X,Y), I < X, J-I == Y-X. #show queen/2.
Впрограмме строка 1 – размер доски 8×8. Строка 2 – определение набора чисел от 1 до n. Строки 3 и 4 идентичны друг другу и задают все варианты размещения ферзей на шахматной доске. Строки 5 и 6 обеспечивают запрет нахождения ферзей на одной диагонали, вертикали или горизонтали.
Врезультате получаем 92 ответа следующего вида:
queen(1,4) queen(2,6) queen(3,8) queen(4,2)
queen(5,7) queen(6,1) queen(7,3) queen(8,5)
Программа может быть сокращена. Альтернативный вариант решения:
#const n = 8.
{queen(I,1..n) } = 1 :- I = 1..n.
{queen(1..n,J) } = 1 :- J = 1..n.
:- { queen(D-X,X) } > 1, D = 2..2*n.
:- { queen(D+Y,Y) } > 1, D = 1-n..n-1.
В результате получаем 92 ответа следующего вида:
queen(2,2) queen(5,1) queen(4,3) queen(1,7)
queen(3,6) queen(6,4) queen(8,5) queen(7,8)
2.2.Задача коммивояжера
Взадаче коммивояжера дан направленный взвешенный граф, и необходимо найти маршрут через все вершины с минимальным весом.
%* Дан взвешенный граф (cost). Первый параметр – начальная вершина дуги, второй параметр – конечная вершина дуги, третий параметр – вес. *%
18
cost(1,2,2). cost(1,3,3). cost(1,4,1).
cost(2,4,2). cost(2,5,2). cost(2,6,4).
cost(3,1,3). cost(3,4,2). cost(3,5,2).
cost(4,1,1). cost(4,2,2).
cost(5,3,2). cost(5,4,2). cost(5,6,1).
cost(6,2,4). cost(6,3,3). cost(6,5,1).
% Дуга описывается edge (см. параметры cost)
edge(X,Y) :- cost(X,Y,_).
% Узел node – первый либо второй параметр cost
node(X) :- cost(X,_,_). node(Y) :- cost(_,Y,_). % Поиск циклов
{cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
%* Должен быть ровно один цикл по всем вершинам. Без ограничения целостности может получиться не-
сколько циклов. *%
reached(Y) :- cycle(1,Y).
reached(Y) :- cycle(X,Y), reached(X).
:- node(Y), not reached(Y). % Поиск минимального решения
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
#show cycle/2.
В результате находится один набор ответов, обеспечивающий вес пути, равный 11.
Answer: 1 cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,6) cycle(6,5) cycle(5,3)
Optimization: 13
Answer: 2 cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 12
Answer: 3 cycle(1,2) cycle(4,1) cycle(3,4) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 11
OPTIMUM FOUND
19
2.3.Задача о раскрашивании графа
Взадаче о раскрашивании графа предлагается назначить цвета узлам графа таким образом, чтобы смежные вершины имели разные цвета. Возможны два варианта решения задачи: для направленного графа и для ненаправленного графа. Рассмотрим решение задачи для направленного графа.
% Узлы
node(1..6).
%* Направленные дуги edge. Первый параметр – начальный узел, второй параметр – конечный узел *%
edge(1,(2;3;4)). edge(2,(4;5;6)). edge(3,(1;4;5)).
edge(4,(1;2)). edge(5,(3;4;6)). edge(6,(2;3;5)). % Количество цветов, в которые раскрашивается граф
#const n = 3.
%Возможные варианты цветов для каждого узла графа
{color(X,1..n) } = 1 :- node(X).
%Проверка: соседние вершины имеют разные цвета
:- edge(X,Y), color(X,C), color(Y,C).
#show color/2.
В результате получается один набор ответов:
color(2,2) color(1,3) color(3,2) color(4,1)
color(5,3) color(6,1)
Задача ненаправленного графа может быть сформулирована как задача раскрашивания стран на карте в минимальное количество цветов так, чтобы соседние страны имели разные цвета.
% Страны на карте (узлы графа)
countries(belgium;denmark;france;germany;netherlands). % Предполагается использовать 3 цвета
colors(red;green;blue). % Дуги графа
edge(france,(belgium;germany)).
edge(netherlands,belgium).
edge(germany,(belgium;netherlands;denmark)). % Дуги графа должны быть ненаправленные
neighbour(X,Y) :- edge(X,Y).
neighbour(Y,X) :- edge(X,Y).
20