Рекурсивные алгоритмы: примеры Рекурсивно-логическое программирование Григорьева И.В.

2 Бинарные деревья Бинарные деревья задаются с помощью тернарного функтора tree (Element, Left, Right), где Element-элемент, находящийся в вершине, a Left и Right-соответственно левое и правое поддерево. Пустое дерево изображается атомом void. Например, дерево a bc

3 может быть задано как tree(a, tree (b, void, void), tree (c, void, void)). tree (c, void, void)).. Определение бинарного дерева binary_tree (Tree) :- binary_tree(void). binary_tree (tree (Element, Left, Right)) :- binary_tree (Left), binary _tree(Right). Отметим, что программа с двойной рекурсией, т.е. в теле рекурсивного правила имеются две цели с тем же предикатом, что и в заголовке правила. Этот эффект возникает благодаря двойной рекурсивной природе бинарных деревьев.

4 Напишем некоторые программы обработки деревьев. Первый пример состоит в проверке, появляется ли некоторый элемент в дереве. Реляционная схема - tree_member (Element, Tree). Отношение выполнено, если элемент Element является одной из вершин дерева Tree. Декларативное понимание программы: «Х- элемент дерева, если X находится в вершине (согласно факту), или Х-элемент левого или правого поддерева (согласно двум рекурсивным правилам)».

5 tree-member (Element,Tree) :- tree_member (X, tree(X, Left, Right)). tree_member (X, tree(Y, Left, Right)) :- tree_member(X,Left). tree_member(X,tree(Y,Left,Right)) :- tree _ member(X,Right).

6 Две ветви бинарного дерева различны, но во многих приложениях это различие несущественно. Следовательно, возникает полезное понятие изоморфизма, которое определяет, являются ли два неупорядоченных дерева по существу одинаковыми. Два бинарных дерева T1 и Т2 изоморфны, если Т2 может быть получено из T1 изменением порядка ветвей в поддеревьях.

7 aab b cb c a c На рисунке изображены три простых бинарных дерева. Первые два изоморфны, третье не изоморфно им.

8 Изоморфизм является отношением эквивалентности с простым рекурсивным определением. Два пустых дерева изоморфны. В случае непустых деревьев два дерева изоморфны, если элементы в вершинах дерева совпадают, и/или оба левых поддерева и оба правых поддерева изоморфны, или левое поддерево одного дерева изоморфно правому поддереву другого и два других поддерева тоже изоморфны.

9 Следующая процедура определяет предикат isotree(Tree1,Tree2), который истинен, если дерево Тrее1 изоморфно дереву Тгее2. Аргументы входят в предикат симметрично. isotree (void, void). isotree(tree (X, Left1,Right1), tree(X,Left2,Right2)) :- isotree(Left1, Left2), isotree(Right1, Right2). isotree(tree (X, Left1, Right1), tree(X, Left2, Right2)) :- isotree(Left1,Right2), isotree(Right1,Left2).

10 Во многих приложениях, использующих деревья, требуется доступ к элементам, указанным в вершинах. Основной является идея обхода дерева в предписанном порядке. Имеются три возможности линейного упорядочения при обходе: сверху вниз, когда сначала идет значение в вершине, далее вершины левого поддерева, затем вершины правого поддерева; слева направо, когда сначала приводятся вершины левого поддерева, затем вершина дерева и далее вершины правого поддерева; и наконец, снизу ввepx, когда значение в вершине приводится после вершин левого и правого поддерева. Определение каждого из этих трех обходов приведено в следующей программе. Рекурсивная структура определений одинакова, единственное отличие состоит в порядке элементов, полученных применением целей вида конк.

11 % Pre- обход бинарного дерева Tree сверху вниз. pre_order(tree(X, L, R), Xs) :- pre_order(L, Ls), pre_order(R,Rs), конк( [X | Ls], Rs, Xs). pre_order(void, [ ]). % In -обход бинарного дерева Tree слева направо. in_order(tree(X, L, R),Xs) :- in_order(L, Ls), in_order(R, Rs), конк(Ls, [X | Rs], Xs). in_order(void,[ ]). % Post-обход бинарного дерева Tree снизу вверх. post_order(tree(X,L,R),Xs) :- post_order(L,Ls), post_order(R,Rs), конк(Rs, [X], Rs1), конк(Ls, Rs1, Xs). post_order(void,[ ]).

