VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Depth = Depth - 1
' Dx и Dy остаются без изменений.
pc = 1 Перейти в начало рекурсивного
вызова.
Else ' Условие остановки.
' Достаточно глубокий уровень рекурсии.
' Продолжить с 4 блоком кода.
pc = 4
End If
Case 4
HilbertPicture.Line -Step(-Dx, -Dy)
If Depth > 1 Then ' Рекурсия.
' Сохранить текущие значения.
SaveValues Depth, Dx, Dy, 0
' Подготовиться к рекурсии.
Depth = Depth - 1
tmp = Dx
Dx = -Dy
Dy = -tmp
pc = 1 Перейти в начало рекурсивного
вызова.
Else ' Условие остановки.
' Достаточно глубокий уровень рекурсии.
' Конец этого рекурсивного вызова.
pc = 0
End If
Case 0 ' Возврат из рекурсии.
If TopOfStack > 0 Then
RestoreValues Depth, Dx, Dy, pc
Else
' Стек пуст. Выход.
Exit Do
End If
End Select
Loop
End Sub
======111
Время выполнения этого алгоритма может быть нелегко оценить
непосредственно. Поскольку методы преобразования рекурсивных процедур в
нерекурсивные не изменяют время выполнения алгоритма, эта процедура так же,
как и предыдущая версия, имеет время выполнения порядка O(N4).
Программа Hilbert2 демонстрирует нерекурсивный алгоритм построения кривых
Гильберта. Задавайте вначале построение несложных кривых (меньше 6
порядка), пока не узнаете, насколько быстро будет выполняться эта программа
на вашем компьютере.
Нерекурсивное построение кривых Серпинского
Приведенный ранее алгоритм построения кривых Серпинского включает в себя
косвенную и множественную рекурсию. Так как алгоритм состоит из четырех
подпрограмм, которые вызывают друг друга, то нельзя просто пронумеровать
важные строки, как это можно было сделать в случае алгоритма построения
кривых Гильберта. С этой проблемой можно справиться, слегка изменив
алгоритм.
Рекурсивная версия этого алгоритма состоит из четырех подпрограмм SierpA,
SierpB, SierpC и SierpD. Подпрограмма SierpA выглядит так:
Private Sub SierpA(Depth As Integer, Dist As Single)
If Depth = 1 Then
Line -Step(-Dist, Dist)
Line -Step(-Dist, 0)
Line -Step(-Dist, -Dist)
Else
SierpA Depth - 1, Dist
Line -Step(-Dist, Dist)
SierpB Depth - 1, Dist
Line -Step(-Dist, 0)
SierpD Depth - 1, Dist
Line -Step(-Dist, -Dist)
SierpA Depth - 1, Dist
End If
End Sub
Три другие процедуры аналогичны. Несложно объединить эти четыре процедуры в
одну подпрограмму.
Private Sub SierpAll(Depth As Integer, Dist As Single, Func As Integer)
Select Case Punc
Case 1 ' SierpA
Case 2 ' SierpB
Case 3 ' SierpC
Case 4 ' SierpD
End Select
End Sub
======112
Параметр Func сообщает подпрограмме, какой блок кода выполнять. Вызовы
подпрограмм заменяются на вызовы процедуры SierpAll с соответствующим
значением Func. Например, вызов подпрограммы SierpA заменяется на вызов
процедуры SierpAll с параметром Func, равным 1. Таким же образом заменяются
вызовы подпрограмм SierpB, SierpC и SierpD.
Полученная процедура рекурсивно вызывает себя в 16 различных точках. Эта
процедура намного сложнее, чем процедура Hilbert, но в других отношениях
она имеет такую же структуру и поэтому к ней можно применить те же методы
устранения рекурсии.
Можно использовать первую цифру меток pc, для определения номера блока
кода, который должен выполняться. Перенумеруем строки в коде SierpA числами
11, 12, 13 и т.д. Перенумеруем строки в коде SierpB числами 21, 22, 23 и
т.д.
Теперь можно пронумеровать ключевые строки кода внутри каждого из блоков.
Для кода подпрограммы SierpA ключевыми строками будут:
' Код SierpA.
11 If Depth = 1 Then
Line -Step(-Dist, Dist)
Line -Step(-Dist, 0)
Line -Step(-Dist, -Dist)
Else
SierpA Depth - 1, Dist
12 Line -Step(-Dist, Dist)
SierpB Depth - 1, Dist
13 Line -Step(-Dist, 0)
SierpD Depth - 1, Dist
14 Line -Step(-Dist, -Dist)
SierpA Depth - 1, Dist
End If
Типичная «рекурсия» из кода подпрограммы SierpA в код подпрограммы SierpB
выглядит так:
SaveValues Depth, 13 ' Продолжить с шага 13 после завершения.
Depth = Depth - 1
pc = 21 ' Передать управление на начало кода
SierpB.
======113
Метка 0 зарезервирована для обозначения выхода из «рекурсии». Следующий код
демонстрирует нерекурсивную версию процедуры SierpAll. Код для подпрограмм
SierpB, SierpC, и SierpD аналогичен коду для SierpA, поэтому он опущен.
Private Sub SierpAll(Depth As Integer, pc As Integer)
Do
Select Case pc
' **********
' * SierpA *
' **********
Case 11
If Depth " & Format$(ToNode(link))
Next link
@Рис. 6.6. Программа Nary
=======123
На рис. 6.7 показано дерево и его представление нумерацией связей. Связи,
выходящие из 3 узла (обозначенного буквой D) это связи от FirstLink(3) до
FirstLink(4)-1. Значение FirstLink(3) равно 9, а FirstLink(4) = 11, поэтому
это связи с номерами 9 и 10. Записи ToNode для этих связей равны ToNode(9)
= 10 и ToNode(10) = 11, поэтому узлы 10 и 11 будут дочерними для 3 узла.
Это узлы, обозначенные буквами K и L. Это означает, что связи, покидающие
узел D, ведут к узлам K и L.
Представление дерева нумерацией связей компактно и основано на массиве,
поэтому деревья, представленные таким образом, можно легко считывать из
файлов и записывать в файл. Операции для работы с массивами, которые
используются при таком представлении, также могут быть быстрее, чем
операции, нужные для использования узлов, содержащих коллекции дочерних
узлов.
По этим причинам большая часть литературы по сетевым алгоритмам использует
представление нумерацией связей. Например, многие статьи, касающиеся
вычисления кратчайшего пути, предполагают, что данные находятся в подобном
формате. Если вам когда-либо придется изучать эти алгоритмы в журналах,
таких как “Management Science” или “Operations Research”, вам необходимо
разобраться в этом представлении.
@Рис. 6.7. Дерево и его представление нумерацией связей
=======123
Используя представление нумерацией связей, можно быстро найти связи,
выходящие из определенного узла. С другой стороны, очень сложно изменять
структуру данных, представленных в таком виде. Чтобы добавить к узлу A на
рис. 6.7 еще одного потомка, придется изменить почти все элементы в обоих
массивах FirstLink и ToNode. Во-первых, каждый элемент в массиве ToNode
нужно сдвинуть на одну позицию вправо, чтобы освободить место под новый
элемент. Затем, нужно вставить новую запись в массив ToNode, которая
указывает на новый узел. И, наконец, нужно обойти массив ToNode, обновив
каждый элемент, чтобы он указывал на новое положение соответствующей записи
ToNode. Поскольку все записи в массиве ToNode сдвинулись на одну позицию
вправо, чтобы освободить место для новой связи, потребуется добавить
единицу ко всем затронутым записям FirstLink.
На рис. 6.8 показано дерево после добавления нового узла. Записи, которые
изменились, закрашены серым цветом.
Удаление узла из начала представления нумерацией связей так же сложно, как
и вставка узла. Если удаляемый узел имеет потомков, процесс занимает еще
больше времени, поскольку придется удалять и все дочерние узлы.
Относительно простой класс с открытой коллекцией дочерних узлов лучше
подходит, если нужно часто модифицировать дерево. Обычно проще понимать и
отлаживать процедуры, которые оперируют деревьями в этом представлении. С
другой стороны, представление нумерацией связей иногда обеспечивает более
высокую производительность для сложных алгоритмов работы с деревьями. Оно
также являются стандартной структурой данных, обсуждаемой в литературе,
поэтому вам следует ознакомиться с ним, если вы хотите продолжить изучение
алгоритмов работы с сетями и деревьями.
@Рис. 6.8. Вставка узла в дерево, представленное нумерацией связей
=======124
Программа Fstar использует представление нумерацией связей для работы с
деревом, имеющим узлы разного порядка. Она аналогична программе NAry, за
исключением того, что она использует представление на основе массива, а не
коллекций.
Если вы посмотрите на код программы Fstar, вы увидите, насколько сложно в
ней добавлять и удалять узлы. Следующий код демонстрирует удаление узла из
дерева.
Sub FreeNodeAndChildren(ByVal parent As Integer, _
ByVal link As Integer, ByVal node As Integer)
' Recursively remove the node's children.
Do While FirstLink(node) < FirstLink(node + 1)
FreeNodeAndChildren node, FirstLink(node), _
ToNode(FirstLink(node))
Loop
' Удалить связь.
RemoveLink parent, link
' Удалить сам узел.
RemoveNode node
End Sub
Sub RemoveLink(node As Integer, link As Integer)
Dim i As Integer
' Обновить записи массива FirstLink.
For i = node + 1 To NumNodes
FirstLink(i) = FirstLink(i) - 1
Next i
' Сдвинуть массив ToNode чтобы заполнить пустую ячейку.
For i = link + 1 To NumLinks - 1
ToNode(i - 1) = ToNode(i)
Next i
' Удалить лишний элемент из ToNode.
NumLinks = NumLinks - 1
If NumLinks > 0 Then ReDim Preserve ToNode(0 To NumLinks - 1)
End Sub
Sub RemoveNode(node As Integer)
Dim i As Integer
' Сдвинуть элементы массива FirstLink, чтобы заполнить
' пустую ячейку.
For i = node + 1 To NumNodes
FirstLink(i - 1) = FirstLink(i)
Next i
' Сдвинуть элементы массива NodeCaption.
For i = node + 1 To NumNodes - 1
NodeCaption(i - 1) = NodeCaption(i)
Next i
' Обновить записи массива ToNode.
For i = 0 To NumLinks - 1
If ToNode(i) >= node Then ToNode(i) = ToNode(i) - 1
Next i
' Удалить лишнюю запись массива FirstLink.
NumNodes = NumNodes - 1
ReDim Preserve FirstLink(0 To NumNodes)
ReDim Preserve NodeCaption(0 To NumNodes - 1)
Unload FStarForm.NodeLabel(NumNodes)
End Sub
Это намного сложнее, чем соответствующий код в программе NAry:
Public Function DeleteDescendant(target As NAryNode) As Boolean
Dim i As Integer
Dim child As NAryNode
' Является ли узел дочерним узлом.
For i = 1 To Children.Count
If Children.Item(i) Is target Then
Children.Remove i
DeleteDescendant = True
Exit Function
End If
Next i
' Если это не дочерний узел, рекурсивно
' проверить остальных потомков.
For Each child In Children
If child.DeleteDescendant(target) Then
DeleteDescendant = True
Exit Function
End If
Next child
End Function
=======125-126
Полные деревья
Полное дерево (complete tree) содержит максимально возможное число узлов на
каждом уровне, кроме нижнего. Все узлы на нижнем уровне сдвигаются влево.
Например, каждый уровень троичного дерева содержит в точности три дочерних
узла, за исключением листьев, и возможно, одного узла на один уровень выше
листьев. На рис. 6.9 показаны полные двоичное и троичное деревья.
Полные деревья обладают рядом важных свойств. Во-первых, это кратчайшие
деревья, которые могут содержать заданное число узлов. Например, двоичное
дерево на рис. 6.9 — одно из самых коротких двоичных деревьев с шестью
узлами. Существуют другие двоичные деревья с шестью узлами, но ни одно из
них не имеет высоту меньше 3.
Во-вторых, если полное дерево порядка D состоит из N узлов, оно будет иметь
высоту порядка O(logD(N)) и O(N) листьев. Эти факты имеют большое значение,
поскольку многие алгоритмы обходят деревья сверху вниз или в
противоположном направлении. Время выполнения алгоритма, выполняющего одно
из этих действий, будет порядка O(N).
Чрезвычайно полезное свойство полных деревьев заключается в том, что они
могут быть очень компактно записаны в массивах. Если пронумеровать узлы в
«естественном» порядке, сверху вниз и слева направо, то можно поместить
элементы дерева в массив в этом порядке. На рис. 6.10 показано, как можно
записать полное дерево в массиве.
Корень дерева находится в нулевой позиции. Дочерние узлы узла I находятся
на позициях 2 * I + 1 и 2 * I + 2. Например, на рис. 6.10, потомки узла в
позиции 1 (узла B), находятся в позициях 3 и 4 (узлы D и E).
Легко обобщить это представление на полные деревья более высокого порядка
D. Корень дерева также будет находиться в позиции 0. Потомки узла I
занимают позиции от D * I + 1 до D * I +(I - 1). Например, в троичном
дереве, потомки узла в позиции 2, будут занимать позиции 7, 8 и 9. На рис.
6.11 показано полное троичное дерево и его представление в виде массива.
@Рис. 6.9. Полные деревья
=========127
@Рис. 6.10. Запись полного двоичного дерева в массиве
При использовании этого метода записи дерева в массиве легко и просто
получить доступ к потомкам узла. При этом не требуется дополнительной
памяти для коллекций дочерних узлов или меток в случае представления
нумерацией связей. Чтение и запись дерева в файл сводится просто к
сохранению или чтению массива. Поэтому это несомненно лучшее представление
дерева для программ, которые сохраняют данные в полных деревьях.
Обход дерева
Последовательное обращение ко всем узлам называется обходом (traversing)
дерева. Существует несколько последовательностей обхода узлов двоичного
дерева. Три простейших из них — прямой (preorder), симметричный (inorder),
и обратный (postorder)обход, описываются простыми рекурсивными алгоритмами.
Для каждого заданного узла алгоритмы выполняют следующие действия:
Прямой обход:
1. Обращение к узлу.
2. Рекурсивный прямой обход левого поддерева.
3. Рекурсивный прямой обход правого поддерева.
Симметричный обход:
1. Рекурсивный симметричный обход левого поддерева.
2. Обращение к узлу.
3. Рекурсивный симметричный обход левого поддерева.
Обратный обход:
1. Рекурсивный обратный обход левого поддерева.
2. Рекурсивный обратный обход правого поддерева.
3. Обращение к узлу.
@Рис. 6.11. Запись полного троичного дерева в массиве
=======128
Все три порядка обхода являются примерами обхода в глубину (depth-first
traversal). Обход начинается с прохода вглубь дерева до тех пор, пока
алгоритм не достигнет листьев. При возврате из рекурсивного вызова
подпрограммы, алгоритм перемещается по дереву в обратном направлении,
просматривая пути, которые он пропустил при движении вниз.
Обход в глубину удобно использовать в алгоритмах, которые должны вначале
обойти листья. Например, метод ветвей и границ, описанный в 8 главе, как
можно быстрее пытается достичь листьев. Он использует результаты,
полученные на уровне листьев для уменьшения времени поиска в оставшейся
части дерева.
Четвертый метод перебора узлов дерева — это обход в ширину (breadth-first
traversal). Этот метод обращается ко всем узлам на заданном уровне дерева,
перед тем, как перейти к более глубоким уровням. Алгоритмы, которые
проводят полный поиск по дереву, часто используют обход в ширину. Алгоритм
поиска кратчайшего маршрута с установкой меток, описанный в 12 главе,
представляет собой обход в ширину, дерева кратчайшего пути в сети.
На рис. 6.12 показано небольшое дерево и порядок, в котором перебираются
узлы во время прямого, симметричного и обратного обхода, а также обхода в
ширину.
@Рис. 6.12. Обходы дерева
======129
Для деревьев больше, чем 2 порядка, все еще имеет смысл определять прямой,
обратный обход, и обход в ширину. Симметричный обход определяется
неоднозначно, так как обращение к каждому узлу может происходить после
обращения к одному, двум, или трем его потомкам. Например, в троичном
дереве, обращение к узлу может происходить после обращения к его первому
потомку или после обращения ко второму потомку.
Детали реализации обхода зависят от того, как записано дерево. Для обхода
дерева на основе коллекций дочерних узлов, программа должна использовать
несколько другой алгоритм, чем для обхода дерева, записанного при помощи
нумерации связей.
Особенно просто обходить полные деревья, записанные в массиве. Алгоритм
обхода в ширину, который требует дополнительных усилий в других
представлениях деревьев, для представлений на основе массива тривиален, так
как узлы записаны в таком же порядке.
Следующий код демонстрирует алгоритмы обхода полного двоичного дерева:
Dim NodeLabel() As String ' Запись меток узлов.
Dim NumNodes As Integer
' Инициализация дерева.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31
|