Поняття та види стратегій

IV. АЛГОРИТМІЧНІ СТРАТЕГІЇ

Поняття алгоритмічної стратегії дозволяє класифікувати базові алгоритми обробки даних по групах їх використання. Сучасніше розуміння терміну відноситься до програмних реалізацій алгоритмів.

Стратегія,Strategy - поведінковий шаблон проектування, призначений для визначення сімейства алгоритмів, інкапсуляції кожного з них і забезпечення їх взаємозамінюваності. Це дозволяє вибирати алгоритм шляхом визначення відповідного класу. Шаблон Strategy дозволяє міняти вибраний алгоритм незалежно від об'єктів- клієнтів, які його використовують.

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

До базових алгоритмів програмування можна віднести:

- Алгоритми роботи із структурами даних. Вони визначають базові принципи і методологію, використовувані для реалізації, аналізу і порівняння алгоритмів. Дозволяють отримати уявлення про методи представлення даних. До таких структур відносяться зв'язні списки і рядки, дерева, абстрактні типи даних, такі як стеки і черги.

- Алгоритми сортування, призначені для впорядкування масивів і файлів, мають особливу важливість. З алгоритмами сортування пов'язані, зокрема, черги по пріоритету, завдання вибору і злиття.

- Алгоритми пошуку, призначені для пошуку конкретних елементів у великих колекціях елементів. До них відносяться основні і розширені методи пошуку з використанням дерев і перетворень цифрових ключів, у тому числі дерева цифрового пошуку, збалансовані дерева, хешування, а також методи, які підходять для роботи з дуже великими файлами.

- Алгоритми на графах корисні при рішенні ряду складних і важливих завдань. Загальна стратегія пошуку на графах розробляється і застосовується до фундаментальних завдань зв'язності, у тому числі до завдання відшукування найкоротшого шляху, побудови мінімального остовного дерева, до завдання про потоки в мережах і завданні про паросочетаниях. Уніфікований підхід до цих алгоритмів показує, що в їх основі лежить одна і та ж процедура, і що ця процедура базується на основному абстрактному типі даних черги по пріоритету.

- Алгоритми обробки рядків включають ряд методів обробки (довгих) послідовників символів. Пошук в рядку призводить до зіставлення з еталоном, що у свою чергу веде до синтаксичного аналізу. До цього ж класу завдань можна віднести і технології стискування файлів.

