Що таке жадібний алгоритм?

АлгоритмиJunior~2 хв читання

Коротка відповідь

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

Детальний розбір

Визначення та інтуїція

Жадібні алгоритми будують рішення крок за кроком, щоразу обираючи варіант, який здається найкращим "тут і зараз" за певним критерієм (жадібна евристика). Ключова особливість: рішення незворотні - вже вибрані елементи не переглядаються.

Ключова ідея

Локальний оптимум: обрати найкращий наступний крок за метрикою.
Незворотність: рішення фіксуються і не відкочуються.
Доведення: часто через аргумент обміну (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) - потрібне динамічне програмування.

Шаблон розробки жадібного рішення

Сформулюйте метрику жадібного вибору (що означає «найвигідніше»).
Відсортуйте дані або підготуйте структуру для швидкого вибору найкращого кандидата.
Ітеруйтеся, щоразу роблячи жадібний вибір і фіксуючи його.
Доведіть коректність: аргумент обміну або індукція + властивість оптимальної підструктури.
Оцініть складність: зазвичай 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]).
Коротко опишіть доведення через аргумент обміну.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.