12 Работа с символьными выражениями Следующий пример - задача о «ханойской башне» - обычный начальный пример применения рекурсии. Задача состоит в перемещении башни из и дисков с одного стержня на другой, с использованием вспомогательного диска. Перемещения осуществляются в соответствии с двумя правилами: за один раз можно перенести лишь один диск, и больший диск нельзя устанавливать на меньший.

13 Имеется легенда, связанная с этой задачей. Где-то в окрестностях Ханоя, который во времена появления легенды был уединенным городком, спрятан монастырь. Монахи выполняют там работу, возложенную на них Богом при создании мира, решают описанную выше задачу с 3 золотыми стержнями и 64 золотыми дисками. В момент завершения работы мир должен рассыпаться в прах. Оптимальное решение задачи с n дисками требует 2^n -1 перемещений.

14 Реляционная схема решения задачи- hanoi(N,А,В,С,Moves). Отношение истинно, если Moves - последовательность перемещений для переноса башни из N дисков со стержня А на стержень В с использованием промежуточного стержня С. Это является некоторым обобщением обычного решения, при котором последовательность перемещений не вычисляется, а, скорее, выполняется. Запись перемещений использует бинарный функтор to, применяемый в виде инфиксного оператора. Терм X to Y означает, что верхний диск со стержня X переносится на стержень Y.

15 Moves - последовательность перемещений при решении задачи о ханойской башне с N дисками и тремя стержнями- A, В и С. hanoi( s(0), A, B, C, [A to В]). hanoi (s(N), A, B, C, Moves) :- hanoi( N, A, C, B, Ms1), hanoi(N, C, B, A, Ms2), конк (Ms1, [A to В | Ms2], Moves).

16 Декларативное понимание основы решения - рекурсивного правила программы, следующее: «Moves есть последовательность перемещений s(N) дисков со стержня А на стержень В с использованием промежуточного стержня С, если Ms1 - последовательность, решающая задачу перемещения N дисков с А на С с промежуточным диском В, Ms2 - последовательность, решающая задачу перемещения N дисков с С на В с промежуточным диском А, и Moves есть результат присоединения [А to B\Ms2] к Ms1».

17 Декларативное понимание основы решения - рекурсивного правила программы, следующее: «Moves есть последовательность перемещений s(N) дисков со стержня А на стержень В с использованием промежуточного стержня С, если Ms1 - последовательность, решающая задачу перемещения N дисков с А на С с промежуточным диском В, Ms2 - последовательность, решающая задачу перемещения N дисков с С на В с промежуточным диском А, и Moves есть результат присоединения [А toB \ Ms2] к Ms1».

18 Рекурсия обрывается при перемещении одного диска. Более изящен, но менее очевиден базис рекурсии, состоящий в перемещении в отсутствие дисков. Соответствующий факт: hanoi(0,A,B,C,[ ]).

19 Булевым формулам Булева формула есть терм, определяемый следующим образом: константы true и false-булевы формулы; если X и Y -булевы формулы, то X & Y, X I Y и ~ Х - булевы формулы, здесь & и I -бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный префиксный оператор отрицания.

20 Булева формула F истинна, если: F = 'true' F = X & Y, X и Y истинны F = X I Y, одна из формул X или Y (или обе) истинны F = ~ X, X ложна. Булева формула F ложна, если F = 'false' F = X & Y, одна из формул X или Y (или обе) ложны F = X I Y, X и Y ложны F = ~ X, X истинна.

21 Программа представляет собой логическую программу, определяющую истинность и ложность булевой формулы. Так как она может использоваться в случае булевой формулы с переменными, то эта программа важнее, чем кажется на первый взгляд. Булева формула с переменными выполнима если существует истинный пример формулы. Она опровержима, если существует ложный пример. Эти отношения и вычисляются в программе.

22 % satisfiable(Formula) % Существует истинный пример % булевой формулы Formula. satisfiable(true). satisftable(X & Y):- satisfiable(X), satisfiable(Y). satisfiable(X I Y):- satisfiable(X). satisfiable(X I Y):- satisfiable(Y). satisfiable( ~ X):- invalid(X).

23 % invalid(Formula) - % Существует ложный пример % булевой формулы Formula. invalid(false). invalid(X I Y):- invalid(X), invalid(Y). invalid(X & Y):- invalid(X). invalid(X & Y):- invalid(Y). invalid(~ Y):- satisfiable(Y).