Программы поиска пути на графе относятся к классу так называемых недетерминированных программ с неизвестным выбором альтернативы, то есть в таких программах неизвестно, какое из нескольких рекурсивных правил будет выполнено для доказательства до того момента, когда вычисление будет успешно завершено. По сути дела такие программы представляют собой спецификацию алгоритма поиска в глубину для решения определенной задачи. Программа проверки изоморфности двух бинарных деревьев, приведенная в примере 56 относится к задачам данного класса.
Пример 74:
Определить путь между вершинами графа, представленного на рисунке:
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. К аргументам отношения добавляется дополнительный аргумент, используемый для накопления уже пройденных при обходе вершин, для исключения повторного использования одного и того же состояния применяется проверка.
Пример 75: написать программу обхода конечного ориентированного графа, представленного на рисунке.
Метод “образовать и проверить” – общий прием, используемый при проектировании алгоритмов и программ. Суть его состоит в том, что один процесс или программа генерирует множество предполагаемых решений задачи, а другой процесс или программа проверяет эти предполагаемые решения, пытаясь найти те из них, которые действительно являются решением задачи.
Используя вычислительную модель Пролога, легко создавать логические программы, реализующие метод “образовать и проверить”. Обычно такие программы содержат конъюнкцию двух целей, одна из которых действует как генератор предполагаемых решений, а вторая проверяет, являются ли эти решения приемлемыми. В Прологе метод “образовать и проверить” рассматривается как метод недетерминированного программирования. В такой недетерминированной программе генератор вносит предположение о некотором элементе из области возможных решений, а затем просто проверяется, корректно ли данное предположение генератора.
Для написания программ недетерминированного выбора конкретного элемента из некоторого списка в качестве генератора обычно используют предикат member из примера 36, порождающий множество решений. При задании цели member (X, [1,2,3,4]) будут даны в требуемой последовательности решения X=1, X=2, X=3, X=4.
Пример 76: проверить существование в двух списках одного и того же элемента.
Первая подцель 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
Приведенная в примере 77 программа представляет решение задачи об N ферзях. Решение задачи представляется в виде некоторой перестановки списка от 1 до N. Порядковый номер элемента этого списка определяет номер вертикали, а сам элемент – номер горизонтали, на пересечении которых стоит ферзь. Так решение [2, 4, 1, 3] задачи о четырех ферзях соответствует первому решению, представленному на рисунке, а решение [3, 1, 4, 2]- второму решению. Подобное описание решений и программа их генерации неявно предполагают, что в любом решении задачи о ферзях на каждой горизонтали и на каждой вертикали будет находиться по одному ферзю.
Пример 77: программа решения задачи об 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).
attack1 (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 (attack1 (X,L2)),
queens (L11, [X|L2], L3).
queens ([], L, L).
fqueens(N,L):-range (1, N, L1),
queens(L1,[],L).
goal
fqueens (4,L),write(L).
При таком задании цели, будет выдано второе решение, представленное на рисунке, если задать внешнюю цель, то будут выданы оба решения.
В данной программе реализован принцип «образоввать и проверить», так как сначала с помощью предиката range генерируется список, содержащий числа от 1 до N. Предикат select перебирает все элементы из полученного списка для размещения очередного ферзя, при этом корректность размещения проверяется при помощи предиката attack. Таким образом, генератором является предикат select, а проверка реализуется при помощи отрицания предиката attack. Чтобы проверить, в безопасном положении находится новый ферзь, необходимо знать позиции ранее размещенных ферзей. В данном случае для хранения промежуточных результатов используется второй параметр предиката queens, так как решение задачи находится на прямом ходе рекурсии, для закрепления результата при выходе из рекурсии используется третий параметр.
