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

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

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

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

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

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

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

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

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

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

Activity-Selector(s,f)

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

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

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

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

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

• Greedy algorithm visualization Візуалізація задачі N ферзів (розташувати на дошці N*N, так щоб жоден з них не атакував іншого).