"Жадібні" алгоритми

15

“Жадібні” алгоритми

(реферат)

1. Види жадібних алгоритмів

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

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

2. Градієнтний метод

Одним з прикладів жадібних алгоритмів є градієнтний метод. Він використовується, якщо допустима множина розв'язку D=Rⁿ (n - розмірний евклідовий простір), а цільова функція диференційована. Градієнтом функції у точці х=(x₁ .. x_n) називається вектор

.

Градієнт задає задає напрямок найшвидшого зростання функції. Тоді у градієнтному методі , де k - номер ітерації, л - величина кроку у напрямку антиградієнта.

Аналогія - знайти найвищу точку на горбистій місцевості із зав'язаними очима.

Досягається локальний, а не глобальний екстремум.

3. Алгоритм Пріма

Для графа G=<V, E> задані ваги його ребер. Остовим деревом графу G є неорієнтоване дерево T=<V, E^/>, яке містить всі вершини графу . Вартість остового дерева визначається як вартість його ребер.

Алгоритм Пріма полягає в знаходженні остового дерева мінімальної вартості.

Остове дерево будують крок за кроком, додаючи до нього по одному ребру за певним оптимізаційним критерієм.

Побудова дерева починається з ребер, що мають мінімальну вартість.

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

Приклад використання алгоритму Пріма:

Дано граф G:

Процес побудови остового дерева:

4. Алгоритм Крускала

Алгоритм Краскала відрізняється від алгоритма Пріма тим, що одночасно будується не одне остове дерево, а кілька дерев одночасно (ліс). По мір зростання окремих дерев вони об'єднуються в спільне остове дерево.

Нові вершини можуть приєднуватися тільки до активних вершин (голови купи).

Розглянемо роботу алгоритму Крускала до графу

Послідовність кроків побудови остового дерева

Результуюче остове дерево

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

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

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

Числа Фібоначчі

Розглянемо техніку динамічного програмування на класичному прикладі побудови послідовності чисел Фібоначчі. N-не число Фібоначчі рекурсивно визначається так:

Потрібно написати програму, яка обчислює N-не число Фібоначчі. Цю задачу можна вирішити двома способами: за допомогою рекурсії або за допомогою динамічного програмування.

Рекурсивний спосіб можна реалізувати функцією:

Function Fib(n:integer):integer;

Begin

if n=0 then fib:=1;

else if n=1 then fib:=1;

else fib:=fib(n-1)+fib(n-2);

End;

Недоліком рекурсії є обчислення чисел Фібоначчі, менших N, по кілька разів. В дин. програм. для обчислення чисел Фібоначчі використовують дві змінні, які зберігають значення двох останніх чисел. Наступне число визначається через два попередніх.

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

6. Вирішувач інтелектуальних задач

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

6.1 Загальний вирішувач задач

В кінці 50-х й на початку 60-х розвивалася програма „Загальний вирішувач задач” (GPS - Ge). В рамках цієї програми створено програму „Логік-теоретик” (А. Ньюелл, Г. Саймон, Дж. Шоу) для доведення теорем математичної логіки (генерація гіпотези й перевірка її істиності).

Схема прийняття рішення наступна:

1. Проаналізувати поточну ситуацію.

2. Порівняти ситуацію з бажаною; якщо відмінностей немає - кінець роботи.

3. З'ясувати, які оператори можна застосувати для зменшення існуючої різниці.

4. Послідовно застосовувати знайдені оператори.

5. Повернутися на крок 1.

Задача про мавпу і банани (стати на скриньку). Метод виявився не достатньо універсальним - його не вдалося використати для гри в шахи.

6.2 Ігрові задачі як задачі прийняття рішень

Ігрові задачі - планування цілеспрямованих дій і прийняття рішень. Характерна особливість ігрових задач - наявність суперника.

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

Розглянемо найпростіший тип ігор - одно крокові антагоністичні ігри.

6.3 Основи теорії однокрокових ігор

Нехай грають два гравця А і В.

Гравець А може вибрати одну з m стратегій б_i, i=1..m.

Гравець В може вибрати одну з n стратегій в_j, j=1..n, .

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

Одно крокові антагоністичні ігри характеризуються матрицею виграшів, елементи якої дорівнюють виграшам одного з гравців (А).

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

6.4 Позиційні ігри з оптимальними стратегіями

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

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

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

1. Кожна вершина дерева відповідає окремій позиції.

2. Корінь дерева відповідає позиції, що аналізується.

3. Листки дерева відповідають завершальним позиціям з відомою функцією виграшу.

4. Дуги відповідають ходам.

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

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

