Представление графов в языке Пролог

Для представления графов в языке Пролог можно использовать три способа:

1. Использование факта языка Пролог для описания дуг или рёбер графа.

2. Использование списка из структур данных: структура задаёт ребро графа.

3. Использование двух списков: списка вершин и списка рёбер.

Две самые распространённые операции, которые выполняются над графами:

· Поиск пути между двумя вершинами;

· Поиск в графе подграфа, который обладает некоторыми заданными свойствами.

Пример 52:

Определить наличие связи между вершинами графа, представленного на рисунке:

 

Две вершины графа связаны, если существует последовательность ребер, ведущая из первой вершины во вторую. Используем для описания структуры графа факты языка Пролог.

domains

top=symbol

predicates

edge (top, top)

/* аргументы обозначают имена вершин */

path( top,top)

/*Предикат connected(symbol, symbol) определяет отношение связанности вершин.*/

clauses

edge (a, b).

edge (c, d).

edge (a, c).

edge (d, e).

edge (b, d).

edge (f, g).

path (X, X).

path (X, Y):- edge (X, Z), path (Z, Y).

Пример 53:

Решить задачу из примера 52, используя списочные структуры для представления графа. Граф задается двумя списками: списком вершин и списком ребер. Граф задается списком структур: структура описывает ребро графа.

domains

edge= e(symbol, symbol)

list=edge*

predicates

path(list, symbol, symbol)

member(list,edge)

/*предикат path(graf, symbol, symbol) определяет отношение связности вершин.*/

clauses

member([H|_],H).

member([_|T],X):-member(T,X).

%path ([],_,_):-fail.

path(L,X,Y):-member(L,e(X,Y)),!.

path(L,X,Y):-member(L,e(X,Z)),path(L,Z,Y).

goal

path ([e(a, b),e(b, c),e(a, f),e(c, d),e(f,d)], a, d).

%path ([e(a, b),e(c, d),e(a, c),e(d, e),e(b, d),e(f, g)], b, g).

Поиск пути на графе.

Программы поиска пути на графе относятся к классу так называемых недетерминированных программ с неизвестным выбором альтернативы, то есть в таких программах неизвестно, какое из нескольких рекурсивных правил будет выполнено для доказательства до того момента, когда вычисление будет успешно завершено. По сути дела такие программы представляют собой спецификацию алгоритма поиска в глубину для решения определенной задачи. Программа проверки изоморфности двух бинарных деревьев, приведенная в примере 56 относится к задачам данного класса.

Пример 54:

Определить путь между вершинами графа, представленного на рисунке:

A- переменная обозначающая начало пути

B- вершина в которую нужно попасть

P -ациклический путь на графе (ациклический путь- это путь не имеющий повторяющих вершин).

 

domains

top=symbol

listtop=top*

predicates

edge (top, top)

/* аргументы обозначают имена вершин */

path (top, top, listtop)

/*Предикат path( top, top, listtop) создает список из вершин, составляющих путь.*/

clauses

edge (a, b).

edge (b, c).

edge (c, a).

edge (b, d).

edge (d, e).

path (A, A, [A]).

path (A, B, [A\P]):-edge(A, N), path(N, B, P).

С помощью поиска в глубину осуществляется корректный обход любого конечного дерева или ориентированного ациклического графа. Однако, встречаются задачи, где требуется производить обход графа с циклами. В процессе вычислений может образоваться бесконечный программный цикл по одному из циклов графа.

Неприятностей с зацикливанием можно избежать двумя способами: ограничением на глубину поиска или накоплением пройденных вершин. Последний способ можно реализовать при помощи модификации отношения path. К аргументам отношения добавляется дополнительный аргумент, используемый для накопления уже пройденных при обходе вершин, для исключения повторного использования одного и того же состояния применяется проверка.

Пример 55: написать программу обхода конечного ориентированного графа, представленного на рисунке.

domains

top=symbol

listtop=top*

predicates

edge(top,top)

path (top,top,listtop,listtop)

path (top,top)

member(top,listtop)

reverse(listtop,listtop,listtop)

clauses

edge(a,b).

edge(b,c).

edge(c,a).

edge(b,d).

edge(d,e).

member(A,[A|_]):-!.

member(A,[_|T]):-member(A,T).

reverse([],T2,T2).

reverse([H|T],T1,T2):-reverse(T,[H|T1],T2).

path(A,B,P,[B|P]):-edge(A,B).

path(A,B,P,P2):-edge(A,N),not(member(N,P)),

P1=[N|P], path (N,B,P1,P2).

path(A,B):-path(A,B,[A],P),reverse(P,[],Res),write(Res).

goal

path(a,e).

2.3.28 Метод “образовать и проверить”

Метод “образовать и проверить” – общий прием, используемый при проектировании алгоритмов и программ. Суть его состоит в том, что один процесс или программа генерирует множество предполагаемых решений задачи, а другой процесс или программа проверяет эти предполагаемые решения, пытаясь найти те из них, которые действительно являются решением задачи.

Используя вычислительную модель Пролога, легко создавать логические программы, реализующие метод “образовать и проверить”. Обычно такие программы содержат конъюнкцию двух целей, одна из которых действует как генератор предполагаемых решений, а вторая проверяет, являются ли эти решения приемлемыми. В Прологе метод “образовать и проверить” рассматривается как метод недетерминированного программирования. В такой недетерминированной программе генератор вносит предположение о некотором элементе из области возможных решений, а затем просто проверяется, корректно ли данное предположение генератора.