- Геометричні алгоритми - це методи рішення завдань з використанням точок і ліній (і інших простих геометричних об'єктів), які увійшли до вживання досить нещодавно. До них відносяться алгоритми побудови опуклих оболонок, заданих набором точок, визначення перетинів геометричних об'єктів, рішення завдань відшукування найближчих точок і алгоритму багатовимірного пошуку. Багато хто з цих методів доповнює прості методи сортування і пошуку.

Виділимо алгоритмічні стратегії, які використовуються в алгоритмах :

- алгоритми грубої сили;

- жадібні алгоритми;

- "Розділяй і володарюй";

- алгоритми з поверненням;

- евристичні алгоритми;

- зіставлення із зразком і алгоритми обробки рядків/текстів;

- алгоритми чисельної апроксимації;

- online- і offline-алгоритми;

- динамічне програмування; і інші.

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

Представимо основні парадигми.

Рекурсія - фундаментальне поняття в математиці і комп'ютерних науках. У мовах програмування рекурсивною програмою називається програма, яка звертається сама до себе. Рекурсивна програма не може викликати себе до безкінечності, отже, друга важлива особливість рекурсивної програми - наявність умови завершення, що дозволяє програмі припинити викликати себе.

Таблиця 4.1. Основні алгоритмічні стратегії

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

Така алгоритмічна парадигма називається рекурсивною декомпозицією. Алгоритми, засновані на рекурсивній декомпозиції, аналізуються за допомогою рекурентних стосунків. Приклад рекурентного відношення визначення функції факторіалу :

Рекурсивну програму завжди можна перетворити в нерекурсивну (ітеративну, використовуючу цикли), яка виконує ті ж обчислення. І навпаки, використовуючи рекурсію, будь-яке обчислення, що припускає використання циклів, можна реалізувати, не прибігаючи до циклів.

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

Наприклад, при спробі вичислити числа Фібоначчі за рекурсивною схемою F(i) = F(i - 1) + F(i - 2), при N >= 1; F(0) = 0; F(1) = 1;

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

Кількість рекурсивних викликів при обчисленні значення F(N) за такою схемою може бути отримана з рішення рекурентного виразу T_N = T_N-1 + T_N-2, при N>=1; T₀ = 1; T₁ = 1, де

T_N приблизно рівний Ф^N, де Ф~1.618 - золота пропорція, тобто приведена вище програма зажадає експоненціальних тимчасових витрат на обчислення.

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

Ідея рекурсивного або звичайного розподілу сходить до технологічного прийому - модульного програмування. У своєму початковому варіанті вона припускає розбиття на завдання різної природи. Не рекурсивний розподіл дозволяє досягти певного ефекту за рахунок розбиття завдання на безліч ідентичних завдань меншої розмірності з наступним об'єднанням результату. Застосування того ж самого алгоритму рекурсивне до отриманих підзадач дає наступний клас алгоритмів - рекурсивний розподіл. Як правило, незалежність отриманих підзадач має на увазі відповідний розподіл початкових даних завдання на підмножини, що не перетинаються, - цьому і відповідає сам термін розподіл. Ефективність (і трудомісткість) таких алгоритмів, залежить від витрат на само розподіл і від пропорцій частин, що розділяються : кращому випадку відповідає ділення на рівні частини (логарифмічні залежність), гіршому - виділення єдиного елементу (лінійні залежності).

Жадібні алгоритми. Ідеальним випадком можна вважати алгоритм, здатний "вибрати з декількох зол" єдино правильне. У основі його так само лежить принцип розподілу, але в кожній точці він має основу вибрати одну з підзадач. Зазвичай це робиться на підставі особливостей організації оброблюваних даних або їх надмірності. Основою жадібних алгоритмів є завжди досить спірне твердження: рух "по лінії найменшого опору" в кожній точці приведе до бажаного результату.

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

Динамічне програмування. В процесі породження дерева рекурсивних викликів можливе повторення підзадач з одними і тими ж даними. Якщо запам'ятовувати результат їх виконання, то ефективність алгоритму може бути значно збільшена. Вивчення рекурсії нерозривно пов'язане з вивченням рекурсивно визначуваних структур даних, званих деревами (trees). Дерева використовуються як для спрощення розуміння і аналізу рекурсивних програм, так і в якості явних структур даних. У свою чергу, рекурсивні програми використовуються для побудови дерев. Глобальний зв'язок між ними (і рекурентними стосунками) використовується при аналізі алгоритмів. Багато алгоритмів використовують два рекурсивні виклики, кожен з яких працює приблизно з половиною вхідних даних. Така рекурсивна схема, по- видимому є найбільш важливим випадком добре відомого методу "розділяй і володарюй" (divide and conquer) розробки алгоритмів. В якості прикладу розглянемо завдання відшукування максимального з N елементів, збережених в масиві a[1], . . ., a[N] з елементами типу Item. Це завдання легко може бути вирішене за один прохід масиву

Рекурсивне рішення типу "розділяй і володарюй ще один простий (хоча абсолютно інший) спосіб рішення тієї ж задачі :

Більшість сучасних мов високого рівня підтримують механізм рекурсивного виклику, коли функція, як елемент структури мови програмування, повертає вичислене значення по своєму імені, може викликати сама себе з іншим аргументом. Ця можливість дозволяє безпосередньо реалізовувати обчислення рекурсивно певних функцій. Відмітимо, що через тезу Черча - Тюринга апарат рекурсивних функцій Черча равний за потужністю машині Т'юринга, і, отже, будь-який рекурсивний алгоритм може бути реалізований ітераційно.

Найчастіше підхід "розділяй і володарюй" використовують через те, що він забезпечує швидші рішення, ніж ітераційні алгоритми. Основним недоліком алгоритмів типу "розділяй і володарюй" являється те, що ділять завдання на незалежні підзадачі. Коли підзадачі незалежні, це часто призводить до неприпустимо великих витрат часу, оскільки одні і ті ж підзадачі починають вирішуватися багато разів.

Аналіз трудомісткості рекурсивних реалізацій алгоритмів, очевидно, пов'язаний як з кількістю операцій, що виконуються при одному виклику функції, так і з кількістю таких викликів. Графічне представлення породжуваного цим алгоритмом ланцюжка рекурсивних викликів називається деревом рекурсивних викликів. Детальніший розгляд призводить до необхідності обліку витрат як на організацію виклику функції і передачі параметрів, так і на повернення вичислених значень і передачу управління в точку виклику. Можна помітити, що деяка гілка дерева рекурсивних викликів обривається досягши такого значення передаваного параметра, при якому функція може бути вичислена безпосередньо. Таким чином, рекурсія еквівалентна конструкції циклу, в якому кожен прохід є виконання рекурсивної функції із заданим параметром. Дерево рекурсивних викликів може мати і складнішу структуру, якщо на кожному виклику породжується декілька звернень - фрагмент дерева рекурсій для чисел Фібоначчі представлений на рис. 4.1.

Рис. 4.1. Фрагмент дерева рекурсії при обчисленні чисел Фібоначчі