(рис 8.1)
Смеющаяся корова, изображенная на фирменном жетоне "Смеющаяся Корова", носит в качестве сережек фирменные жетоны, на которых, я подозреваю, но зрение не позволяет убедиться в правильности моего предположения, изображена корова с фирменными жетонами, на которых изображена …
Эта реклама, появившаяся в 1921 году, все еще хорошо работает, являясь примером структуры, определенной рекурсивно в следующем смысле:
"Рекурсия" – использование рекурсивного определения – широко применяется в программировании: она позволяет элегантно определять синтаксические структуры; мы также познакомимся с рекурсивно определенными структурами данных и рекурсивными процедурами.
Мы будем использовать термин "рекурсивный" как сокращение "рекурсивно определенный" – рекурсивная грамматика,
При рассмотрении свойств рекурсивно определенного понятия будем применять рекурсивные доказательства – обобщающие индуктивные доказательства, использующие целые числа для индуктивного шага.
Рекурсия является прямой, если определение $$А$$ ссылается на экземпляр $$А$$, и косвенной, если для $$1 <= i < n$$ (для некоторого $$n >=2$$) определение каждого $$A_i$$ ссылается на $$A_{i+1}$$, а определение $$A_n$$ ссылается на $$A_1$$.
В этой лекции нас будут интересовать такие понятия, для которых рекурсивные определения естественны, элегантны и удобны. Примеры будут включать рекурсивные программы, рекурсивные синтаксические определения, рекурсивные структуры данных. Мы также получим некоторое представление о рекурсивных доказательствах.
Один из классов
В этот момент могут возникнуть вполне обоснованные сомнения – а есть ли смысл в рекурсивных определениях, как можно определить понятие через само понятие, "масло масляное"?
Вы вправе сомневаться. Не все рекурсивные определения хороши для определения чего-либо. Когда вас просят дать характеристику кому-нибудь, а вы отвечаете: "Света? Ну, это просто Света, что еще можно сказать!" – то вы не много нового сказали. Так что следует позаботиться о критериях, гарантирующих полезность определения, даже если оно рекурсивно.
Прежде чем мы это сделаем, позвольте убедиться прагматичным путем, ознакомившись с несколькими типичными примерами, когда рекурсия очевидно полезна и осмысленна. Это придаст нам твердую убежденность, большую, чем просто вера, основанная на надеждах и молитвах, что рекурсия – это практически полезный способ определять грамматики, структуры данных и алгоритмы. После чего настанет время для подходящего математического обоснования рекурсивных определений.
С введением универсальности мы получаем возможность определять тип как:
| Т1 | класс, не являющийся универсальным, такой как INTEGER или STATION; |
| Т2 | родовое порождение в форме C[T], где С – Т – тип. |
Это определение рекурсивно, оно просто означает, что, при наличии ARRAY и LIST, правильными классами также будут:
INTEGER, STATION и им подобные в соответствии с определением Т1;Т2, прямые родовые порождения: ARRAY[INTEGER], LIST[STATION] и так далее.Т2: ARRAY[LIST[INTEGER]], ARRAY[ARRAY [LIST[STATION]]] и так далее – родовые порождения любого уровня вложенности.Используя подобный прием, можно дать ответ на упражнение из первой лекции, где требовалось дать определение алфавитному (лексикографическому) порядку.
Рассмотрим подмножество Eiffel с двумя видами операторов.
variable:= expression, рассматриваемое здесь как терминальное и далее не уточняемое.then (без else) для простоты.Грамматика, определяющая язык, такова:
$$\text{Оператор }\triangleq\text{ Присваивание | Условный}\\\text{Условный }\triangleq}\text{ if Условие then Оператор end }$$Для наших непосредственных целей будем полагать, что "Условие" является терминальным понятием. Это определение грамматики очевидно рекурсивно, поскольку определение "Оператор" включает "Условный", а его определение, в свою очередь, включает "Оператор". Но так как здесь присутствует нерекурсивная часть определения – "Присваивание", то в целом грамматика четко определяет правильные конструкции языка:
if c then a end;if c1 then if c2 then a end end, if c1 then if c2 then if c3 then a end end end и так далее.Рекурсивные грамматики на самом деле являются незаменимым средством для описания любого языка, который, как все распространенные языки, поддерживает вложенные структуры.
Класс STOP представляет понятие остановки для линии метро:
class STOP create
…
feature
next: STOP
— Следующая остановка на той же линии.
…Другие компоненты, здесь опущенные (см.6.5)
end
Наивная интерпретация будет предполагать, что каждый экземпляр STOP содержит экземпляр STOP, который, в свою очередь, содержит остановку и так до бесконечности, как в схеме со Смеющейся коровой. Это и в самом деле было бы так, если бы STOP принадлежал развернутым, а не ссылочным типам:
(рис 8.2) Вложенные поля (интерпретация не корректна)
Такое попросту невозможно. Но STOP в любом случае является ссылочным типом, подобно любому классу, определенному как class X… без всяких других квалификаций, так что реальная картина выглядит так:
(рис 8.3) Линия, связанная ссылками
Рекурсия в таком определении структуры данных просто указывает, что каждый экземпляр класса потенциально содержит ссылку на экземпляр того же класса, "потенциально" – поскольку ссылка может иметь значение void, и тогда действие рекурсии прекращается, как для последней остановки на рисунке.
В той же 6-й главе, где рассматривались линии метро, шла речь и о классе PERSON c атрибутом spouse типа PERSON.
Это весьма общая ситуация в определении полезных структур данных, начиная от связных списков до деревьев различного вида (таких как бинарные деревья, изучаемые позже в этой лекции). Определения полезных классов часто включают ссылки на объекты определяемого класса или (
Известная последовательность чисел Фибоначчи обладает многими прекрасными свойствами и появляется во многих приложениях математики и естественных наук. Она имеет следующее определение:
$$F_0=0\\F_1=1\\F_i=F_{i-1}+F_{i-2}\qquad \text{- Для}\;i>1$$Леонардо Фибоначчи из Пизы (1170 – 1250) сыграл ключевую роль в знакомстве Запада с трудами индийских и арабских математиков. Он известен также и собственными исследованиями, лежащими в основании современной математики. Он сформулировал задачу, приводящую к его знаменитой последовательности (которая была известна еще индийским математикам):
Человек получил пару кроликов и поместил их в загон, окруженный со всех сторон стеной. Как много пар кроликов можно получить от этой пары в год, если каждый месяц каждая пара производит новую пару, которая становится продуктивной на втором месяце?
(рис 8.4) Фибоначчи
Решение дает следующее рассуждение. Пары кроликов в месяце $$i$$ включают пары кроликов, уже существующие в предыдущем месяце (кролики не умирают); обозначим их число как $$F_{i-1}$$, плюс потомство, принесенное кроликами, жившими в месяце $$i-2$$ (кролики, появившиеся в месяце $$i-1$$, потомства не приносят). Это и дает приведенную выше формулу, создающую последовательность целых чисел 0, 1, 1, 2, 3, 5, 8 и так далее. Формула приводит к рекурсивной программе, вычисляющей $$F_n$$ для любого $$n$$:
fibonacci (n: INTEGER): INTEGER
— Элемент с индексом n в последовательности Фибоначчи.
require
non_negative: n >= 0
do
if n = 0 then
Result := 0
elseif n = 1 then
Result := 1
else
Result := fibonacci(n – 1)+ fibonacci(n – 2)
end
end
Напишите небольшую программную систему, включающую вышеприведенную рекурсивную функцию и печатающую ее результат. Протестируйте ее для небольших значений n, включая 12, как в оригинальном тексте Фибоначчи.
Функция включает два рекурсивных вызова. То, что это работает, может казаться несколько загадочным (вот почему стоит проверить выполнение функции на нескольких значениях). После изучения этой лекции легитимность таких
Принципиальным аргументом в пользу такого способа записи программы есть то, что она вполне соответствует математическому определению последовательности Фибоначчи. Дальнейшее рассмотрение покажет, что этот факт не столь впечатляющий, поскольку получить нерекурсивную версию также не сложно.
Можете ли вы, не заглядывая в дальнейший текст, написать функцию, вычисляющую N-е
Следующая функция дает тот же результат, что и рекурсивная версия. Проверьте это на нескольких значениях.
fibonacci1 (n: INTEGER): INTEGER
— Элемент с индексом n в последовательности Фибоначчи.
— (Нерекурсивная версия.)
require
positive: n >=1
local
i, previous, second_previous: INTEGER
do
from
i := 1 ; Result := 1
invariant
Result = fibonacci(i )
previous = fibonacci (i – 1)
until i = n loop
i := i + 1
second_previous := previous
previous := Result
Result := previous + second_previous
variant
n – i
end
end
n >= 1, а не n >= 0. Благодаря правилам инициализации previous начинается с 0, что гарантирует начальное выполнение инварианта, так как $$F_0 = 0$$. Переменная second_previous обновляется на каждом шаге цикла и ей не нужно специальной инициализации.Эта версия более удалена от оригинального математического определения, но все же проста и понятна. Заметьте:
Оставим в стороне вкус и эффективность. Если бы мы рассматривали только такие примеры, то необходимость рекурсивных программ была бы далеко не очевидной. Нам необходимы примеры, в которых рекурсия обеспечила бесспорные преимущества, например, за счет того, что ее нерекурсивный аналог был бы значительно сложнее и труднее в понимании. Такие примеры существуют в большом количестве. Одним из них является очаровательная головоломка – "Ханойская башня". В этом примере сконцентрировано много полезных свойств рекурсии, и практически нет не относящихся к делу деталей.
В величественном храме Бенареса, под куполом, отмечающим центр мира, на медной плите установлены три бриллиантовых стержня. Каждый стержень высотой в локоть и тонок, как пчелиная талия. На один из этих стержней в начале мироздания Бог поместил 64 диска из чистого золота. Самый большой диск покоится на медной плите, а остальные, друг друга меньше, создают пирамиду, вздымающуюся к вершине стержня. Это и есть священная башня Брахмы.
Ночью и днем неустанно священники, сменяя друг друга, работают, чтобы перенести священную башню на третий бриллиантовый стержень, не нарушив при этом священных правил, установленных Брахмой. Когда их работа будет закончена, падет башня, падут брахманы и наступит конец мира.
(рис 8.5) Башня Ханоя (должна быть башней Бенареса?) из 9 дисков в начальном состоянии
Несмотря на восточный орнамент, эта история является созданием французского математика Эдуарда Лукаса (подписывающегося как "N. Claus de
Почему коммерчески доступные модели Ханойской башни имеют размеры много меньшие, чем 64 диска?
(Подсказка: игра сопровождается бумажным свертком, на котором дается решение головоломки в форме последовательности ходов; А => C, A => B и т. д.)
Чтобы ответить на этот вопрос, давайте оценим минимальное число ходов $$H_n$$ (ход – это перемещение диска с одного стержня на другой), требуемое для решения задачи. Если задача имеет решение, то нужно перенести n дисков со стержня А на стержень В, используя стержень С как промежуточный. При этом нужно соблюдать правило Будды, запрещающее класть больший диск на меньший. В оригинальной версии n = 64, для небольшой модели n = 9.
Заметим, что для любой стратегии перемещения в некоторый момент необходимо перенести самый большой диск со стержня А на стержень В, а это возможно лишь при условии, что все остальные n -1 дисков в этом момент находятся на диске С в требуемом порядке:
(рис 8.6) Промежуточное состояние
Каково минимальное число ходов, необходимое для достижения этого промежуточного состояния? Необходимо перенести n -1 диск со стержня А на стержень С, не перемещая самый большой диск и используя стержень В как промежуточный. Ввиду симметричности задачи для этого потребуется $$H_{n-1}$$ ходов.
Сразу же по достижении этого состояния можно перенести за один ход самый большой диск с А на В, после чего перенести n – 1 диск с С на В, используя А как промежуточный. Общее количество ходов:
$$H_n=2*H_{n-1}+1$$Учитывая, что $$H_0$$ равно 0, получим:
$$H_n=2^n-1$$Как следствие, нетрудно получить ответ на наш тест. Вспомним, что $$2^{10} = 1024$$, или примерно $$10^3$$, и получим, что число ходов $$2^{64}$$ примерно равно $$1,5 * 10^{19}$$.
Год – это примерно 30 миллионов секунд. Если предположить, что священники Бенареса за секунду выполняют один ход – весьма неплохая скорость для переноса золотого диска, – всю работу они закончат за 500 миллиардов лет, что примерно в 30 раз превосходит оценочный возраст существования нашей вселенной. Даже компьютеру, выполняющему 100 миллионов ходов за секунду, при моделировании этой задачи для переноса дисков потребуется не одна тысяча лет.
Вывод оценки $$H_n$$ был конструктивным, в том смысле, что он дает практическую стратегию для перемещения дисков.
Эта стратегия превращает число ходов $$H_n = 2^n – 1$$ из теоретического минимума в практически достижимую цель. Мы можем записать алгоритм в виде рекурсивной процедуры, входящей в класс
hanoi (n: INTEGER; source, target, other: CHARACTER)
— Перенос n дисков из source на target,
— используя other как промежуточное хранилище,
— в соответствии с правилами игры "Ханойская башня"
require
non_negative: n >= 0
different1: source /= target
different2: target /= other
different3: source /= other
do
if n > 0 then
hanoi (n–1, source, other, target)
move (source, target)
hanoi (n–1, other, target, source)
end
end
По соглашению стержни представляются символами – 'A', 'B', 'C'. Другое соглашение, принятое в этой лекции (уже использованное в предыдущих примерах), состоит в подсветке рекурсивных ветвей кода, – процедура hanoi содержит два таких участка.
Базисная операция move(source, target) перемещает один диск с вершины стержня source на вершину target. Предусловие устанавливает, что на source должен находиться, по крайней мере, один диск, а на target диска либо нет, либо диск в вершине имеет больший размер, чем перемещаемый диск. Запишем move как процедуру, выводящую на консоль инструкцию по перемещению диска:
move (source, target: CHARACTER)
— Инструкция по перемещению диска с source на target.
do
io.put_character (source)
io.put_string (" to ")
io.put_character (target)
io.put_new_line
end
Напишите систему с корневым классом hanoi и move. Проверьте их работоспособность на примерах.
Например, выполните вызов
hanoi (4, 'A', 'B', 'C')
В результате должна быть напечатана последовательность из пятнадцати ($$2^4 – 1$$) ходов:
| A на C | B на C | B на A |
| A на B | A на C | C на B |
| C на B | A на B | A на C |
| A на C | C на B | A на B |
| B на A | C на A | C на B |
Эта последовательность ходов успешно переносит диски с А на B в полном соответствии с правилами игры.
Один из способов анализа рекурсивного решения – процедуры hanoi – состоит в том, чтобы рассматривать перемещение n – 1 дисков, как один обобщенный ход. В этом случае мы могли бы начать перемещение с этого хода (с А на С):
(рис 8.7) Начальный глобальный ход Фибоначчи
После этого можно сделать обычный ход, перенеся самый большой диск на целевой стержень, а затем снова выполнить обобщенный ход, который легален, поскольку все диски обобщенного хода меньше, чем диск, уже лежащий на целевом стержне.
Конечно, это фиктивное рассмотрение, поскольку правилами разрешается перенос только одного диска за один ход, но перемещая n – 1 диск, можно применять ту же технику, зная, что целевой стержень либо пуст, либо содержит диски большего размера. Так можно рекурсивно выполнять перемещения, уменьшая каждый раз значение n. Когда же n становится равным нулю, то делать ничего не нужно.
Не стоит легкомысленно относиться к примеру с Ханойской башней. Это решение служит прекрасной моделью для многих рекурсивных программ с важными практическими приложениями. Простота алгоритма является результатом использования двух рекурсивных вызовов, и это делает эту задачу идеальной для изучения свойств рекурсивных алгоритмов, к чему мы вернемся чуть позже в этой лекции.
В предыдущих лекциях мы рассматривали управляющие структуры языка программирования как технику, используемую для решения сложных задач.
(рис 8.8)
Что можно сказать о рекурсивном решении? К кому нужно обращаться? Ответ – к себе! Возможно – несколько раз (как в случае с Ханойской башней и многих других)!
Зачем обращаться к другим, если я доверяю себе (по крайней мере, я так думаю)?
Теперь мы знаем, что эта стратегия не так глупа, как может казаться с первого раза. Я прошу себя решить ту же задачу, но на подмножестве исходных данных или на нескольких таких подмножествах. Тогда я могу справиться с задачей, если удастся
Такова идея рекурсии, рассматриваемая как стратегия решения сложной задачи. Она связана с некоторыми предыдущими стратегиями.
Если Ханойская башня является квинтэссенцией рекурсивной процедуры, то бинарные деревья являются квинтэссенцией
Бинарное дерево над G, для произвольного типа данных G, задается конечным множеством элементов, называемых узлами, каждый из которых содержит значение типа G. Узлы, если они есть, разделяются на три непересекающихся подмножества:
Все это просто выразить в каркасе класса, не включающем методов:
class BINARY_TREE [G] feature
item: G
left, right: BINARY_TREE[G]
end
Ссылка void указывает на пустое дерево. Проиллюстрируем бинарное дерево над целыми (рис 8.9).
Форма "Ветвления" – это наиболее общий стиль представления бинарных деревьев, но не единственный: возможно представление в форме вложенности, которое для данного примера выглядит так (рис 8.10).
Определение бинарного дерева явно допускает, что дерево может быть пустым. Без этого, конечно, рекурсивное определение приводило бы к бесконечной структуре, в то время как бинарные деревья, что также предписано определением, являются конечными структурами данных.
(рис 8.9) Соглашение: Бинарное дерево (представленное "ветвлением")
(рис 8.10) Бинарное дерево (вложенное представление)
Если бинарное дерево не пусто, то оно всегда имеет корень и может не иметь поддеревьев, иметь только левое или только правое поддерево или иметь оба поддерева.
Любой узел бинарного дерева сам рассматривается как бинарное дерево. Достаточно взглянуть на два последних рисунка. Узел, помеченный как 35, задает полное дерево, 23 – его
Большинство методов класса, определяющего рекурсивную структуру класса, будут строиться рекурсивно с учетом рекурсивного определения данных. Простым примером является метод, подсчитывающий число узлов бинарного дерева. В пустом дереве число узлов равно нулю, для непустого дерева число узлов равно сумме трех значений: для корня и числа узлов соответственно левого и правого поддеревьев. Нетрудно записать это наблюдение в виде рекурсивной функции, входящей в класс BINARY_TREE.
count: INTEGER
— Число узлов.
do
Result := 1
if left /= Void then Result := Result + left.count end
if right /= Void then Result := Result + right.count end
end
Заметьте схожесть этой функции с процедурой Hanoi.
Дети (непосредственные потомки) узла – сами узлы – являются корневыми узлами левого и правого поддеревьев:
(рис 8.11) Бинарное дерево (представление "ветвлением")
Если С – сыновний (дочерний) узел В, то В – родитель С. Более точно мы можем сказать, что В является "родителем" С, благодаря следующему результату:
Теорема кажется очевидной, но мы докажем ее, что даст нам возможность познакомиться с рекурсивными доказательствами.
Рекурсивное доказательство теоремы о единственном родителе в значительной степени отражает рекурсивное определение бинарного дерева.
Если бинарное дерево BT пусто, то теорема выполняется. В противном случае бинарное дерево имеет корень и два непересекающихся бинарных дерева, о которых мы можем предположить – "рекурсивная предпосылка", – что они оба удовлетворяют теореме. Это следует из определений "бинарного дерева", "ребенка" и "родителя", так что узел С может иметь родителя Р в ВТ только одним из трех возможных случаев:
| Р1 | Р является корнем ВТ, а С является корнем либо левого, либо правого поддерева; |
| Р2 | они оба принадлежат |
| Р3 | они оба принадлежат правому поддереву, и Р является родителем С в этом поддереве. |
В случае Р1 узел С по гипотезе рекурсивности, являясь корнем, не имеет родителей в своем поддереве, так что у него есть единственный родитель – корень всего дерева ВТ. В случаях Р2 и Р3, опять-таки по гипотезе рекурсивности, Р был единственным родителем С в соответствующем поддереве, и это остается верным и во всем дереве.
Любой узел С, отличный от корня, удовлетворяет одному из трех рассмотренных вариантов и, следовательно, имеет в точности одного родителя. Только если С является корнем дерева, он не будет соответствовать рассмотренным ситуациям и, как следствие, у него не будет родителей, что и завершает доказательство теоремы.
Подобные рекурсивные доказательства полезны, когда необходимо установить, что некоторое свойство выполняется для всех экземпляров рекурсивно определенного понятия. Структура доказательства определяется структурой определения.
Эта схема применима в целом для всех рекурсивно определяемых понятий. Мы увидим ее применение к рекурсивно определенной процедуре hanoi.
Интересный пример бинарного дерева можно получить, моделируя выполнение процедуры hanoi, например, для трех дисков. Каждый узел содержит аргументы данного вызова, а левое и правое поддерево соответствуют рекурсивным вызовам:
(рис 8.12) Выполнение Hanoi, рассматриваемое как бинарное дерево
Добавление операции move позволило бы реконструировать последовательность операций. Формально мы выполним это позднее.
Этот пример высвечивает связь межу рекурсивными алгоритмами и hanoi, выполнение моделировалось бы не бинарным деревом, а деревом общего вида.
Еще о свойствах бинарных деревьях и о терминологии
Как отмечалось, узел бинарного дерева может иметь:
(рис 8.13) Копия ранее приведенного дерева
Определим восходящий путь в бинарном дереве как последовательность из нуля или более узлов, где любой узел последовательности является родителем предыдущего узла, если таковой имеется. В нашем примере узлы с метками 60, 78, 54 формируют восходящий путь. Справедливо следующее свойство, являющееся следствием теоремы о единственном родителе.
Доказательство. Рассмотрим произвольный узел С бинарного дерева. Построим восходящий путь, начинающийся в С. В соответствии с теоремой о единственном родителе такой путь определяется единственным образом. Если путь конечен, то заканчиваться он должен в корне дерева, поскольку любой другой узел имеет родителя, и следовательно, построение восходящего пути могло бы быть продолжено. Для завершения доказательства необходимо показать, что все пути конечны. Единственный способ построения бесконечного пути (учитывая, что число узлов бинарного дерева по определению конечно) состоит в том, что путь включает цикл. Если некоторый узел n встретится дважды, то он встретится сколь угодно много раз, так что бесконечный путь должен содержать подпоследовательность в форме n... n. Но это означает, что n появляется в своем собственном левом или правом поддереве, что невозможно по определению бинарных деревьев.
Рассмотрение нисходящих путей позволяет установить следующий факт, как следствие предыдущей теоремы.
Весом бинарного дерева является максимальное число узлов среди всех нисходящих путей от корня к
Это понятие можно определить рекурсивно, следуя снова рекурсивной структуре определения. Вес пустого дерева равен нулю. Вес непустого дерева равен 1 плюс максимум (рекурсивно) из весов левого и правого поддеревьев. Мы можем добавить соответствующую функцию в класс BINARY_TREE:
height: INTEGER
— Максимальное число узлов нисходящего пути.
local
lh, rh: INTEGER
do
if left /= Void then lh := left.height end
if right /= Void then rh := right.height end
Result := 1 + lh.max (rh)
end
Здесь рекурсивное определение адаптируется к соглашению, принятому для класса, который рассматривает только непустые поддеревья. Отметьте опять-таки схожесть с hanoi.
В классе BINARY_TREE пока определены только три компонента, все они являются запросами: item, left и right. Мы можем добавить процедуру создания:
make (x: G)
— Инициализация item значением x.
do
item := x
ensure
set: item = x
end
Добавим в класс команды, позволяющие изменять поддеревья, и значение в корне:
add_left (x: G)
— Создать левого сына со значением x..
require
no_left_child_behind: left = Void
do
create left.make (x)
end
add_right … Аналогично add_left…
replace (x: G)
— Установить значение корня равным x.
do item := x end
На практике удобно специфицировать replace как команду-присваиватель для соответствующего запроса, изменив объявление запроса следующим образом:
item: G assign replace
Это позволяет писать bt.item:= x вместо bt.item.replace(x).
Нет ничего удивительного в том, что, благодаря рекурсивной определенности, с бинарным деревом связываются многие height является одним из таких примеров. Приведем сейчас и другие. Предположим, что требуется напечатать все значения элементов, связанных с узлами дерева. Следующая процедура, добавленная в класс, выполняет эту работу:
print_all
— Печать значений всех узлов.
do
if left /= Void then print_all (left)end
print (item)
if right /= Void then print_all (right) end
end
print (доступная всем класса через общего родителя ANY), которая печатает подходящее представление значения типа G – родового параметра в классе BINARY_TREE[G].Заметьте, структура print_all идентична структуре hanoi.
Хотя роль процедуры print_all состоит в печати всех значений, ее алгоритмическая схема не зависит от специфики операции, выполняемой над узлами дерева (print в данном случае). Процедура является примером обхода бинарного дерева: алгоритма, выполняющего однократно некоторую операцию над каждым элементом структуры данных в некотором заранее предписанном порядке обхода узлов. Обход является вариантом итерации.
Для двоичных деревьев наиболее часто используются три порядка обхода дерева, которые иногда называют соответственно инфиксным, префиксным и постфиксным порядками обхода.
В этих определениях "посетить" означает выполнение операции над отдельным узлом, такой как print в процедуре print_all; "обход" означает либо рекурсивное применение алгоритма для поддерева, либо отсутствие каких-либо действий, если поддерево пусто.
Префиксный порядок обхода, так же как и другие способы обхода, идущие, насколько это возможно, в глубину поддерева, называются также обходами "вначале в глубину", например, "самый левый в глубину".
Процедура print_all является иллюстрацией инфиксного способа обхода дерева. Достаточно просто записываются и другие способы обхода, например, для постфиксного обхода тело процедуры post имеет вид:
if left /= Void then post (left) end
if right /= Void then post (right) end
visit (item)
Здесь visit является операцией над узлом, такой как print.
visit. Чтобы избежать этого, можно рассматривать операцию как аргумент метода обхода. Это возможно сделать в Eiffel, используя механизм агентов, описанный в последующих лекциях.В качестве еще одной иллюстрации инфиксного обхода рассмотрим снова бинарное дерево выполнения hanoi для n = 3, где узлы уровня 0 опущены, поскольку не представляют интересной информации в данном случае.
(рис 8.14) Выполнение Hanoi в инфиксном порядке обхода
Процедура hanoi является матерью всех инфиксных обходов: обход левого дерева, если оно есть, посещение корня, обход правого поддерева, если оно есть. При посещении каждого узла выполняется операция move(source, target). Инфиксный порядок дает нужную последовательность ходов: A B, A C, B C, A B, C A, C B, A B.
Для произвольного бинарного дерева процедура print_all, реализующая инфиксный порядок, печатает значения узлов в произвольном порядке. Если же порядок важен для нас, то необходимо переходить к бинарным деревьям поиска.
Множество G, над которым определено общее бинарное дерево, может быть любым множеством. Для бинарных деревьев поиска предполагается, что на множестве G задано полное отношение порядка, позволяющее сравнивать любые два элемента G, задавая a < b, такое, что истинно одно из трех отношений: a < b, b < a, a ∼ b. Примерами таких множеств могут служить INTEGER и REAL с отношением порядка <, но G может быть любым вполне упорядоченным множеством.
Как обычно, мы пишем a < = b, когда либо a < b, либо a ∼ b. Аналогично, b > a, если a < b. Над вполне упорядоченным множеством можно определить бинарное дерево поиска.
root со значением item, равным r, выполняются условия:
item, равным le, справедливо: le < r;root есть правое поддерево, то для любого его узла со значением item, равным ri, справедливо: ri > r.Значения в узлах
(рис 8.15) Упражнение 5.11.3
Дерево, показанное на рисунке, является бинарным деревом поиска.
Процедура print_all, примененная к этому дереву, напечатает значения, упорядоченные по возрастанию, начиная с наименьшего значения 12.
Используя приведенные на данный момент процедуры, постройте дерево, показанное на рисунке, затем напечатайте значения в узлах, вызвав print_all. Убедитесь, что значения упорядочены.
Давайте рассмотрим причины, по которым деревья поиска являются полезными, как контейнерные структуры – потенциальные соперники хэш-таблиц. В самом деле, они обычно обеспечивают лучшую производительность, чем последовательные списки. В предположении случайного характера появления данных последовательный список, содержащий n элементов, обеспечивает:
Для бинарного дерева поиска обе операции имеют сложность O(log n), что намного лучше, чем O(n) для больших n (вспомните, что для нотации "О-большое" не имеет значения основание алгоритма). Проанализируем эффективность работы полного бинарного дерева, которое определяется тем, что для любого его узла оба поддерева, выходящие из узла, имеют одну и ту же высоту h:
(рис 8.16) Полное бинарное дерево
Нетрудно видеть, при помощи индукции по высоте h, что число узлов n в полном дереве высоты h равно $$2^h – 1$$. Как следствие, $$h = \log_2(n+1)$$. В полном дереве как поиск, так и вставка, используя приведенные ниже алгоритмы, выполняются за время O(log n), начиная работу в корне и следуя нисходящим путем к
Конечно, большинство практических бинарных деревьев не являются полными. Если не повезет при вставке, то производительность может быть столь же плоха, как и для последовательного списка – O(n). К этому добавляются
(рис 8.17) Схемы бинарных деревьев поиска, являющиеся причиной поведения O(N)
При случайном порядке вставки бинарные деревья поиска остаются достаточно близкими к полным деревьям с поведением близким к O(log n). Можно гарантировать выполнение операций поиска, вставки и удаления за время O(log n), если пользоваться специальными вариантами таких деревьев –
Приведем рекурсивную функцию поиска в бинарном дереве поиска (эта и следующая функция добавлены в класс, реализующий бинарные деревья поиска):
has (x: G): BOOLEAN
— Есть ли x в каком-либо узле?
require
argument_exists: x /= Void
do
if x ~ item then
Result := True
elseif x < item then
Result := (left /=Void) and then left.has (x)
else — x > item
Result := (right /= Void) and then right.has (x)
end
end
Алгоритм имеет сложность O(h), где h –
В этом варианте приводится простая нерекурсивная версия алгоритма:
has1 (x: G): BOOLEAN
— Есть ли x в каком-либо узле?
require
argument_exists: x /= Void
local
node: BINARY_TREE [G]
do
from
node := Current
until
Result or node = Void
invariant
— x не находится в вышерасположенных узлах на нисходящем пути от корня
loop
if x < item then
node := left
elseif x > item then
node := right
else
Result := True
end
variant
— (Высота дерева) – (Длина пути от корня к узлу)
end
end
Для вставки элемента можно использовать следующую рекурсивную процедуру:
put (x: G)
— Вставка x, если он не присутствует в дереве.
require
argument_exists: x /= Void
do
if x < item then
if left = Void then
add_left (x)
else
left.put (x)
end
elseif x > item then
if right = Void then
add_right (x)
else
right.put (x)
end
end
end
Отсутствие ветви else во внешнем if отражает наше решение не размещать дублирующую информацию. Как следствие, вызов put с уже присутствующим значением не имеет эффекта. Это корректное поведение ("не жучок, а свойство"), о чем и уведомляет заголовочный комментарий. Некоторые пользователи могут, однако, предпочитать другой API с предусловием, устанавливающим not has(x).
Возникает естественный вопрос: как написать процедуру удаления – remove(x:G)? Это не так просто, поскольку нельзя просто удалить узел, содержащий x, если только это не лист дерева. Удаление листа сводится к обнулению одной из ссылок – left или right. Удаление произвольного узла приводило бы к нарушению инварианта бинарного дерева поиска.
Что следует сделать, так это реорганизовать дерево, перемещая узлы, лежащие в основании узла с найденным значением x, так, чтобы сохранить истинность инварианта.
В удаляемый узел нужно поместить элемент дерева, лежащий ниже удаляемого элемента. Есть два кандидата на эту роль, позволяющие сохранить истинность инварианта:
Если перемещаемый элемент является
(рис 8.18) Ранее построенное дерево
Предположим, что удаляется remove (35). Тогда в корень можно поместить либо элемент 23 (из
Подобно
Напишите процедуру remove(x:G), которая удаляет элемент x, если он присутствует в дереве, сохраняя инвариант.
Прежде чем исследовать теоретические основы рекурсивного программирования, полезно познакомиться еще с одним приложением, а точнее – с целым классом приложений, для которого рекурсия является естественным инструментом: алгоритмами перебора с возвратом. В имени отражена основная идея алгоритма: отыскивается решение некоторой проблемы, последовательно перебираются возможные пути; всякий раз, когда решение на данном пути заходит в тупик, происходит возврат назад к предыдущей развилке, из которой не все возможные пути были исследованы. Процесс заканчивается успешно, если на одном из путей достигается решение задачи. Неуспех в решении возникает тогда, когда ни на одном пути решение не получено или достигнут лимит времени, отведенный на поиск решения.
Перебор с возвратами применим к задаче, если каждое ее потенциальное решение может рассматриваться как последовательность выборов.
При необходимости достижения некоторой цели путешествия в незнакомом городе как к последней надежде можно прибегнуть к перебору с возвратом. Скажем, Вы находитесь в точке А (главная станция Цюриха) и хотите добраться до точки В (между главными зданиями ЕТН и Университета Цюриха):
(рис 8.19) Испытания и перебор с возвратами
Не имея карты и по застенчивости не отваживаясь спросить дорогу к цели, вы решили исследовать прилежащие улицы и проверять после каждой попытки, не достигнута ли цель (предполагается, что у вас есть фотография конечной точки). Вы знаете, что цель расположена на востоке, так что во избежание зацикливания все западно-ориентированные сегменты игнорируются.
На каждом этапе вы проверяете отрезки улиц, начиная с севера и двигаясь по часовой стрелке. Первая попытка приводит в точку 1. Здесь вы понимаете, что это не отвечает вашей цели, так как далее все возможные пути ведут на запад, то есть это тупик и нужно возвращаться назад в исходную точку А. Далее вы испытываете следующий выбор, приводящий в 2. Здесь есть несколько возможностей, и вначале вы проверяете путь, ведущий в 3, который оказывается тупиком, так что приходится вернуться в точку 2.
Если все "правильные" (не ведущие на запад) пути в 2 были исследованы и приводили к тупикам, то из 2 пришлось бы вернуться в точку А. Но в данной ситуации из 2 есть еще не исследованный выбор, ведущий в точку 4.
Процесс продолжается аналогичным образом, вы можете дополнить его самостоятельно, используя приведенную карту. Возможно, это не лучшая стратегия для путешествия в незнакомом городе, но иногда она может быть единственно возможной. Более важно, что она представляет общую схему метода "проб и ошибок", характерную для программирования перебора с возвратами. Схема может быть описана с помощью рекурсивной процедуры:
find ( p: PAT H): PATH
— Решение, если оно существует, начинающееся в P.
require
meaningful: p /= Void
local
c: LIST [CHOICE]
do
if p.is_solution then
Result := p
else
c := p.choices
from c.start until
(Result /= Void) or c.after
loop
Result := find ( p + c)
c.forth
end
end
end
Здесь применяются следующие соглашения. Выборы на каждом шаге описываются типом CHOICE (во многих ситуациях для этой цели можно использовать тип INTEGER). Есть также тип PATH, но каждый путь path – это просто последовательность выборов, и p + c – это путь, полученный присоединением c к p. Мы идентифицируем решение с путем, приводящим к цели, так что find возвращает PATH. По соглашению, если find не находит решения, то возвращается void. Запрос is_solution позволяет выяснить, найдено ли решение. Список выборов – p.choices, доступных из p, является пустым списком, если p – это тупик.
Для получения решения достаточно использовать find(p0), где p0 – начальный пустой путь.
Как обычно, Result инициализируется значением Void. Если в вызове find(p) ни один из рекурсивных вызовов на возможных расширениях p + c не вырабатывает решения (в частности, если таких расширений вообще нет, поскольку p.choices пусто), то цикл завершится со значением c.after, и тогда find(p) вернет значение Void. Если это был начальный вызов find(p0), то процесс завершается, не достигнув положительного результата, в противном случае рекурсивно включается следующий вызов, пока не будет получен результат или не будут перебраны все возможности.
Если один из вызовов находит, что p является решением, то p возвращается в качестве результата, и, подымаясь вверх по цепочке вызовов, результат возвращается, поскольку Result /= Void является условием выхода.
Рекурсия дает четкую основу для управления такой схемой. Это естественный способ выразить природу
p может быть атрибутом, если мы добавим p:= p+x перед рекурсивным вызовом и p:= p.head после него (где head вырабатывает копию последовательности с удаленным последним элементом). Мы разработаем общий каркас, позволяющий безопасно выполнять такую оптимизацию.Общая схема перебора с возвратом требует некоторой настройки для практического использования. Прежде всего, в том виде, как она приведена, не гарантируется завершаемость. Чтобы убедиться в завершаемости любого выполнения, необходимо одно из двух:
Дополнительно практическая реализация обычно может обнаруживать эквивалентность некоторых путей, например, для ситуации, представленной на рисунке:
(рис 8.20) Путь с циклом
Пути [1, 2, 3, 4], [1, 2, 3, 4, 2, 3, 4], [1, 2, 3, 4, 2, 3, 4, 2, 3, 4] и так далее являются эквивалентными. Пример, демонстрирующий нахождение маршрута без циклов, состоял в важной рекомендации – "никогда не уезжайте на запад, молодой человек". Конечно, этот совет не может служить общей рекомендацией и связан лишь с конкретной проблемной ситуацией. Чтобы справиться с циклом, необходимо сохранять информацию о ранее посещенных точках и игнорировать любой путь, ведущий к такой точке.
Для любой задачи, в решении которой может помочь перебор с возвратами, может помочь и построение модели в виде дерева. При установке соответствия будем использовать деревья, где каждый узел будет иметь произвольное число потомков, обобщая концепции, рассмотренные при определении бинарных деревьев. Путь в дереве (последовательность узлов) соответствует пути в алгоритме перебора (последовательность выборов). Дерево в примере с маршрутами представлено на рис 8.21.
(рис 8.21) Дерево путей при переборе с возвратами
Мы можем представлять всю карту города подобным образом: узлы отражают местоположение указанных на карте точек, дуги представляют отрезки улиц, соединяющих точки. В результате получается граф. Граф может быть деревом только в том случае, если в нем нет циклов. Если граф не является деревом, то на его основе можно построить дерево, называемое
Для такого представления нашей задачи в виде дерева:
is_solution, адаптированное для применения к узлам);В нашем примере этот порядок приведет к посещению узлов А, 1, 2, 3, 4.
Это соответствие указывает, что "Префиксный обход" и "Перебор с возвратами" основаны на одной и той же идее: всякий раз, когда мы рассматриваем возможный путь, мы разматываем все его возможные продолжения – все поддеревья узла, – прежде чем обращаемся к любому альтернативному выбору на уровне, представляющем непосредственных потомков узла. Например, если А на предыдущем рисунке будет иметь третьего потомка, то обход не будет его рассматривать, прежде чем не обойдет все поддеревья 2.
Единственное свойство, отличающее алгоритм перебора с возвратами от префиксного обхода, состоит в том, что он останавливается сразу же, как только найден узел, удовлетворяющий выбранному критерию.
Префиксный порядок был определен для бинарных деревьев следующим образом: посетить корень, затем обойти
Интересным примером стратегии перебора, также естественным образом моделируемой деревом, является минимаксная техника, применяемая в играх, таких как шахматы. Она применима, если справедливы следующие предположения:
(mb – mw) + 3 * (kb – kw), где mb и mw – число простых шашек соответственно у Макса и Минни, а kb и kw – число дамок, каждая из которых оценивается в три раза выше, чем простая шашка. Конечно, в хорошей Минни старается найти позицию, минимизирующую оценочную функцию, а Макс старается ее максимизировать.
(рис 8.22) Дерево игры
Каждый игрок использует минимаксную стратегию для выбора в текущей позиции одного из возможных ходов. Дерево моделирует игры такого вида, последовательные уровни дерева представляют ходы каждого из игроков.
На рисунке все начинается с позиции, где ход должна сделать Минни. Цель стратегии – позволить Минни среди ходов, доступных в данной позиции (три на рисунке), выбрать тот, который гарантирует лучший результат. В данном случае она старается получить минимальное значение оценочной функции на
Предположение о симметричности – основа для
| М1 | Значение листа является результатом применения оценочной функции к соответствующей позиции игры. |
| М2 | Значение внутреннего узла, задающего ход Макса, является максимумом из значений детей этого узла. |
| М3 | Значение внутреннего узла, задающего ход Минни, является минимумом из значений детей этого узла. |
Можно видеть, что значение в каждом узле является минимумом (для уровней 1 и 3) или максимумом (на уровне 2) значений сыновей узла. Оптимальный ход для Минни, обеспечивающий значение -7, состоит в выборе хода С.
Перебор с возвратами вполне подходит для
(рис 8.23) Дерево игры с оценками
Следующий алгоритм, являясь вариацией ранее приведенной общей схемы перебора, реализует эту идею. Он представлен функцией value – гарантированное значение из начальной позиции p, и choice – начальный выбор, приводящий к этому значению. Аргумент l задает уровень, на котором появляется позиция p в ходе игры. Первый ход из этой позиции, возвращаемый как часть результата, является ходом Минни (как на рисунке), если l нечетно, и ходом Макса, если l четно.
minimax ( p: POSITION; l: INTEGER): TUPLE [value, choice: INTEGER]
— Оптимальная стратегия(value + choice) на уровне l, начиная с позиции p.
local
next: TUPLE [value, choice: INTEGER]
do
if p.is_terminal (l ) then
Result := [value: p.value; choice: 0]
else
c := p.choices
from
Result := worst (l )
c.start
until c.after loop
next := minimax (p.moved (c.item), l + 1)
Result := better (next, Result, l )
end
end
end
Для представления результата используется кортеж, задающий значение и выбор.
Дополнительные функции worst и better дают возможность переключаться между Максом и Минни – игрок минимизирует на каждом нечетном ходе и максимизирует на четном.
worst (l: INTEGER): INTEGER
— Худшее возможное значение для игрока на уровне l.
do
if l \\ 2 = 1 then Result := Max else Result := Min end
end
better (a, b: TUPLE [value, choice: INTEGER]; l: INTEGER):
TUPLE [value, choice: INTEGER]
- Лучшее из a и b, в соответствии с их значениями для игрока на уровне l.
do
if l \\ 2 = 1 then
Result := (a.value < b.value)
else
Result := (a.value > b.value)
end
end
Для определения худшего значения для каждого игрока вводятся две константы Max и Min (самое большое и самое малое значения).
Функция POSITION:
is-terminal указывает, что в данной позиции нет ходов, подлежащих исследованию;value дает значение оценочной функции (запрос value может иметь предусловие is-terminal);choices, где каждый выбор представлен целым, задающим допустимый ход;i является таким выбором, moved(i) дает позицию, полученную в результате применения соответствующего хода к текущей позиции.Простейший способ убедиться, что алгоритм завершается, состоит в ограничении глубины перебора, задав Limit – предельное число уровней. Вот почему is-terminal в том виде, как она задана, включает уровень l как аргумент. Она может быть записана в виде:
is_terminal (l: INTEGER): BOOLEAN
— Следует ли исследовать уровень l или остановиться на текущей позиции?
do
Result := (l = Limit) or choices.is_empty
end
На практике используются более сложные критерии остановки, например, алгоритм может сохранять затраты процессорного времени и останавливаться, когда достигнуто ограничение по времени.
Для выполнения мы вызываем initial задает начальную позицию игры. Уровень 1 указывает на то, что ход принадлежит Минни.
Минимаксная стратегия всегда выполняет полный обход дерева допустимых ходов игры. Можно существенно улучшить эффективность работы, применяя оптимизацию, известную как "альфа-бета-стратегия", которая позволяет пропускать в процессе обхода целые поддеревья, "бесполезные" для достижения цели игры. Это прекрасная идея, заслуживающая внимания не только как "умное" решение, но и как пример усовершенствования рекурсивного алгоритма.
Альфа-бета имеет смысл только в предположениях, сделанных для
Идея пропуска поддерева основана на том, что игрок на уровне l +1 обнаруживает, что нет необходимости продолжать анализировать поддерево, поскольку он может получить на нем лучший результат, чем уже полученный. Но для его противника этот результат будет худшим, чем тот, что уже гарантирован ему на уровне l, и потому противник никогда не выберет это поддерево (напомним, что игроки всегда выбирают оптимальный ход с точки зрения принятой стратегии).
Предыдущий пример позволяет проиллюстрировать идею альфа-бета-стратегии. Рассмотрим ситуацию в процессе работы минимаксного алгоритма, когда исследовано несколько начальных узлов.
(рис 8.24) Пропуск полезных поддеревьев
Мы находимся в процессе вычисления значения (максимума) для узла Ма1 и, как часть этой цели, вычисления значения (минимум) для узла Мi2. Анализ первого поддерева для Ма1 с корнем в Мi1 позволил определить частичный максимум для Ма1, равный 8 (на рисунке он отмечен знаком вопроса, сигнализирующим, что вычисления еще не завершены). Это означает для Макса, что 8 он себе обеспечил и на меньшее не согласится. При анализе поддерева с корнем Мi2 мы пришли к поддереву Ма2 (к листу в данном конкретном случае, но вывод применим к любому поддереву), где значение равно 6, так что в любом случае Минни не выберет в Мi2 значение, большее 6, а тогда ясно, что дальнейший анализ бесполезен, поскольку не окажет влияния на значение в вышестоящем узле Ма1. Так что, как только найдено значение 6 для Ма2, альфа-бета-стратегия прекратит анализ поддерева с корнем в Мi2.
Эта оптимизация интересна сама по себе, но она дает и хорошую возможность отточить наши навыки рекурсивного программирования. Попытайтесь сами построить соответствующий метод, не заглядывая в решение, которое приводится ниже.
Адаптируйте минимаксный алгоритм, приведенный ранее, так, чтобы он использовал стратегию "альфа-бета" для отбраковки бесполезных поддеревьев.
Расширение алгоритма достаточно просто. Методу понадобится еще один аргумент, задающий значение (если оно существует), которое для противника гарантированно находится на уровне непосредственно выше. Вот минимаксная процедура с добавленной альфа-бета стратегией:
alpha_beta ( p: POSITION; l: INTEGER; guarantee: INTEGER):
TUPLE [value, choice:
INTEGER]
— Оптимальная стратегия(value + choice) на уровне l, начиная с позиции p.
— Нечетный уровень минимизирует, четный – максимизирует.
local
next: TUPLE [value, choice: INTEGER]
do
if p.is_terminal (l ) then
Result := [value: p.value; choice: 0]
else
c := p.choices
from
Result := worst (l )
c.start
until c.after or better (guarantee, Result, l – 1) loop
next := minimax ( p.moved (c.item), l + 1), Result)
Result := better (next, Result, l )
end
end
end
Каждый игрок теперь останавливает анализ своего выбора, если противник может получить гарантированно лучший результат.
better определена без предусловия, то это означает, что она может принимать и уровень 0, так что допустимо передавать ей l - 1. Мы могли бы передавать и l + 1, поскольку вариантом better(guarantee, Result, l-1) является better(Result, guarantee, l), благодаря симметрической природе стратегии.Рекурсивный вызов передает как "guarantee" на следующий уровень лучший Result, полученный на текущем уровне. Как следствие, альфа-бета останавливает обход узлов детей, когда срабатывает новый переключатель выхода better(guarantee, Result, l-1). Такая ситуация никогда не встретится для первого сыновнего узла, поскольку Result инициализирован значением worst.
(рис 8.1)
Смеющаяся корова, изображенная на фирменном жетоне "Смеющаяся Корова", носит в качестве сережек фирменные жетоны, на которых, я подозреваю, но зрение не позволяет убедиться в правильности моего предположения, изображена корова с фирменными жетонами, на которых изображена …
Эта реклама, появившаяся в 1921 году, все еще хорошо работает, являясь примером структуры, определенной рекурсивно в следующем смысле:
"Рекурсия" – использование рекурсивного определения – широко применяется в программировании: она позволяет элегантно определять синтаксические структуры; мы также познакомимся с рекурсивно определенными структурами данных и рекурсивными процедурами.
Мы будем использовать термин "рекурсивный" как сокращение "рекурсивно определенный" – рекурсивная грамматика,
При рассмотрении свойств рекурсивно определенного понятия будем применять рекурсивные доказательства – обобщающие индуктивные доказательства, использующие целые числа для индуктивного шага.
Рекурсия является прямой, если определение $$А$$ ссылается на экземпляр $$А$$, и косвенной, если для $$1 <= i < n$$ (для некоторого $$n >=2$$) определение каждого $$A_i$$ ссылается на $$A_{i+1}$$, а определение $$A_n$$ ссылается на $$A_1$$.
В этой лекции нас будут интересовать такие понятия, для которых рекурсивные определения естественны, элегантны и удобны. Примеры будут включать рекурсивные программы, рекурсивные синтаксические определения, рекурсивные структуры данных. Мы также получим некоторое представление о рекурсивных доказательствах.
Один из классов
В этот момент могут возникнуть вполне обоснованные сомнения – а есть ли смысл в рекурсивных определениях, как можно определить понятие через само понятие, "масло масляное"?
Вы вправе сомневаться. Не все рекурсивные определения хороши для определения чего-либо. Когда вас просят дать характеристику кому-нибудь, а вы отвечаете: "Света? Ну, это просто Света, что еще можно сказать!" – то вы не много нового сказали. Так что следует позаботиться о критериях, гарантирующих полезность определения, даже если оно рекурсивно.
Прежде чем мы это сделаем, позвольте убедиться прагматичным путем, ознакомившись с несколькими типичными примерами, когда рекурсия очевидно полезна и осмысленна. Это придаст нам твердую убежденность, большую, чем просто вера, основанная на надеждах и молитвах, что рекурсия – это практически полезный способ определять грамматики, структуры данных и алгоритмы. После чего настанет время для подходящего математического обоснования рекурсивных определений.
С введением универсальности мы получаем возможность определять тип как:
| Т1 | класс, не являющийся универсальным, такой как INTEGER или STATION; |
| Т2 | родовое порождение в форме C[T], где С – Т – тип. |
Это определение рекурсивно, оно просто означает, что, при наличии ARRAY и LIST, правильными классами также будут:
INTEGER, STATION и им подобные в соответствии с определением Т1;Т2, прямые родовые порождения: ARRAY[INTEGER], LIST[STATION] и так далее.Т2: ARRAY[LIST[INTEGER]], ARRAY[ARRAY [LIST[STATION]]] и так далее – родовые порождения любого уровня вложенности.Используя подобный прием, можно дать ответ на упражнение из первой лекции, где требовалось дать определение алфавитному (лексикографическому) порядку.
Рассмотрим подмножество Eiffel с двумя видами операторов.
variable:= expression, рассматриваемое здесь как терминальное и далее не уточняемое.then (без else) для простоты.Грамматика, определяющая язык, такова:
$$\text{Оператор }\triangleq\text{ Присваивание | Условный}\\\text{Условный }\triangleq}\text{ if Условие then Оператор end }$$Для наших непосредственных целей будем полагать, что "Условие" является терминальным понятием. Это определение грамматики очевидно рекурсивно, поскольку определение "Оператор" включает "Условный", а его определение, в свою очередь, включает "Оператор". Но так как здесь присутствует нерекурсивная часть определения – "Присваивание", то в целом грамматика четко определяет правильные конструкции языка:
if c then a end;if c1 then if c2 then a end end, if c1 then if c2 then if c3 then a end end end и так далее.Рекурсивные грамматики на самом деле являются незаменимым средством для описания любого языка, который, как все распространенные языки, поддерживает вложенные структуры.
Класс STOP представляет понятие остановки для линии метро:
class STOP create
…
feature
next: STOP
— Следующая остановка на той же линии.
…Другие компоненты, здесь опущенные (см.6.5)
end
Наивная интерпретация будет предполагать, что каждый экземпляр STOP содержит экземпляр STOP, который, в свою очередь, содержит остановку и так до бесконечности, как в схеме со Смеющейся коровой. Это и в самом деле было бы так, если бы STOP принадлежал развернутым, а не ссылочным типам:
(рис 8.2) Вложенные поля (интерпретация не корректна)
Такое попросту невозможно. Но STOP в любом случае является ссылочным типом, подобно любому классу, определенному как class X… без всяких других квалификаций, так что реальная картина выглядит так:
(рис 8.3) Линия, связанная ссылками
Рекурсия в таком определении структуры данных просто указывает, что каждый экземпляр класса потенциально содержит ссылку на экземпляр того же класса, "потенциально" – поскольку ссылка может иметь значение void, и тогда действие рекурсии прекращается, как для последней остановки на рисунке.
В той же 6-й главе, где рассматривались линии метро, шла речь и о классе PERSON c атрибутом spouse типа PERSON.
Это весьма общая ситуация в определении полезных структур данных, начиная от связных списков до деревьев различного вида (таких как бинарные деревья, изучаемые позже в этой лекции). Определения полезных классов часто включают ссылки на объекты определяемого класса или (
Известная последовательность чисел Фибоначчи обладает многими прекрасными свойствами и появляется во многих приложениях математики и естественных наук. Она имеет следующее определение:
$$F_0=0\\F_1=1\\F_i=F_{i-1}+F_{i-2}\qquad \text{- Для}\;i>1$$Леонардо Фибоначчи из Пизы (1170 – 1250) сыграл ключевую роль в знакомстве Запада с трудами индийских и арабских математиков. Он известен также и собственными исследованиями, лежащими в основании современной математики. Он сформулировал задачу, приводящую к его знаменитой последовательности (которая была известна еще индийским математикам):
Человек получил пару кроликов и поместил их в загон, окруженный со всех сторон стеной. Как много пар кроликов можно получить от этой пары в год, если каждый месяц каждая пара производит новую пару, которая становится продуктивной на втором месяце?
(рис 8.4) Фибоначчи
Решение дает следующее рассуждение. Пары кроликов в месяце $$i$$ включают пары кроликов, уже существующие в предыдущем месяце (кролики не умирают); обозначим их число как $$F_{i-1}$$, плюс потомство, принесенное кроликами, жившими в месяце $$i-2$$ (кролики, появившиеся в месяце $$i-1$$, потомства не приносят). Это и дает приведенную выше формулу, создающую последовательность целых чисел 0, 1, 1, 2, 3, 5, 8 и так далее. Формула приводит к рекурсивной программе, вычисляющей $$F_n$$ для любого $$n$$:
fibonacci (n: INTEGER): INTEGER
— Элемент с индексом n в последовательности Фибоначчи.
require
non_negative: n >= 0
do
if n = 0 then
Result := 0
elseif n = 1 then
Result := 1
else
Result := fibonacci(n – 1)+ fibonacci(n – 2)
end
end
Напишите небольшую программную систему, включающую вышеприведенную рекурсивную функцию и печатающую ее результат. Протестируйте ее для небольших значений n, включая 12, как в оригинальном тексте Фибоначчи.
Функция включает два рекурсивных вызова. То, что это работает, может казаться несколько загадочным (вот почему стоит проверить выполнение функции на нескольких значениях). После изучения этой лекции легитимность таких
Принципиальным аргументом в пользу такого способа записи программы есть то, что она вполне соответствует математическому определению последовательности Фибоначчи. Дальнейшее рассмотрение покажет, что этот факт не столь впечатляющий, поскольку получить нерекурсивную версию также не сложно.
Можете ли вы, не заглядывая в дальнейший текст, написать функцию, вычисляющую N-е
Следующая функция дает тот же результат, что и рекурсивная версия. Проверьте это на нескольких значениях.
fibonacci1 (n: INTEGER): INTEGER
— Элемент с индексом n в последовательности Фибоначчи.
— (Нерекурсивная версия.)
require
positive: n >=1
local
i, previous, second_previous: INTEGER
do
from
i := 1 ; Result := 1
invariant
Result = fibonacci(i )
previous = fibonacci (i – 1)
until i = n loop
i := i + 1
second_previous := previous
previous := Result
Result := previous + second_previous
variant
n – i
end
end
n >= 1, а не n >= 0. Благодаря правилам инициализации previous начинается с 0, что гарантирует начальное выполнение инварианта, так как $$F_0 = 0$$. Переменная second_previous обновляется на каждом шаге цикла и ей не нужно специальной инициализации.Эта версия более удалена от оригинального математического определения, но все же проста и понятна. Заметьте:
Оставим в стороне вкус и эффективность. Если бы мы рассматривали только такие примеры, то необходимость рекурсивных программ была бы далеко не очевидной. Нам необходимы примеры, в которых рекурсия обеспечила бесспорные преимущества, например, за счет того, что ее нерекурсивный аналог был бы значительно сложнее и труднее в понимании. Такие примеры существуют в большом количестве. Одним из них является очаровательная головоломка – "Ханойская башня". В этом примере сконцентрировано много полезных свойств рекурсии, и практически нет не относящихся к делу деталей.
В величественном храме Бенареса, под куполом, отмечающим центр мира, на медной плите установлены три бриллиантовых стержня. Каждый стержень высотой в локоть и тонок, как пчелиная талия. На один из этих стержней в начале мироздания Бог поместил 64 диска из чистого золота. Самый большой диск покоится на медной плите, а остальные, друг друга меньше, создают пирамиду, вздымающуюся к вершине стержня. Это и есть священная башня Брахмы.
Ночью и днем неустанно священники, сменяя друг друга, работают, чтобы перенести священную башню на третий бриллиантовый стержень, не нарушив при этом священных правил, установленных Брахмой. Когда их работа будет закончена, падет башня, падут брахманы и наступит конец мира.
(рис 8.5) Башня Ханоя (должна быть башней Бенареса?) из 9 дисков в начальном состоянии
Несмотря на восточный орнамент, эта история является созданием французского математика Эдуарда Лукаса (подписывающегося как "N. Claus de
Почему коммерчески доступные модели Ханойской башни имеют размеры много меньшие, чем 64 диска?
(Подсказка: игра сопровождается бумажным свертком, на котором дается решение головоломки в форме последовательности ходов; А => C, A => B и т. д.)
Чтобы ответить на этот вопрос, давайте оценим минимальное число ходов $$H_n$$ (ход – это перемещение диска с одного стержня на другой), требуемое для решения задачи. Если задача имеет решение, то нужно перенести n дисков со стержня А на стержень В, используя стержень С как промежуточный. При этом нужно соблюдать правило Будды, запрещающее класть больший диск на меньший. В оригинальной версии n = 64, для небольшой модели n = 9.
Заметим, что для любой стратегии перемещения в некоторый момент необходимо перенести самый большой диск со стержня А на стержень В, а это возможно лишь при условии, что все остальные n -1 дисков в этом момент находятся на диске С в требуемом порядке:
(рис 8.6) Промежуточное состояние
Каково минимальное число ходов, необходимое для достижения этого промежуточного состояния? Необходимо перенести n -1 диск со стержня А на стержень С, не перемещая самый большой диск и используя стержень В как промежуточный. Ввиду симметричности задачи для этого потребуется $$H_{n-1}$$ ходов.
Сразу же по достижении этого состояния можно перенести за один ход самый большой диск с А на В, после чего перенести n – 1 диск с С на В, используя А как промежуточный. Общее количество ходов:
$$H_n=2*H_{n-1}+1$$Учитывая, что $$H_0$$ равно 0, получим:
$$H_n=2^n-1$$Как следствие, нетрудно получить ответ на наш тест. Вспомним, что $$2^{10} = 1024$$, или примерно $$10^3$$, и получим, что число ходов $$2^{64}$$ примерно равно $$1,5 * 10^{19}$$.
Год – это примерно 30 миллионов секунд. Если предположить, что священники Бенареса за секунду выполняют один ход – весьма неплохая скорость для переноса золотого диска, – всю работу они закончат за 500 миллиардов лет, что примерно в 30 раз превосходит оценочный возраст существования нашей вселенной. Даже компьютеру, выполняющему 100 миллионов ходов за секунду, при моделировании этой задачи для переноса дисков потребуется не одна тысяча лет.
Вывод оценки $$H_n$$ был конструктивным, в том смысле, что он дает практическую стратегию для перемещения дисков.
Эта стратегия превращает число ходов $$H_n = 2^n – 1$$ из теоретического минимума в практически достижимую цель. Мы можем записать алгоритм в виде рекурсивной процедуры, входящей в класс
hanoi (n: INTEGER; source, target, other: CHARACTER)
— Перенос n дисков из source на target,
— используя other как промежуточное хранилище,
— в соответствии с правилами игры "Ханойская башня"
require
non_negative: n >= 0
different1: source /= target
different2: target /= other
different3: source /= other
do
if n > 0 then
hanoi (n–1, source, other, target)
move (source, target)
hanoi (n–1, other, target, source)
end
end
По соглашению стержни представляются символами – 'A', 'B', 'C'. Другое соглашение, принятое в этой лекции (уже использованное в предыдущих примерах), состоит в подсветке рекурсивных ветвей кода, – процедура hanoi содержит два таких участка.
Базисная операция move(source, target) перемещает один диск с вершины стержня source на вершину target. Предусловие устанавливает, что на source должен находиться, по крайней мере, один диск, а на target диска либо нет, либо диск в вершине имеет больший размер, чем перемещаемый диск. Запишем move как процедуру, выводящую на консоль инструкцию по перемещению диска:
move (source, target: CHARACTER)
— Инструкция по перемещению диска с source на target.
do
io.put_character (source)
io.put_string (" to ")
io.put_character (target)
io.put_new_line
end
Напишите систему с корневым классом hanoi и move. Проверьте их работоспособность на примерах.
Например, выполните вызов
hanoi (4, 'A', 'B', 'C')
В результате должна быть напечатана последовательность из пятнадцати ($$2^4 – 1$$) ходов:
| A на C | B на C | B на A |
| A на B | A на C | C на B |
| C на B | A на B | A на C |
| A на C | C на B | A на B |
| B на A | C на A | C на B |
Эта последовательность ходов успешно переносит диски с А на B в полном соответствии с правилами игры.
Один из способов анализа рекурсивного решения – процедуры hanoi – состоит в том, чтобы рассматривать перемещение n – 1 дисков, как один обобщенный ход. В этом случае мы могли бы начать перемещение с этого хода (с А на С):
(рис 8.7) Начальный глобальный ход Фибоначчи
После этого можно сделать обычный ход, перенеся самый большой диск на целевой стержень, а затем снова выполнить обобщенный ход, который легален, поскольку все диски обобщенного хода меньше, чем диск, уже лежащий на целевом стержне.
Конечно, это фиктивное рассмотрение, поскольку правилами разрешается перенос только одного диска за один ход, но перемещая n – 1 диск, можно применять ту же технику, зная, что целевой стержень либо пуст, либо содержит диски большего размера. Так можно рекурсивно выполнять перемещения, уменьшая каждый раз значение n. Когда же n становится равным нулю, то делать ничего не нужно.
Не стоит легкомысленно относиться к примеру с Ханойской башней. Это решение служит прекрасной моделью для многих рекурсивных программ с важными практическими приложениями. Простота алгоритма является результатом использования двух рекурсивных вызовов, и это делает эту задачу идеальной для изучения свойств рекурсивных алгоритмов, к чему мы вернемся чуть позже в этой лекции.
В предыдущих лекциях мы рассматривали управляющие структуры языка программирования как технику, используемую для решения сложных задач.
(рис 8.8)
Что можно сказать о рекурсивном решении? К кому нужно обращаться? Ответ – к себе! Возможно – несколько раз (как в случае с Ханойской башней и многих других)!
Зачем обращаться к другим, если я доверяю себе (по крайней мере, я так думаю)?
Теперь мы знаем, что эта стратегия не так глупа, как может казаться с первого раза. Я прошу себя решить ту же задачу, но на подмножестве исходных данных или на нескольких таких подмножествах. Тогда я могу справиться с задачей, если удастся
Такова идея рекурсии, рассматриваемая как стратегия решения сложной задачи. Она связана с некоторыми предыдущими стратегиями.
Если Ханойская башня является квинтэссенцией рекурсивной процедуры, то бинарные деревья являются квинтэссенцией
Бинарное дерево над G, для произвольного типа данных G, задается конечным множеством элементов, называемых узлами, каждый из которых содержит значение типа G. Узлы, если они есть, разделяются на три непересекающихся подмножества:
Все это просто выразить в каркасе класса, не включающем методов:
class BINARY_TREE [G] feature
item: G
left, right: BINARY_TREE[G]
end
Ссылка void указывает на пустое дерево. Проиллюстрируем бинарное дерево над целыми (рис 8.9).
Форма "Ветвления" – это наиболее общий стиль представления бинарных деревьев, но не единственный: возможно представление в форме вложенности, которое для данного примера выглядит так (рис 8.10).
Определение бинарного дерева явно допускает, что дерево может быть пустым. Без этого, конечно, рекурсивное определение приводило бы к бесконечной структуре, в то время как бинарные деревья, что также предписано определением, являются конечными структурами данных.
(рис 8.9) Соглашение: Бинарное дерево (представленное "ветвлением")
(рис 8.10) Бинарное дерево (вложенное представление)
Если бинарное дерево не пусто, то оно всегда имеет корень и может не иметь поддеревьев, иметь только левое или только правое поддерево или иметь оба поддерева.
Любой узел бинарного дерева сам рассматривается как бинарное дерево. Достаточно взглянуть на два последних рисунка. Узел, помеченный как 35, задает полное дерево, 23 – его
Большинство методов класса, определяющего рекурсивную структуру класса, будут строиться рекурсивно с учетом рекурсивного определения данных. Простым примером является метод, подсчитывающий число узлов бинарного дерева. В пустом дереве число узлов равно нулю, для непустого дерева число узлов равно сумме трех значений: для корня и числа узлов соответственно левого и правого поддеревьев. Нетрудно записать это наблюдение в виде рекурсивной функции, входящей в класс BINARY_TREE.
count: INTEGER
— Число узлов.
do
Result := 1
if left /= Void then Result := Result + left.count end
if right /= Void then Result := Result + right.count end
end
Заметьте схожесть этой функции с процедурой Hanoi.
Дети (непосредственные потомки) узла – сами узлы – являются корневыми узлами левого и правого поддеревьев:
(рис 8.11) Бинарное дерево (представление "ветвлением")
Если С – сыновний (дочерний) узел В, то В – родитель С. Более точно мы можем сказать, что В является "родителем" С, благодаря следующему результату:
Теорема кажется очевидной, но мы докажем ее, что даст нам возможность познакомиться с рекурсивными доказательствами.
Рекурсивное доказательство теоремы о единственном родителе в значительной степени отражает рекурсивное определение бинарного дерева.
Если бинарное дерево BT пусто, то теорема выполняется. В противном случае бинарное дерево имеет корень и два непересекающихся бинарных дерева, о которых мы можем предположить – "рекурсивная предпосылка", – что они оба удовлетворяют теореме. Это следует из определений "бинарного дерева", "ребенка" и "родителя", так что узел С может иметь родителя Р в ВТ только одним из трех возможных случаев:
| Р1 | Р является корнем ВТ, а С является корнем либо левого, либо правого поддерева; |
| Р2 | они оба принадлежат |
| Р3 | они оба принадлежат правому поддереву, и Р является родителем С в этом поддереве. |
В случае Р1 узел С по гипотезе рекурсивности, являясь корнем, не имеет родителей в своем поддереве, так что у него есть единственный родитель – корень всего дерева ВТ. В случаях Р2 и Р3, опять-таки по гипотезе рекурсивности, Р был единственным родителем С в соответствующем поддереве, и это остается верным и во всем дереве.
Любой узел С, отличный от корня, удовлетворяет одному из трех рассмотренных вариантов и, следовательно, имеет в точности одного родителя. Только если С является корнем дерева, он не будет соответствовать рассмотренным ситуациям и, как следствие, у него не будет родителей, что и завершает доказательство теоремы.
Подобные рекурсивные доказательства полезны, когда необходимо установить, что некоторое свойство выполняется для всех экземпляров рекурсивно определенного понятия. Структура доказательства определяется структурой определения.
Эта схема применима в целом для всех рекурсивно определяемых понятий. Мы увидим ее применение к рекурсивно определенной процедуре hanoi.
Интересный пример бинарного дерева можно получить, моделируя выполнение процедуры hanoi, например, для трех дисков. Каждый узел содержит аргументы данного вызова, а левое и правое поддерево соответствуют рекурсивным вызовам:
(рис 8.12) Выполнение Hanoi, рассматриваемое как бинарное дерево
Добавление операции move позволило бы реконструировать последовательность операций. Формально мы выполним это позднее.
Этот пример высвечивает связь межу рекурсивными алгоритмами и hanoi, выполнение моделировалось бы не бинарным деревом, а деревом общего вида.
Еще о свойствах бинарных деревьях и о терминологии
Как отмечалось, узел бинарного дерева может иметь:
(рис 8.13) Копия ранее приведенного дерева
Определим восходящий путь в бинарном дереве как последовательность из нуля или более узлов, где любой узел последовательности является родителем предыдущего узла, если таковой имеется. В нашем примере узлы с метками 60, 78, 54 формируют восходящий путь. Справедливо следующее свойство, являющееся следствием теоремы о единственном родителе.
Доказательство. Рассмотрим произвольный узел С бинарного дерева. Построим восходящий путь, начинающийся в С. В соответствии с теоремой о единственном родителе такой путь определяется единственным образом. Если путь конечен, то заканчиваться он должен в корне дерева, поскольку любой другой узел имеет родителя, и следовательно, построение восходящего пути могло бы быть продолжено. Для завершения доказательства необходимо показать, что все пути конечны. Единственный способ построения бесконечного пути (учитывая, что число узлов бинарного дерева по определению конечно) состоит в том, что путь включает цикл. Если некоторый узел n встретится дважды, то он встретится сколь угодно много раз, так что бесконечный путь должен содержать подпоследовательность в форме n... n. Но это означает, что n появляется в своем собственном левом или правом поддереве, что невозможно по определению бинарных деревьев.
Рассмотрение нисходящих путей позволяет установить следующий факт, как следствие предыдущей теоремы.
Весом бинарного дерева является максимальное число узлов среди всех нисходящих путей от корня к
Это понятие можно определить рекурсивно, следуя снова рекурсивной структуре определения. Вес пустого дерева равен нулю. Вес непустого дерева равен 1 плюс максимум (рекурсивно) из весов левого и правого поддеревьев. Мы можем добавить соответствующую функцию в класс BINARY_TREE:
height: INTEGER
— Максимальное число узлов нисходящего пути.
local
lh, rh: INTEGER
do
if left /= Void then lh := left.height end
if right /= Void then rh := right.height end
Result := 1 + lh.max (rh)
end
Здесь рекурсивное определение адаптируется к соглашению, принятому для класса, который рассматривает только непустые поддеревья. Отметьте опять-таки схожесть с hanoi.
В классе BINARY_TREE пока определены только три компонента, все они являются запросами: item, left и right. Мы можем добавить процедуру создания:
make (x: G)
— Инициализация item значением x.
do
item := x
ensure
set: item = x
end
Добавим в класс команды, позволяющие изменять поддеревья, и значение в корне:
add_left (x: G)
— Создать левого сына со значением x..
require
no_left_child_behind: left = Void
do
create left.make (x)
end
add_right … Аналогично add_left…
replace (x: G)
— Установить значение корня равным x.
do item := x end
На практике удобно специфицировать replace как команду-присваиватель для соответствующего запроса, изменив объявление запроса следующим образом:
item: G assign replace
Это позволяет писать bt.item:= x вместо bt.item.replace(x).
Нет ничего удивительного в том, что, благодаря рекурсивной определенности, с бинарным деревом связываются многие height является одним из таких примеров. Приведем сейчас и другие. Предположим, что требуется напечатать все значения элементов, связанных с узлами дерева. Следующая процедура, добавленная в класс, выполняет эту работу:
print_all
— Печать значений всех узлов.
do
if left /= Void then print_all (left)end
print (item)
if right /= Void then print_all (right) end
end
print (доступная всем класса через общего родителя ANY), которая печатает подходящее представление значения типа G – родового параметра в классе BINARY_TREE[G].Заметьте, структура print_all идентична структуре hanoi.
Хотя роль процедуры print_all состоит в печати всех значений, ее алгоритмическая схема не зависит от специфики операции, выполняемой над узлами дерева (print в данном случае). Процедура является примером обхода бинарного дерева: алгоритма, выполняющего однократно некоторую операцию над каждым элементом структуры данных в некотором заранее предписанном порядке обхода узлов. Обход является вариантом итерации.
Для двоичных деревьев наиболее часто используются три порядка обхода дерева, которые иногда называют соответственно инфиксным, префиксным и постфиксным порядками обхода.
В этих определениях "посетить" означает выполнение операции над отдельным узлом, такой как print в процедуре print_all; "обход" означает либо рекурсивное применение алгоритма для поддерева, либо отсутствие каких-либо действий, если поддерево пусто.
Префиксный порядок обхода, так же как и другие способы обхода, идущие, насколько это возможно, в глубину поддерева, называются также обходами "вначале в глубину", например, "самый левый в глубину".
Процедура print_all является иллюстрацией инфиксного способа обхода дерева. Достаточно просто записываются и другие способы обхода, например, для постфиксного обхода тело процедуры post имеет вид:
if left /= Void then post (left) end
if right /= Void then post (right) end
visit (item)
Здесь visit является операцией над узлом, такой как print.
visit. Чтобы избежать этого, можно рассматривать операцию как аргумент метода обхода. Это возможно сделать в Eiffel, используя механизм агентов, описанный в последующих лекциях.В качестве еще одной иллюстрации инфиксного обхода рассмотрим снова бинарное дерево выполнения hanoi для n = 3, где узлы уровня 0 опущены, поскольку не представляют интересной информации в данном случае.
(рис 8.14) Выполнение Hanoi в инфиксном порядке обхода
Процедура hanoi является матерью всех инфиксных обходов: обход левого дерева, если оно есть, посещение корня, обход правого поддерева, если оно есть. При посещении каждого узла выполняется операция move(source, target). Инфиксный порядок дает нужную последовательность ходов: A B, A C, B C, A B, C A, C B, A B.
Для произвольного бинарного дерева процедура print_all, реализующая инфиксный порядок, печатает значения узлов в произвольном порядке. Если же порядок важен для нас, то необходимо переходить к бинарным деревьям поиска.
Множество G, над которым определено общее бинарное дерево, может быть любым множеством. Для бинарных деревьев поиска предполагается, что на множестве G задано полное отношение порядка, позволяющее сравнивать любые два элемента G, задавая a < b, такое, что истинно одно из трех отношений: a < b, b < a, a ∼ b. Примерами таких множеств могут служить INTEGER и REAL с отношением порядка <, но G может быть любым вполне упорядоченным множеством.
Как обычно, мы пишем a < = b, когда либо a < b, либо a ∼ b. Аналогично, b > a, если a < b. Над вполне упорядоченным множеством можно определить бинарное дерево поиска.
root со значением item, равным r, выполняются условия:
item, равным le, справедливо: le < r;root есть правое поддерево, то для любого его узла со значением item, равным ri, справедливо: ri > r.Значения в узлах
(рис 8.15) Упражнение 5.11.3
Дерево, показанное на рисунке, является бинарным деревом поиска.
Процедура print_all, примененная к этому дереву, напечатает значения, упорядоченные по возрастанию, начиная с наименьшего значения 12.
Используя приведенные на данный момент процедуры, постройте дерево, показанное на рисунке, затем напечатайте значения в узлах, вызвав print_all. Убедитесь, что значения упорядочены.
Давайте рассмотрим причины, по которым деревья поиска являются полезными, как контейнерные структуры – потенциальные соперники хэш-таблиц. В самом деле, они обычно обеспечивают лучшую производительность, чем последовательные списки. В предположении случайного характера появления данных последовательный список, содержащий n элементов, обеспечивает:
Для бинарного дерева поиска обе операции имеют сложность O(log n), что намного лучше, чем O(n) для больших n (вспомните, что для нотации "О-большое" не имеет значения основание алгоритма). Проанализируем эффективность работы полного бинарного дерева, которое определяется тем, что для любого его узла оба поддерева, выходящие из узла, имеют одну и ту же высоту h:
(рис 8.16) Полное бинарное дерево
Нетрудно видеть, при помощи индукции по высоте h, что число узлов n в полном дереве высоты h равно $$2^h – 1$$. Как следствие, $$h = \log_2(n+1)$$. В полном дереве как поиск, так и вставка, используя приведенные ниже алгоритмы, выполняются за время O(log n), начиная работу в корне и следуя нисходящим путем к
Конечно, большинство практических бинарных деревьев не являются полными. Если не повезет при вставке, то производительность может быть столь же плоха, как и для последовательного списка – O(n). К этому добавляются
(рис 8.17) Схемы бинарных деревьев поиска, являющиеся причиной поведения O(N)
При случайном порядке вставки бинарные деревья поиска остаются достаточно близкими к полным деревьям с поведением близким к O(log n). Можно гарантировать выполнение операций поиска, вставки и удаления за время O(log n), если пользоваться специальными вариантами таких деревьев –
Приведем рекурсивную функцию поиска в бинарном дереве поиска (эта и следующая функция добавлены в класс, реализующий бинарные деревья поиска):
has (x: G): BOOLEAN
— Есть ли x в каком-либо узле?
require
argument_exists: x /= Void
do
if x ~ item then
Result := True
elseif x < item then
Result := (left /=Void) and then left.has (x)
else — x > item
Result := (right /= Void) and then right.has (x)
end
end
Алгоритм имеет сложность O(h), где h –
В этом варианте приводится простая нерекурсивная версия алгоритма:
has1 (x: G): BOOLEAN
— Есть ли x в каком-либо узле?
require
argument_exists: x /= Void
local
node: BINARY_TREE [G]
do
from
node := Current
until
Result or node = Void
invariant
— x не находится в вышерасположенных узлах на нисходящем пути от корня
loop
if x < item then
node := left
elseif x > item then
node := right
else
Result := True
end
variant
— (Высота дерева) – (Длина пути от корня к узлу)
end
end
Для вставки элемента можно использовать следующую рекурсивную процедуру:
put (x: G)
— Вставка x, если он не присутствует в дереве.
require
argument_exists: x /= Void
do
if x < item then
if left = Void then
add_left (x)
else
left.put (x)
end
elseif x > item then
if right = Void then
add_right (x)
else
right.put (x)
end
end
end
Отсутствие ветви else во внешнем if отражает наше решение не размещать дублирующую информацию. Как следствие, вызов put с уже присутствующим значением не имеет эффекта. Это корректное поведение ("не жучок, а свойство"), о чем и уведомляет заголовочный комментарий. Некоторые пользователи могут, однако, предпочитать другой API с предусловием, устанавливающим not has(x).
Возникает естественный вопрос: как написать процедуру удаления – remove(x:G)? Это не так просто, поскольку нельзя просто удалить узел, содержащий x, если только это не лист дерева. Удаление листа сводится к обнулению одной из ссылок – left или right. Удаление произвольного узла приводило бы к нарушению инварианта бинарного дерева поиска.
Что следует сделать, так это реорганизовать дерево, перемещая узлы, лежащие в основании узла с найденным значением x, так, чтобы сохранить истинность инварианта.
В удаляемый узел нужно поместить элемент дерева, лежащий ниже удаляемого элемента. Есть два кандидата на эту роль, позволяющие сохранить истинность инварианта:
Если перемещаемый элемент является
(рис 8.18) Ранее построенное дерево
Предположим, что удаляется remove (35). Тогда в корень можно поместить либо элемент 23 (из
Подобно
Напишите процедуру remove(x:G), которая удаляет элемент x, если он присутствует в дереве, сохраняя инвариант.
Прежде чем исследовать теоретические основы рекурсивного программирования, полезно познакомиться еще с одним приложением, а точнее – с целым классом приложений, для которого рекурсия является естественным инструментом: алгоритмами перебора с возвратом. В имени отражена основная идея алгоритма: отыскивается решение некоторой проблемы, последовательно перебираются возможные пути; всякий раз, когда решение на данном пути заходит в тупик, происходит возврат назад к предыдущей развилке, из которой не все возможные пути были исследованы. Процесс заканчивается успешно, если на одном из путей достигается решение задачи. Неуспех в решении возникает тогда, когда ни на одном пути решение не получено или достигнут лимит времени, отведенный на поиск решения.
Перебор с возвратами применим к задаче, если каждое ее потенциальное решение может рассматриваться как последовательность выборов.
При необходимости достижения некоторой цели путешествия в незнакомом городе как к последней надежде можно прибегнуть к перебору с возвратом. Скажем, Вы находитесь в точке А (главная станция Цюриха) и хотите добраться до точки В (между главными зданиями ЕТН и Университета Цюриха):
(рис 8.19) Испытания и перебор с возвратами
Не имея карты и по застенчивости не отваживаясь спросить дорогу к цели, вы решили исследовать прилежащие улицы и проверять после каждой попытки, не достигнута ли цель (предполагается, что у вас есть фотография конечной точки). Вы знаете, что цель расположена на востоке, так что во избежание зацикливания все западно-ориентированные сегменты игнорируются.
На каждом этапе вы проверяете отрезки улиц, начиная с севера и двигаясь по часовой стрелке. Первая попытка приводит в точку 1. Здесь вы понимаете, что это не отвечает вашей цели, так как далее все возможные пути ведут на запад, то есть это тупик и нужно возвращаться назад в исходную точку А. Далее вы испытываете следующий выбор, приводящий в 2. Здесь есть несколько возможностей, и вначале вы проверяете путь, ведущий в 3, который оказывается тупиком, так что приходится вернуться в точку 2.
Если все "правильные" (не ведущие на запад) пути в 2 были исследованы и приводили к тупикам, то из 2 пришлось бы вернуться в точку А. Но в данной ситуации из 2 есть еще не исследованный выбор, ведущий в точку 4.
Процесс продолжается аналогичным образом, вы можете дополнить его самостоятельно, используя приведенную карту. Возможно, это не лучшая стратегия для путешествия в незнакомом городе, но иногда она может быть единственно возможной. Более важно, что она представляет общую схему метода "проб и ошибок", характерную для программирования перебора с возвратами. Схема может быть описана с помощью рекурсивной процедуры:
find ( p: PAT H): PATH
— Решение, если оно существует, начинающееся в P.
require
meaningful: p /= Void
local
c: LIST [CHOICE]
do
if p.is_solution then
Result := p
else
c := p.choices
from c.start until
(Result /= Void) or c.after
loop
Result := find ( p + c)
c.forth
end
end
end
Здесь применяются следующие соглашения. Выборы на каждом шаге описываются типом CHOICE (во многих ситуациях для этой цели можно использовать тип INTEGER). Есть также тип PATH, но каждый путь path – это просто последовательность выборов, и p + c – это путь, полученный присоединением c к p. Мы идентифицируем решение с путем, приводящим к цели, так что find возвращает PATH. По соглашению, если find не находит решения, то возвращается void. Запрос is_solution позволяет выяснить, найдено ли решение. Список выборов – p.choices, доступных из p, является пустым списком, если p – это тупик.
Для получения решения достаточно использовать find(p0), где p0 – начальный пустой путь.
Как обычно, Result инициализируется значением Void. Если в вызове find(p) ни один из рекурсивных вызовов на возможных расширениях p + c не вырабатывает решения (в частности, если таких расширений вообще нет, поскольку p.choices пусто), то цикл завершится со значением c.after, и тогда find(p) вернет значение Void. Если это был начальный вызов find(p0), то процесс завершается, не достигнув положительного результата, в противном случае рекурсивно включается следующий вызов, пока не будет получен результат или не будут перебраны все возможности.
Если один из вызовов находит, что p является решением, то p возвращается в качестве результата, и, подымаясь вверх по цепочке вызовов, результат возвращается, поскольку Result /= Void является условием выхода.
Рекурсия дает четкую основу для управления такой схемой. Это естественный способ выразить природу
p может быть атрибутом, если мы добавим p:= p+x перед рекурсивным вызовом и p:= p.head после него (где head вырабатывает копию последовательности с удаленным последним элементом). Мы разработаем общий каркас, позволяющий безопасно выполнять такую оптимизацию.Общая схема перебора с возвратом требует некоторой настройки для практического использования. Прежде всего, в том виде, как она приведена, не гарантируется завершаемость. Чтобы убедиться в завершаемости любого выполнения, необходимо одно из двух:
Дополнительно практическая реализация обычно может обнаруживать эквивалентность некоторых путей, например, для ситуации, представленной на рисунке:
(рис 8.20) Путь с циклом
Пути [1, 2, 3, 4], [1, 2, 3, 4, 2, 3, 4], [1, 2, 3, 4, 2, 3, 4, 2, 3, 4] и так далее являются эквивалентными. Пример, демонстрирующий нахождение маршрута без циклов, состоял в важной рекомендации – "никогда не уезжайте на запад, молодой человек". Конечно, этот совет не может служить общей рекомендацией и связан лишь с конкретной проблемной ситуацией. Чтобы справиться с циклом, необходимо сохранять информацию о ранее посещенных точках и игнорировать любой путь, ведущий к такой точке.
Для любой задачи, в решении которой может помочь перебор с возвратами, может помочь и построение модели в виде дерева. При установке соответствия будем использовать деревья, где каждый узел будет иметь произвольное число потомков, обобщая концепции, рассмотренные при определении бинарных деревьев. Путь в дереве (последовательность узлов) соответствует пути в алгоритме перебора (последовательность выборов). Дерево в примере с маршрутами представлено на рис 8.21.
(рис 8.21) Дерево путей при переборе с возвратами
Мы можем представлять всю карту города подобным образом: узлы отражают местоположение указанных на карте точек, дуги представляют отрезки улиц, соединяющих точки. В результате получается граф. Граф может быть деревом только в том случае, если в нем нет циклов. Если граф не является деревом, то на его основе можно построить дерево, называемое
Для такого представления нашей задачи в виде дерева:
is_solution, адаптированное для применения к узлам);В нашем примере этот порядок приведет к посещению узлов А, 1, 2, 3, 4.
Это соответствие указывает, что "Префиксный обход" и "Перебор с возвратами" основаны на одной и той же идее: всякий раз, когда мы рассматриваем возможный путь, мы разматываем все его возможные продолжения – все поддеревья узла, – прежде чем обращаемся к любому альтернативному выбору на уровне, представляющем непосредственных потомков узла. Например, если А на предыдущем рисунке будет иметь третьего потомка, то обход не будет его рассматривать, прежде чем не обойдет все поддеревья 2.
Единственное свойство, отличающее алгоритм перебора с возвратами от префиксного обхода, состоит в том, что он останавливается сразу же, как только найден узел, удовлетворяющий выбранному критерию.
Префиксный порядок был определен для бинарных деревьев следующим образом: посетить корень, затем обойти
Интересным примером стратегии перебора, также естественным образом моделируемой деревом, является минимаксная техника, применяемая в играх, таких как шахматы. Она применима, если справедливы следующие предположения:
(mb – mw) + 3 * (kb – kw), где mb и mw – число простых шашек соответственно у Макса и Минни, а kb и kw – число дамок, каждая из которых оценивается в три раза выше, чем простая шашка. Конечно, в хорошей Минни старается найти позицию, минимизирующую оценочную функцию, а Макс старается ее максимизировать.
(рис 8.22) Дерево игры
Каждый игрок использует минимаксную стратегию для выбора в текущей позиции одного из возможных ходов. Дерево моделирует игры такого вида, последовательные уровни дерева представляют ходы каждого из игроков.
На рисунке все начинается с позиции, где ход должна сделать Минни. Цель стратегии – позволить Минни среди ходов, доступных в данной позиции (три на рисунке), выбрать тот, который гарантирует лучший результат. В данном случае она старается получить минимальное значение оценочной функции на
Предположение о симметричности – основа для
| М1 | Значение листа является результатом применения оценочной функции к соответствующей позиции игры. |
| М2 | Значение внутреннего узла, задающего ход Макса, является максимумом из значений детей этого узла. |
| М3 | Значение внутреннего узла, задающего ход Минни, является минимумом из значений детей этого узла. |
Можно видеть, что значение в каждом узле является минимумом (для уровней 1 и 3) или максимумом (на уровне 2) значений сыновей узла. Оптимальный ход для Минни, обеспечивающий значение -7, состоит в выборе хода С.
Перебор с возвратами вполне подходит для
(рис 8.23) Дерево игры с оценками
Следующий алгоритм, являясь вариацией ранее приведенной общей схемы перебора, реализует эту идею. Он представлен функцией value – гарантированное значение из начальной позиции p, и choice – начальный выбор, приводящий к этому значению. Аргумент l задает уровень, на котором появляется позиция p в ходе игры. Первый ход из этой позиции, возвращаемый как часть результата, является ходом Минни (как на рисунке), если l нечетно, и ходом Макса, если l четно.
minimax ( p: POSITION; l: INTEGER): TUPLE [value, choice: INTEGER]
— Оптимальная стратегия(value + choice) на уровне l, начиная с позиции p.
local
next: TUPLE [value, choice: INTEGER]
do
if p.is_terminal (l ) then
Result := [value: p.value; choice: 0]
else
c := p.choices
from
Result := worst (l )
c.start
until c.after loop
next := minimax (p.moved (c.item), l + 1)
Result := better (next, Result, l )
end
end
end
Для представления результата используется кортеж, задающий значение и выбор.
Дополнительные функции worst и better дают возможность переключаться между Максом и Минни – игрок минимизирует на каждом нечетном ходе и максимизирует на четном.
worst (l: INTEGER): INTEGER
— Худшее возможное значение для игрока на уровне l.
do
if l \\ 2 = 1 then Result := Max else Result := Min end
end
better (a, b: TUPLE [value, choice: INTEGER]; l: INTEGER):
TUPLE [value, choice: INTEGER]
- Лучшее из a и b, в соответствии с их значениями для игрока на уровне l.
do
if l \\ 2 = 1 then
Result := (a.value < b.value)
else
Result := (a.value > b.value)
end
end
Для определения худшего значения для каждого игрока вводятся две константы Max и Min (самое большое и самое малое значения).
Функция POSITION:
is-terminal указывает, что в данной позиции нет ходов, подлежащих исследованию;value дает значение оценочной функции (запрос value может иметь предусловие is-terminal);choices, где каждый выбор представлен целым, задающим допустимый ход;i является таким выбором, moved(i) дает позицию, полученную в результате применения соответствующего хода к текущей позиции.Простейший способ убедиться, что алгоритм завершается, состоит в ограничении глубины перебора, задав Limit – предельное число уровней. Вот почему is-terminal в том виде, как она задана, включает уровень l как аргумент. Она может быть записана в виде:
is_terminal (l: INTEGER): BOOLEAN
— Следует ли исследовать уровень l или остановиться на текущей позиции?
do
Result := (l = Limit) or choices.is_empty
end
На практике используются более сложные критерии остановки, например, алгоритм может сохранять затраты процессорного времени и останавливаться, когда достигнуто ограничение по времени.
Для выполнения мы вызываем initial задает начальную позицию игры. Уровень 1 указывает на то, что ход принадлежит Минни.
Минимаксная стратегия всегда выполняет полный обход дерева допустимых ходов игры. Можно существенно улучшить эффективность работы, применяя оптимизацию, известную как "альфа-бета-стратегия", которая позволяет пропускать в процессе обхода целые поддеревья, "бесполезные" для достижения цели игры. Это прекрасная идея, заслуживающая внимания не только как "умное" решение, но и как пример усовершенствования рекурсивного алгоритма.
Альфа-бета имеет смысл только в предположениях, сделанных для
Идея пропуска поддерева основана на том, что игрок на уровне l +1 обнаруживает, что нет необходимости продолжать анализировать поддерево, поскольку он может получить на нем лучший результат, чем уже полученный. Но для его противника этот результат будет худшим, чем тот, что уже гарантирован ему на уровне l, и потому противник никогда не выберет это поддерево (напомним, что игроки всегда выбирают оптимальный ход с точки зрения принятой стратегии).
Предыдущий пример позволяет проиллюстрировать идею альфа-бета-стратегии. Рассмотрим ситуацию в процессе работы минимаксного алгоритма, когда исследовано несколько начальных узлов.
(рис 8.24) Пропуск полезных поддеревьев
Мы находимся в процессе вычисления значения (максимума) для узла Ма1 и, как часть этой цели, вычисления значения (минимум) для узла Мi2. Анализ первого поддерева для Ма1 с корнем в Мi1 позволил определить частичный максимум для Ма1, равный 8 (на рисунке он отмечен знаком вопроса, сигнализирующим, что вычисления еще не завершены). Это означает для Макса, что 8 он себе обеспечил и на меньшее не согласится. При анализе поддерева с корнем Мi2 мы пришли к поддереву Ма2 (к листу в данном конкретном случае, но вывод применим к любому поддереву), где значение равно 6, так что в любом случае Минни не выберет в Мi2 значение, большее 6, а тогда ясно, что дальнейший анализ бесполезен, поскольку не окажет влияния на значение в вышестоящем узле Ма1. Так что, как только найдено значение 6 для Ма2, альфа-бета-стратегия прекратит анализ поддерева с корнем в Мi2.
Эта оптимизация интересна сама по себе, но она дает и хорошую возможность отточить наши навыки рекурсивного программирования. Попытайтесь сами построить соответствующий метод, не заглядывая в решение, которое приводится ниже.
Адаптируйте минимаксный алгоритм, приведенный ранее, так, чтобы он использовал стратегию "альфа-бета" для отбраковки бесполезных поддеревьев.
Расширение алгоритма достаточно просто. Методу понадобится еще один аргумент, задающий значение (если оно существует), которое для противника гарантированно находится на уровне непосредственно выше. Вот минимаксная процедура с добавленной альфа-бета стратегией:
alpha_beta ( p: POSITION; l: INTEGER; guarantee: INTEGER):
TUPLE [value, choice:
INTEGER]
— Оптимальная стратегия(value + choice) на уровне l, начиная с позиции p.
— Нечетный уровень минимизирует, четный – максимизирует.
local
next: TUPLE [value, choice: INTEGER]
do
if p.is_terminal (l ) then
Result := [value: p.value; choice: 0]
else
c := p.choices
from
Result := worst (l )
c.start
until c.after or better (guarantee, Result, l – 1) loop
next := minimax ( p.moved (c.item), l + 1), Result)
Result := better (next, Result, l )
end
end
end
Каждый игрок теперь останавливает анализ своего выбора, если противник может получить гарантированно лучший результат.
better определена без предусловия, то это означает, что она может принимать и уровень 0, так что допустимо передавать ей l - 1. Мы могли бы передавать и l + 1, поскольку вариантом better(guarantee, Result, l-1) является better(Result, guarantee, l), благодаря симметрической природе стратегии.Рекурсивный вызов передает как "guarantee" на следующий уровень лучший Result, полученный на текущем уровне. Как следствие, альфа-бета останавливает обход узлов детей, когда срабатывает новый переключатель выхода better(guarantee, Result, l-1). Такая ситуация никогда не встретится для первого сыновнего узла, поскольку Result инициализирован значением worst.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.