misle.ru страница 1
скачать файл
Вариант 4.

1. Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n). Однако при некотором стечении обстоятельств дерево может оказаться вырожденным. Тогда высота его будет O(n), и доступ к данным существенно замедлится. В этом разделе мы рассмотрим модифицированный класс деревьев, обладающих всеми преимуществами бинарных деревьев поиска и никогда не вырождающихся. Они называются сбалансированными или AVL-деревьями. Под сбалансированностью будем понимать то, что для каждого узла дерева высоты обоих его поддеревьев различаются не более чем на 1. Строго говоря, этот критерий нужно называть AVL-сбалансированностью в отличие от идеальной сбалансированности, когда для каждого узла дерева количества узлов в левом и правом поддеревьях различаются не более чем на 1. Здесь мы всегда будем иметь в виду AVL-сбалансированность.

Новые методы вставки и удаления в классе AVL-деревьев гарантируют, что все узлы останутся сбалансированными по высоте. На рисунках 7.23 и 7.24 показаны эквивалентные представления массива AVL-деревом и бинарным деревом поиска. Рисунок 7.23 представляет простой пятиэлементный массив А (A[5] = {1,2,3,4,5}), отсортированный по возрастанию.



Рис. 7.24. Представление бинарного и AVL-дерева для массива В


Рисунок 7.24 представляет массив B (B[8] = {20, 30, 80, 40, 10, 60, 50, 70}). Бинарное дерево поиска имеет высоту 5, в то время как высота AVL-дерева равна 2. В общем случае высота сбалансированного дерева не превышает O(log2n). Таким образом, AVL-дерево является мощной структурой хранения, обеспечивающей быстрый доступ к данным.

Алгоритм AVL-вставки


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

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

Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balanceFactor = 0). После вставки в поддерево нового элемента узел стал перевешивать влево или вправо в зависимости от того, в какое поддерево была произведена вставка. Если элемент вставлен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, то 1. Например, на пути 40-50-60 каждый узел сбалансирован. После вставки узла 55 показатели сбалансированности изменяются (рисунок 7.26).

Случай 2. Одно из поддеревьев узла перевешивает, и новый узел вставляется в более легкое поддерево. Узел становится сбалансированным. Сравните, например, состояния дерева до и после вставки узла 55 (рисунок 7.27).

Случай 3. Одно из поддеревьев узла перевешивает, и новый узел помещается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balanceFactor выходит за пределы -1..1. Чтобы восстановить равновесие, нужно выполнить поворот.

Исключение из сбалансированного дерева


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

Принципиальная схема алгоритма исключения из сбалансиро­ванного дерева аналогична (7.28). Простые случаи — удаление терминальных вершин или вершин только с одним потомком. Если же от исключаемой вершины "отходят" два поддерева, то, как и раньше, она заменяется на самую правую вершину ее лево­го поддерева. Как и в случае включения (7.31). Балансировка идет, только если balanceFactor какой-либо вершины оказывается равен 2. Это значение присваивается переменной balanceFactor при обнаружении и исклю­чении какой-либо вершины или уменьшении высоты какого-либо поддерева в процессе самой балансировки.

Из исходно­го сбалансированного дерева (рис. 7.34, а) последовательно ис­ключаются вершины с ключами 4, 8, 6, 5, 2, 1 и 7 и получаются деревья, представленные на рис. 4.34, б-з. Исключение ключа 4 выглядит просто, поскольку он представляет собой терминальную вершину.

Однако в результате получается несбалансированная вершина 3. Соответствующая операция балансировки требует единственного поворота. При исключении вершины 6 вновь требуется балансировка. В этот момент одиночным RR-поворотом балансируется правое поддерево вершины 7. Исключение вершины 2, хотя само по себе оно простое, поскольку вершина имеет лишь одного потомка, приводит к усложненному двукратному RL-повороту. И четвертый случай: двукратный RL-поворот проводится при изъятии вершины 7, вместо которой вначале помещался cамый правый элемент ее левого поддерева, т. е. вершина с ключом 3.

Включение может потребовать поворота 2, 3 вершин, исключение может потребовать поворотов во всех вершинах. В худшем случае O(log2n) операций. Вероятность поворотов: при включении на 2 включения 1 поворот, при исключении 1 поворот на 5 случаев. Исключение самой правой вершины из дерева Фибоначчи приводит к самому худшему случаю – перестройке всего дерева.

2. Приближения в задаче о раскраске графа


Раскраска графа — необычная задача: как мы уже упоминали ра­нее, построение раскраски, достаточно близкой к оптимальной, дает­ся столь же сложно, как и построение оптимальной раскраски. Число красок, даваемое наилучшим известным полиномиальным алгоритмом, более чем вдвое превышает оптимальное. Кроме того доказано, что если существует полиномиальный алгоритм, раскрашивающий верши­ны любого графа числом красок, превышающим оптимальное не более чем вдвое, то существует и полиномиальный алгоритм оптимальной раскраски любого графа. Существование такого алгоритма означало бы, что P=NP. На сложность графа можно наложить некоторые усло­вия, облегчающие его раскраску. Например, известны полиномиальные алгоритмы раскраски планарных графов, т.е. таких графов, которые можно изобразить на плоскости в виде набора вершин и ребер, пред­ставленных попарно не пересекающимися дугами.

Вот простой алгоритм последовательной раскраски произвольного графа с N вершинами.


ColorGraph(G)

G раскрашиваемый граф


for i=l to N

c=l ;


while в G есть вершина, соседняя с вершиной i,

покрашенная цветом с

с=с+1;

end while;



покрасить вершину i цветом с

end for;


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

Приближения в задаче об упаковке рюкзака


Приближенный алгоритм упаковки рюкзака представляет собой простой жадный алгоритм, выбирающий наилучшее отношение стоимости к раз­меру. Сначала мы сортируем список объектов по отношению стоимости к размеру. Каждый объект представляется в виде пары [размер, сто­имость]. Для списка объектов ([25, 50], [20, 80], [20, 50], [15, 45], [30, 105], [35, 35], [20, 10], [10, 45]) удельные стоимости имеют значения (2, 4, 2.5, 3, 3.5, 1, 0.5, 4.5). Сортировка удельных стоимостей приводит к списку ([10, 45], [20, 80], [30, 105], [15, 45], [20, 50], [25,50], [35, 35], [20, 10]). После этого мы начинаем заполнять рюкзак последовательно иду­щими элементами отсортированного списка объектов. Если очередной объект не входит — мы отбрасываем его и переходим к следующему; так продолжается до тех пор, пока рюкзак не заполнится или список объектов не будет исчерпан. Таким образом, если емкость рюкзака 80, то мы сможем поместить в него первые четыре предмета суммарно­го объема 75 и общей стоимостью 275. Это не оптимальное решение: первые три предмета с добавкой пятого дают суммарный объем 80 и стоимость 280.

3. Условия применения динамического программирования:

  1. Небольшое число подзадач. Уменьшение числа подзадач происходит из-за многократного их повторения (т.н. перекрывающиеся подзадачи)

  2. Дискретность (неделимость) величин, рассматриваемых в задаче.
скачать файл



Смотрите также: