Метод балансування

Динамічне програмування

Найбільш загальною формою називають процес покрокового рішення задач, коли на кожному кроці вибирається одно значення з безлічі допустимих на цьому кроці, причому таке, яке оптимізує задану мету. У основі програмування лежить принцип оптимальності Беномена. Суть методу:

Часто не вдається розбити завдання на невелику кількість підзадач, об'єднане рішення яких дозволяє отримати рішення шуканих задач.

Виникають 2 можливості:

1. Можна спробувати розділити завдання на стільки завдань, скільки необхідно, потім кожну на ще дрібніші і так далі. Якщо алгоритм зводиться до саме такої послідовності, то отримаємо завдання з експоненціальним часом рішенням.

2. Іноді вдається отримати алгоритм з поліноміальним числом підзадач, і ту або іншу доводитися вирішувати багаторазово. Якщо би відслідковували кожну підзадачу і просто відшукували їх рішення, то можна отримали поліноміальне рішення.

Іноді простіше створити таблицю рішення усіх підзадач незалежно від того, потрібна вона або ні.

Заповнення таблиць - рішення підзадач для отримання рішення певної задачі - в теорії алгоритмів дістало назву динамічного програмування. Форми алгоритмів динамічного програмування можуть бути різними, загальними можуть бути лише заповнені таблиці і порядок заповнення її елементів.

При проектуванні деяких алгоритмів доводитися йти на раз-особисті компроміси, тобто по можливості збалансувати обчислювальні витрати на використання різних частин алгоритми. Метод балансування розглядається як балансування дерев. Дерево - важлива структура даних, вживана для зберігання, обробки і представлення інформації. Дерево складається з елементів^ вершин і зв'язків між ними (дуг). Серед вершин виділяється одна, яка називається коренем. Вона є батьківською по відношенню до інших пов'язаних з нею вершин. Усі вершини, пов'язані з коренем дугами, називаються нащадками. Кожна вершина в дереві, окрім кореня, має точно одну батьківську вершину і більше нащадків. Дерево має дві властивості:

• зв’язність: з кореня треба пройти по дугах до кожної вершини;

• воно не містить циклів, тобто замкнутих послідовностей вершин і дуг.

У комп'ютерних науках часто використовуються дерева, в яких усі вершини містять обмежене число нащадків (не більше двох).

Якщо це число 2 (0,1,2), то такі дерева називаються бінарними. Якщо у вершини два нащадки, те дерево ділиться на ліве піддерево і праве. Розрізняють ідеальні і вироджені дерева.

Ідеальне дерево - дерево, в якому усі вершини розташовуються на k рівнях: корінь - на 1-му, дві вершини на 2-му, чотири - на 3-му. Нова вершина може бути поміщена тільки на k+1 рівень.

Вироджене дерево - дерево, яке є лінійним списком елементів, впорядкованих за збільшенням або зменшенням інформаційних полів.

Критерій якості дерева - це довжина найдовшої гілки. На одиницю від цього значення відрізняється кількість рівнянь дерева, тобто її висота (на одиницю менше). Дерева мінімальної висоти мають максимальну кількість вершин на одному рівні. Таким чином хороші з точки зору пошуку і вставки вершини - це дерева мінімальної висоти. Вони мають мінімальну кількість вершин на кожному рівні.

Метод балансування - метод що дозволяє не допустити занадто поганих дерев.

Суть: дерево називається збалансованим, якщо висота hl лівого піддерева і висота hr правого піддерева для кожної вершини відрізняються не більше ніж на одиницю. Кращі зі збалансованих дерев є ідеальними. При включенні нової вершини в дерево може (але не обов’язково) збільшуватися висота одного з дерев.

Можливі 3 ситуації.

1. Вершина включається в піддерево меншої висоти, його висота збільшується на одиницю, дерево ставає збалансованим (ідеальним).

2. Піддерева мають однакову висоту. При включенні нової вершини, висота однієї з них збільшується на одиницю, дерево залишається збалансованим.

3. Вершина включається в піддерево більшої висоти, різниця висот ставає рівною двом. Дерево стає незбалансованим. Варіанти рішення: треба гілці одного з піддерев підняти на одну одиницю і одночасно на одиницю опустити інше. Ця модифікація призводить до зміни форми дерева. Піднімаючи ліве піддерево, включаючи його корінь, тим самим, робиться рівень кореня лівого піддерева вищим, ніж корінь самого дерева. Отже, корінь лівого піддерева стає коренем усього дерева. В цьому випадку доведеться змінити деякі зв'язки між вершинами, оскільки якщо корені міняються ролями, то на зворотні міняються і відношення пращур-нащадок.

Дата добавления: 2014-11-08