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

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

Наприклад, використання жадібної стратегії для задачі комівояжера породжує такий алгоритм: «На кожному етапі вибирати найближче з невідвіданих міст».

Специфіка

Зазвичай, жадібний алгоритм базується на п'яти принципах:

1. Набір можливих варіантів, з яких робиться вибір;
2. Функція вибору, за допомогою якої знаходиться найкращий варіант, який буде додано до розв'язку;
3. Функція придатності, яка визначає придатність отриманого набору;
4. Функція цілі, передає значення розв'язку або частковому розв'язку;
5. Функція розв'язку, яка вказує на те, що кінцевий розв'язок знайдено.

Визначання придатності

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

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

Критерії застосування

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

Принцип жадібного вибору

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

Властивість оптимальної підструктури

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

Коли алгоритми жадібного типу зазнають невдачі

Жадібні алгоритми можна охарактеризувати як «короткозорі» і «невідновлювані». Вони ідеальні лише для задач з «оптимальною підструктурою». Попри це, жадібні алгоритми найкраще підходять для простих задач. Для багатьох інших задач жадібні алгоритми зазнають невдачі у продукуванні оптимального розв'язку, і можуть навіть видати найгірший з можливих розв'язків. Один з прикладів — алгоритм найближчого сусіднього міста, згаданий вище.

Приклади

Розмін монет

Задача. Монетна система деякої держави складається з монет вартістю $a_{1}=1<a_{2}<...<a_{n}$. Вимагається видати суму S найменшою можливою кількістю монет.

Жадібний алгоритм розв'язання цієї задачі такий. Беремо найбільшу можливу кількість монет вартості $a_{n}$: $x_{n}=\lfloor S/a_{n}\rfloor$. Так само знаходимо скільки потрібно монет меншого номіналу і т. д.

Для цієї задачі жадібний алгоритм не завжди дає правильний розв'язок. Наприклад, суму 10 копійок монетами вартістю 1, 5 і 6 коп. жадібний алгоритм розміняє так: 6 коп. — 1 шт., 1 коп. — 4 шт., в той час як правильний розв'язок — 2 монети по 5 копійок. Проте, на всіх реальних монетних системах жадібний алгоритм видає правильну відповідь.

Вибір заявок

Задача. На конференції, щоб відвести більше часу на неформальне спілкування, різні секції рознесли по різних аудиторіях. Вчений із надзвичайно широкими інтересами бажає відвідати декілька доповідей у різних секціях. Відомі початок $s_{i}$ і кінець $f_{i}$ кожної доповіді. Визначити, яку найбільшу кількість доповідей можна відвідати.

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

Activity-Selector(s,f)

1. $n\leftarrow$ length[s]
2. $A\leftarrow \left\{1\right\}$
3. $j\leftarrow 1$
4. for $i\leftarrow 2$ to n
   • do if $s_{i}\geq f_{j}$
     • then $A\leftarrow A$ ∪ {i}
       • $j\leftarrow i$
5. return A

На вхід алгоритму подаються масиви початків і закінчень доповідей. Множина А складається з номерів вибраних заявок, а j — номер наступної заявки. Жадібний алгоритм шукає заявку, що починається не раніше від закінчення j-ї, потім знайдену заявку включає в А, а j присвоює її номер.

Алгоритм працює за $O(n\log n)$, тобто за складністю сортування, оскільки вибірка має меншу складність $O(n)$. На кожному кроці вибирається найкращий розв'язок. Покажемо, що результатом буде оптимальний розв'язок.

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

Див. також

• Евристичний алгоритм
• Жадібний алгоритм Радо-Едмондса

Література

• Томас Кормен, Чарльз Лейзерсон, Рональд Рівест і Кліффорд Штайн. Вступ в алгоритми, 2-ге видання. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Розділ 16.

Посилання

• Greedy algorithm visualization [Архівовано 30 серпня 2009 у Wayback Machine.] Візуалізація задачі N ферзів (розташувати на дошці N*N, так щоб жоден з них не атакував іншого).