Для написания программ недетерминированного выбора конкретного элемента из некоторого списка в качестве генератора обычно используют предикат member из примера 36, порождающий множество решений. При задании цели member (X, [1,2,3,4]) будут даны в требуемой последовательности решения X=1, X=2, X=3, X=4.

Пример 56: проверить существование в двух списках одного и того же элемента.

domains

list=integer*

predicates

member (integer, list)

intersect(list,list)

clauses

member (Head, [Head |_ ]).

member (Head, [_ | Tail ]):- member (Head, Tail).

intersect (L1, L2):- member(X, L1), member(X, L2).

goal

intersect ([1, 4, 3, 2], [2, 5,6]).

Первая подцель member в предикате intersect генерирует элементы из первого списка, а с помощью второй подцели member проверяется, входят ли эти элементы во второй список. Описывая данную программу как недетерминированную, можно говорить, что первая цель делает предположение о том, что X содержится в списке L1, а вторая цель проверяет, является ли X элементом списка L2.

Следующее определение предиката member с использованием предиката append:

member(X, L):- append(L1, [X|L2], L) само по существу является программой, в которой реализован принцип «образовать и проверить». Однако, в данном случае, два шага метода сливаются в один в процессе унификации. С помощью предиката append производится расщепление списка и тут же выполняется проверка, является ли X первым элементом второго списка.

Еще один пример преимущества соединения генерации и проверки дает программа для решения задачи об N ферзях: требуется разместить N ферзей на квадратной доске размером NxN так, чтобы на каждой горизонтальной, вертикальной или диагональной линии было не больше одной фигуры. В первоначальной формулировке речь шла о размещении 8 ферзей на шахматной доске таким образом, чтобы они не угрожали друг другу. Отсюда пошло название задачи о ферзях.

Эта задача хорошо изучена в математике. Для N=2 и N=3 решения не существует; два симметричных решения при N=4 показаны на рисунке. Для N=8 существует 88 (а с учетом симметричных – 92) решений этой задачи.

 

		Q
Q
			Q
	Q
	Q
			Q
Q
		Q

 

Приведенная в примере 57 программа представляет решение задачи об N ферзях. Решение задачи представляется в виде некоторой перестановки списка от 1 до N. Порядковый номер элемента этого списка определяет номер вертикали, а сам элемент – номер горизонтали, на пересечении которых стоит ферзь. Так решение [2, 4, 1, 3] задачи о четырех ферзях соответствует первому решению, представленному на рисунке, а решение [3, 1, 4, 2]- второму решению. Подобное описание решений и программа их генерации неявно предполагают, что в любом решении задачи о ферзях на каждой горизонтали и на каждой вертикали будет находиться по одному ферзю.

Пример 57: программа решения задачи об N ферзях.

domains

list=integer*

predicates

range (integer, integer, list)

/* предикат порождает список, содержащий числа в заданном интервале*/

queens (list, list, list)

/* предикат формирует решение задачи о N ферзях в виде списка решений, при этом первый список – текущий вариант списка неразмещённых ферзей, второй список промежуточное решение, третий список - результат*/

select (integer, list, list)

/*предикат удаляет из списка одно вхождение элемента*/

attack (integer, list)

/*предикат преобразует attack, чтобы ввести начальное присваивание разности в номерах горизонталей */

attack (integer, integer, list)

/*предикат проверяет условие атаки ферзя другими ферзями из списка, два ферзя находятся на одной и той же диагонали, на расстоянии M вертикалей друг от друга, если номер горизонтали одного ферзя на M больше или на M меньше номера горизонтали другого ферзя*/

fqueens (integer, list)

clauses

range (M, N, [M|T]):- M<N, M1=M+1, range (M1, N, T).

range (N, N, [N]):-!.

select(X,[X|T1],T1).

select (X, [Y|T1], [Y|T2]):-select (X, T1, T2).

attack (X, L):- attack(X, 1, L).

attack( X, N, [Y|T2]):-N=X-Y; N=Y-X.

attack( X, N, [Y|T2]):-N1=N+1, attack (X, N1, T2).

queens (L1, L2, L3):-select (X, L1, L11),

not (attack (X,L2)),

queens (L11, [X|L2], L3).

queens ([], L, L).

fqueens(N,L):-range (1, N, L1),

queens(L1,[],L).

goal

fqueens (4,L).

В данной программе реализован принцип «образовать и проверить», так как сначала с помощью предиката range генерируется список, содержащий числа от 1 до N. Предикат select перебирает все элементы из полученного списка для размещения очередного ферзя, при этом корректность размещения проверяется при помощи предиката attack. Таким образом, генератором является предикат select, а проверка реализуется при помощи отрицания предиката attack. Чтобы проверить, в безопасном ли положении находится новый ферзь, необходимо знать позиции ранее размещенных ферзей. В данном случае для хранения промежуточных результатов используется второй параметр предиката queens, так как решение задачи находится на прямом ходе рекурсии, для закрепления результата при выходе из рекурсии используется третий параметр.