11. Дерево двоичного поиска

В любом ДДП на любом уровне выполняется следующее условие: в левом поддереве хранятся элементы меньшие, чем значения записанные в корне поддерева, в правом – большее. поэтому если ставится задача определить, содержится ли значение y среди множества элементов X, то на каждой проверке (на каждом внутреннем узле) исключаются из рассмотрения элементы, содержащиеся в другом поддереве, тем самым сокращая число операций.

Добавление в ДДП.

1 шаг. Добавляемый элемент ищется в ДДП, так как хранение дубликатов ДДП исключено.

2 шаг. Если значение не найдено, то элемент добавляется в ту позицию, которая соответствует характеристическому правилу ДДП, т.е. становится листом.

Например:

Удаление.

1 шаг. Ищется удаляемый элемент в ДДП

2 шаг. Если найденный элемент – лист, то он просто динамически удаляется, а у родителя в поле связи записывается 0.

3 шаг. Если удаляемый элемент – внутренний узел и имеет одного сына, то родитель удаляемого элемента становится родителем сына удаляемого элемента того же поддерева.

4 шаг. Если удаляемый элемент – внутренний узел с двумя сыновьями, то его место занимает наибольший элемент в левом поддереве, который является самым правым сыном, или наименьший элемент в правом поддереве, который является самым левым сыном (выбор реализации неважен). Самый правый (левый) сын означает, что у него нет соответствующего сына (справа/слева), т.е. он имеет либо 0 (лист) либо 1 сын с противоположной стороны. Этот найденный узел удаляется из дерева согласно одному из предыдущих шагов алгоритма.

Недостаток - ДДП является несбалансированным деревом. Если последовательность упорядочена, то ДДП превращается в ЛСС.

Достоинство – позволяет найти элемент в дереве за время, меньшее чем O(n).

12. 2-3-дерево

в 2-3-дереве элементы располагаются в листьях, а внутренние узлы – служебные, для которых можно предложить следующую структуру:

2-3-дерево является ДДП в том смысле что для любого элемента выполняется условие .

То есть тут как бы 2 ДДП:

Таким образом структура внутреннего узла:

p – указатель на родителя

x, y, z – указатели на левое, среднее и правое поддеревья

a, b – копии значений элементов множества (листьев), причём a есть минимальное значение в среднем поддереве, b – минимум в правом поддереве.

Характеристическое ограничение в 2-3-дереве заключается в том, что у любого внутреннего узла за исключением быть может корня может быть строго либо 2 либо 3 сына. Это обеспечивается при добавлении расщеплением внутреннего узла а при удалении – склейкой.

И последнее замечание. Заметим, что для любого уровня выполнение характеристического правила (см. рисунок) обеспечивает то, что листья будут упорядочены слева направо.

Если дерево имеет 2 сына, то используются строго левые позиции (левое и среднее поддерево, b и z – не используются).

Добавление нового элемента

1. 2-3-дерево – пустое дерево, добавляем узел

2. Если элемент добавляется (привязывается) к родителю, имеющему меньше трёх сыновей, то лист добавляется так, чтобы эти элементы были упорядочены слева направо (реализуется это перенастройкой двух или трёх связей)

3. Если при добавлении новый элемент претендует быть четвёртым, то внутренний узел расщепляется, причём четыре сына распределяются между двумя родителями по два сына так, чтобы было упорядочено слева направо. Поскольку расщепляемый узел был корнем, то создаётся новый внутренний узел (корень), к которому «подвязываются» сыновьями внутренние узлы, не нарушая очерёдности слева направо.

Удаление.

Если элемент присутствует в дереве, то он удаляется из листьев, а все внутренние узлы, являющиеся элементами пути от корня до удалённого элемента перестраиваются, в том числе пересчитываются a и b (если надо).

1. Если удаляемый лист имеет двух братьев у внутреннего узла, то он удаляется тривиально, а братья плотно переупорядочиваются слева направо.

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

Таким образом удаление внутреннего узла может привести к рекурсивному удалению вплоть до корня.

Трудоёмкость 2-3-дерева

Что лучше – стратегия разрежения или стратегия уплотнения?

При разрежению мы стремимся к асимптотике

А при уплотнении

13. B-дерево

B-дерево – это обобщение 2-3-дерева, когда любой внутренний узел может иметь число сыновей от до .

значение k – эвристично и выборка его связана с линейным просмотром полей a,b,c,d,e,f,…

В В-деревьях листьями являются области памяти (при постраничной их адресации), но на страницах элементы упорядочены и добавление осуществляется в ЛСС элементов памяти.

Асимптотика – от до

В-деревья являются основой построения индексных файлов (структур индексации) в БД для ускорения нахождения записи (адреса записи в хранилище) представляемое листом В-дерева, а вспомогательные значения a,b,c,d,e,f,… есть значения ключевых выражений некоторых записей.

Зная ключевое выражение поиска можно за логарифмическое время найти запись.

14. Методы разработки алгоритмов

    1. Метод декомпозиции («разделяй и властвуй»)

Суть этого метода: задача разбивается на более простые до тех пор, пока решение не станет тривиальным. С точки зрения трудоёмкости это означает понижение размерности решаемой задачи до тривиального случая, а затем обобщение его до n.

2. Жадный алгоритм («greedy»)

