Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке жадібний алгоритм?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Жадібний алгоритм** - це підхід, який на кожному кроці робить локально найкращий (найвигідніший) вибір, не переглядаючи вже прийняті рішення, сподіваючись, що послідовність таких виборів приведе до глобально оптимального рішення. **Ключове:** рішення незворотні - вони фіксуються і ніколи не переглядаються.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Жадібний алгоритм - це підхід, який на кожному кроці робить локально найкращий (найвигідніший) вибір, не переглядаючи вже прийняті рішення, сподіваючись, що послідовність таких виборів приведе до глобально оптимального рішення. ## Детальний розбір ### Визначення та інтуїція Жадібні алгоритми будують рішення крок за кроком, щоразу обираючи варіант, який здається найкращим "тут і зараз" за певним критерієм (жадібна евристика). Ключова особливість: рішення незворотні - вже вибрані елементи не переглядаються. ### Ключова ідея - Локальний оптимум: обрати найкращий наступний крок за метрикою. - Незворотність: рішення фіксуються і не відкочуються. - Доведення: часто через аргумент обміну (exchange argument) або індукцію. ### Коли жадібність дає оптимум - Є оптимальна підструктура: оптимум задачі складається з оптимумів підзадач. - Виконується властивість жадібного вибору: існує оптимальне рішення, що починається з жадібного кроку. - Класичні приклади: - Відбір інтервалів, що не перетинаються (activity selection) - сортування за раннім закінченням. - Мінімальне остовне дерево: Kruskal/Prim. - Найкоротші шляхи: Дейкстра за невід'ємних ваг. - Код Хаффмана. - Розмін монет за канонічних систем номіналів (наприклад, 1, 2, 5, 10, ...). ### Коли жадібність не працює - Рюкзак 0/1: жадібний вибір за ціною/вагою не гарантує оптимуму. - Розмін монет для довільних номіналів, напр. [1, 3, 4] і сума 6: жадібно 4+1+1 (3 монети), оптимально 3+3 (2 монети). - Найкоротші шляхи з від'ємними ребрами - потрібен Bellman-Ford. - Інтервали з вагами (weighted interval scheduling) - потрібне динамічне програмування. ### Шаблон розробки жадібного рішення 1. Сформулюйте метрику жадібного вибору (що означає «найвигідніше»). 2. Відсортуйте дані або підготуйте структуру для швидкого вибору найкращого кандидата. 3. Ітеруйтеся, щоразу роблячи жадібний вибір і фіксуючи його. 4. Доведіть коректність: аргумент обміну або індукція + властивість оптимальної підструктури. 5. Оцініть складність: зазвичай O(n log n) через сортування або роботу черг із пріоритетом. ### Приклад 1: Відбір інтервалів, що не перетинаються Задача: обрати максимум інтервалів, що не перетинаються. Жадібна евристика: завжди брати інтервал із найранішим часом закінчення. ``` function selectActivities(intervals) { // intervals: [{ start: number, end: number }] intervals.sort((a, b) => a.end - b.end); const result = []; let currentEnd = -Infinity; for (const it of intervals) { if (it.start >= currentEnd) { result.push(it); currentEnd = it.end; } } return result; // Максимальна за розміром множина інтервалів, що не перетинаються } // Приклад const intervals = [ { start: 1, end: 3 }, { start: 2, end: 5 }, { start: 0, end: 6 }, { start: 5, end: 7 }, { start: 8, end: 9 }, { start: 5, end: 9 } ]; console.log(selectActivities(intervals)); // Складність: O(n log n) через сортування; доведення - через аргумент обміну. ``` ### Приклад 2: Розмін монет (канонічна система) Жадібна евристика: завжди брати максимально можливий номінал. Коректно для канонічних систем (наприклад, 1, 2, 5, 10). ``` def greedy_change(amount, coins): coins = sorted(coins, reverse=True) result = [] for c in coins: cnt = amount // c if cnt > 0: result.append((c, cnt)) amount -= cnt * c return result # Приклад print(greedy_change(28, [1, 2, 5, 10])) # Вивід: [(10, 2), (5, 1), (2, 1), (1, 1)] # Примітка: для довільних номіналів жадібний підхід може бути неоптимальним. ``` ### Доведення коректності (нарис): аргумент обміну Ідея: порівнюємо жадібне рішення G з оптимальним O. Покажемо, що можна поступово перетворити O на рішення, яке починається з жадібного вибору, не погіршуючи якість. Повторюючи перетворення, отримаємо рішення, що збігається з G, отже, G оптимальне. Наприклад, у задачі про інтервали будь-який оптимальний набір можна «переставити» так, щоб його перший інтервал закінчувався не пізніше жадібного, не зменшуючи потужності множини. ### Сильні та слабкі сторони - Плюси: простота реалізації, висока швидкість (часто O(n log n)), низьке споживання пам'яті. - Мінуси: не завжди гарантує оптимум; важливе доведення або контрприклад. ### Коротка пам'ятка для співбесіди - Сформулюйте жадібний критерій і поясніть, чому він розумний. - Назвіть випадки застосовності (інтервали, MST, Дейкстра ≥ 0, Хаффман). - Наведіть контрприклад, де жадібність ламається (рюкзак 0/1, монети [1,3,4]). - Коротко опишіть доведення через аргумент обміну.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.