Методи розробки алгоритмів

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

Метод частинних цілей

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

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

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

Метод сходження

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

Дерева розв'язків

Багато складних реальних задач можна змоделювати за допомогою дерев розв'язків. Кожний вузол дерева представляє один крок вирішення задачі. Кожна гілка в дереві представляє розв'язок, який веде до більш повного рішення. Листки є остаточним розв'язком. Мета полягає в тому, щоб знайти «найкращий шлях» від кореня дерева до листка при виконанні певних умов. Ці умови і значення поняття «найкращий» для шляху залежить від конкретної задачі.

Метод відпрацювання назад

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

Програмування з поверненнями назад

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

Метод спроб та помилок

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

Альфа-бета відсікання

Одна дуже проста умова дозволяє позбавитися від розгляду значної частини типового дерева гри. Цикл (6) в алгоритмі може ігнорувати певних нащадків, досить часто доволі велику їх кількість.

Загальне правило відсікання вузлів зв'язане з поняттям кінцевих і приблизних значень вузлів. Кінцеве значення — це то, що називають виграшем. Приблизне значення — це верхня межа значення вузла в режимі MIN, або нижня межа значення вузла в режимі MAX. Приведемо правила обчислення цих значень.

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

2.Якщо орієнтовне значення вузла в режимі MAX рівне v1, а кінцеве значення одного з його нащадків рівне v2, тоді встановити приблизне значення вузла рівним max(v1,v2). Якщо вузол знаходиться в режимі MIN — min(v1,v2).

3. Якщо p є вузлом в режимі MAX, і має батька q, а приблизні значення вузлів рівні v1 і v2, відповідно, причому v1<v2, тоді можна відсікти всіх нерозглянутих нащадків вузла p, якщо p є вузлом в режимі MAX, а q є, таким чином в режимі MIN, і v2<v1.

Метод гілок і границь

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

Див. також

• Розділяй та володарюй (інформатика)
• Динамічне програмування

Джерела

• Методи розробки алгоритмів: Тексти лекцій / О. В. Костів, С. А. Ярошко; Львів. нац. ун-т ім. І.Франка. — Л., 2002. — 99 c. — Бібліогр.: 10 назв.

Посилання

• Теорія алгоритмів і математична логіка