На каждом шаге принимается решение о направлении (о продолжении) поиска решения, исходя из того предположения, что выполняя наилучшее в соответствии с заданным критерием качества последовательности шагов можно получить «хорошее» решение. В жадном алгоритме отсутствуют возвраты к предыдущим шагам, что исключает перебор (даже небольшой) вариантов решений.

3. Динамическое программирование

Принцип Беллмана. Шестой семестр.

4. Переборная схема решения

Метод поиска решения, при котором систематически перебираются все варианты решения. Асимптотика такого перебора – или . Для систематизации полного перебора строится дерево решений, где узлу соответствует точка принятия возможного варианта решения, а число сыновей (т.е. дуг) – количество вариантов развития событий.

Отдельное решение (т.е. кандидат в ответы) – это либо лист, либо путь от корня до листа, как стратегия развития события.

Одним из вариантов уменьшения трудоёмкости на практике является отсечение отдельных ветвей дерева решений на более ранних стадиях без получений листьев. Это такие алгоритмы, как -отсечение, метод ветвей и границ.

Задача - составить расписание теннисного турнира по круговой системе. В один день у каждого игрока не более одной игры. Провести турнир за минимальное число дней.

Жадные алгоритмы

Задача – дать сдачу минимальным количеством монет.

Есть монеты в 1, 5 и 10 копеек. Дать сдачу в 15 коп.

Решение – 10 и 5 копеек – 2 монеты.

Изменим исходные данные. Имеем монеты имени Филатова – 1 5 и 10 копеек.

Тем же алгоритмом – 11 1 1 1 1 = 5 монет – локально-оптимальное решение.

Допустим, в банкомате имени Филатова закончились монеты в 1 копейку (бомжи растащили)

Сдаёт 11 копеек, надо ещё 4 но есть только 5 – всё, решения нет.

Но если сделать это по-другому, то 5*3=15.

Таким образом жадный алгоритм на одних исходных данных может давать глобально оптимальное решение, а на других – либо допустимое (локально-оптимальное) решение, либо вообще не давать решения, не доказывая того факта, что решения действительно нет.

Таким образом можно различать случаи нахождения ГОР – решения задачи, действительно наилучшего из всех возможных вариантов исходных данных – без математического доказательства (например, методом индукции/дедукции) находится полным перебором.

ЛОК – это наилучшее из возможных вариантов решений для конкретных исходных данных (и того алгоритма, который к ним применён).

Задача о монетах принадлежит классу np, для её решения за полиномиальное время были подобраны такие исходные данные, для которых жадный алгоритм получает ГОР.

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

Требования к эвристическому алгоритму:

1. Решение должно быть допустимым

2. И так или иначе давать решение в пределах заданной точности.

Самым простым эвристическим алгоритмом является жадный алгоритм.

Очень симпатичная задачка из Ахо.

Решить задачу коммивояжёра, т.е. найти минимальный гамильтонов цикл, т.е. (по-русски говоря) обойти все вершины графа, посещая каждую вершину ровно 1 раз так, чтобы суммарная длина пути на всём множестве вариантов обхода вершин была бы минимальной.

Пусть у нас шесть городов.

Попробуем получить жадный алгоритм.

Пример жадного алгоритма:

На каждом шаге выбираем ближайшую непосещённую вершину. На последнем шаге замыкаем маршрут (когда непосещённых вершин не осталось).

В таком случае длина этого маршрута оказалась Существует ли маршрут, более короткий?

Вариант б (S=48,39) является кратчайшим (ГОР) и находится полным перебором.

Однако заметим, что оно всего лишь лучше на 4% решения получаемого жадным алгоритмом за полиномиальное время, что позволяет применить жадный алгоритм для решения задачи.

Поиск с возвратом

Ищем – решение. Не дерево, а решение. Возврат – мы возвращаемся к предыдущим шагам и идём поальтернативным веткам развития событий.

За сим я на сегодня с вами проСЧаюсь. Так, курсовые!

Значит, попробуем посмотреть такой граф:

Для задачи коммивояжёра можно предложить следующий алгоритм нахождения нижней границы множества решений, пусть даже такой маршрут нельзя построить – нас интересует идеальное значение, к которому мы будем приближать наше решение в процессе его поиска: для каждой вершины выбираем две минимальные инцидентные дуги за полиномиальное время. Но заметим что такой путь не может быть построен.

Для задачи коммивояжёра дерево поиска решений может иметь в узлах либо до n сыновей либо 2 сына. В каждом узле дерева решений проверяется допустимость текущего (или следующего шага), в нашей задаче это – неповторяемость вершин и образование на последнем шаге цикла.

Находится первое допустимое решение. Это базовое решение на последующих шагах будем пытаться улучшать. Причём некоторые будущие варианты заведомо могут оказаться хуже на более ранних этапах построения дерева решений – такая ветвь сразу отсекается чтоб не ипать моск и мы переходим к следующей ветви, поэтому такой метод называется «методом ветвей и границ».

Другой вариант построения дерева перебора состоит не в переборе вариантов развития ситуации в принятии решения о включении или невключении в ответ кандидата – дихотомия, т.е. выбор одного из двух, поэтому дерево бинарное. В случае задачи коммивояжёра принимается решение о включении или невключении отдельной дуги. Это уже можно осуществлять на основе идеального маршрута длиной 17.5, включая и исключая из него дуги так, чтобы образовался допустимый гамильтонов цикл.

=-====-==-=-===========

Алгоритмы построение и анализ. Кармен Лейзерсон Ривест (Лекции Массачусетского университета).

Прочитать к экзамену элементы теории сложности.

--===============