Дерево гри може бути експліцитним (задається явно) й імпліцитним (породжується по мірі необхідності).

Для пошуку по дереву використовують стратегії в ширину та глибину.

Процедура, яка дозволяє знайти оптимальну стратегію, називається мінімаксною.

Мінімаксна процедура є процедурою повного перебору, яка задається правилами:

1. Мінімаксна оцінка завершальних позицій дорівнює функції виграшу.

2. Мінімаксна оцінка альфа-вершини дорівнює максимуму мінімаксних оцінок безпосередніх наступників.

3. Мінімаксна оцінка бета-вершини дорівнює мінімуму мінімаксних оцінок безпосередніх наступників.

Розглянемо дерево гри:

Рис.19.1. Аналіз на основі мінімаксної процедури, виділено оптимальний варіант для оптимальної гри суперників.

Розрахуємо кількість позицій для гри в шахи. Якщо на кожному кроці можна зробити 30 ходів, а партія складається з 80 півходів , то кількість позицій 30⁸⁰.

Обмеження глибини перебору

Для обмеження перебору звичайно зменшують глибину перебору d. Горизонтом для даної позиції називають множину позицій для глибини d.

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

В шашках статична оцінка може бути обчислена як функція 6k+4m+u, де k - перевага в дамках, m - у простих шашках, u - перевага в рухливості.

7. Альфа - бета відтинання

Альфа-бета відтинання є одним зі способів скорочення перебору.

Відтинанням у деякій вершині називається припинення аналізу цієї вершини разом з усіма її наступниками.

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

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

Попередня оцінка бета-вершини дорівнює мінімуму з остаточних оцінок безпосередніх наступників.

Правила відтинань:

1. Відтинання у альфа-вершині відбувається, коли попередня оцінка цієї вершини стає не меншою, ніж попередня оцінка будь-якого бета-попередника.

2. Відтинання у бета-вершині відбувається, коли попередня оцінка цієї вершини стає не більшою, ніж попередня оцінка будь-якого альфа-попередника.

Рис.19.2. Ілюстрація альфа-бета відтинань

Якщо глибина перебору d, а b - коефіцієнт розгалуження, то при повному переборі потрібно розглядати варіантів b^d. Альфа-бета відтинання потребує приблизно 4b^d/2 позицій.

Огляд сучасних шахових програм

Програми Hiarch, Rebel, Mchess при виконанні на процесорах Pentium показують якість гри на рівні гросмейстерів.

Спеціалізований шаховий комп'ютер RS/6000 в 1997 році виграв у Каспарова з рахунком 3,5 на 2,

Прогрес шахових програм досягнуто:

1. За рахунку зростання швидкості обчислень.

2. Використанням дебютних та ендшпіль них бібліотек.

3. Бібліотека найкращих ходів.

4. Метод форсованих варіантів (перевіряються форсовані варіанти нижче глибини перебору - шахи і взяття фігур).

8. Евристичні алгоритми

8.1 Евристики як засіб зменшення перебору

Евристики - правила субоптимальної поведінки в певних ситуаціях.

Прислів'я - приклади евристик (Сім разів відміряй, а потім відріж).

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

8.2 Задача розфарбовування графу

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

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

Нехай G=(V, E) - неорієнтований граф, для якого є n вершин. Розфарбовуванням графу називатимемо відображення ц множини V на множину С таку, що С=с₁ .. с_m. Елементи множини С називатимемо фарбами.

Вірним розфарбовуванням графу називатимемо таке, при якому дві суміжні вершини розфарбовані різними кольорами. Вірне розфарбовування розбиває множини V на m хроматичних класів.

Хроматичним числом ч(G) називають мінімальне число фарб. Називатимемо граф k-розфарбовуванням, якщо ч(G)<>k, тa хроматичним, якщо ч(G)=k.

З розфарбовуванням графу пов'язано дві задачі: 1) знайти хроматичне число графу ч(G); 2) знайти хоча б одне вірне розфарбовування.

Для планарного графу доведено гіпотезу, що його можна розфарбувати не більше ніж 4-ма фарбами.

8.3.Точні та евристичні методи розфарбовування

Точні методи мають експоненційну складність.

Для графу G кількість фарб ч(G)<=k<=n.

Теорема Кенінга. Граф є біхроматичним (2-х хроматичним), тоді й тільки тоді, коли він не містить непарних простих циклів. З теореми випливає, що будь-яке дерево є біхроматичним.

Для оцінки верхнього значення хроматичного числа графу використовується Теорема Уелша-Пауел. Нехай у графі G вершини впорядковані за спаданням степенів. Тоді

.

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