Що означає 'жадібний критерій вибору'?

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

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

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

Розгорнуте пояснення

Що це означає формально

Жадібний алгоритм будує рішення покроково, щоразу обираючи «найкращий на зараз» елемент за певним правилом. Жадібний критерій вибору - це обґрунтування того, що такий локальний вибір не зіпсує можливість досягти глобального оптимуму. Зазвичай це спирається на дві властивості задачі:

Оптимальна підструктура: оптимальне рішення задачі містить оптимальні рішення її підзадач.
Властивість жадібного вибору (greedy-choice property): існує оптимальне рішення, яке починається з певного локально оптимального вибору; отже, зробивши цей вибір, ми не втратимо оптимальність.

Коли критерій виконується: типові задачі

Вибір інтервалів, що не перетинаються (activity selection): завжди брати інтервал із найранішим часом закінчення - дає максимум сумісних інтервалів.
Мінімальні остовні дерева (Kruskal/Prim): «властивість розрізу» гарантує, що щоразу можна брати мінімальне ребро, яке перетинає деякий розріз, і це безпечно.
Найкоротші шляхи від джерела за невід'ємних ваг (Dijkstra): завжди обираємо вершину з мінімальною поточною оцінкою відстані; за невід'ємних ваг це безпечно.
Код Хаффмана: на кожному кроці об'єднуємо два найменші за частотою вузли - це веде до оптимального префіксного коду.
Здача монетами для «канонічних» номіналів (наприклад, 1, 5, 10, 25): брати завжди найбільшу підходящу монету - оптимально.

Коли не працює: контрприклади

Здача монетами за номіналів {1, 3, 4}: для суми 6 жадібність дає 4+1+1 (3 монети), оптимум - 3+3 (2 монети).
Рюкзак 0/1: брати предмет із найбільшою цінністю/вагою часто не оптимально (жадібність працює лише для дробового рюкзака).
Найкоротші шляхи з від'ємними вагами: жадібний вибір Dijkstra некоректний; потрібен Bellman-Ford.

Як доводять коректність жадібного алгоритму

Аргумент перестановки (exchange argument): показують, що будь-який оптимум можна «підправити», замінивши його перший вибір на жадібний, не погіршивши результат.
Властивість розрізу/циклів (для графів): мінімальне ребро через розріз завжди безпечне; максимальне на циклі - небезпечне (для MST).
Матроїдна структура: якщо множина допустимих рішень утворює матроїд, жадібний алгоритм оптимальний для будь-якої монотонної функції ваги.
Індукція за кроками: після кожного жадібного кроку залишається підзадача того самого типу, до якої застосовний той самий аргумент.

Шаблон проектування жадібного рішення

Сформулюйте ціль (що максимізуємо/мінімізуємо).
Визначте множину допустимих рішень і обмежень.
Запропонуйте локальне правило вибору (жадібний крок).
Доведіть властивість жадібного вибору (зазвичай обміном) та оптимальну підструктуру.
Реалізуйте: сортування/структури даних + однопрохідний вибір.
Оцініть складність і розберіть крайні випадки.

Приклад: вибір максимального числа інтервалів, що не перетинаються

Правило: завжди брати наступний інтервал із мінімальним часом закінчення, який сумісний із уже вибраними.

// intervals: масив об'єктів { start, end }
function selectActivities(intervals) {
  // 1) Сортуємо за часом закінчення
  intervals.sort((a, b) => a.end - b.end);

  const result = [];
  let lastEnd = -Infinity;

  // 2) Ідемо зліва направо, додаючи перший сумісний інтервал
  for (const it of intervals) {
    if (it.start >= lastEnd) {
      result.push(it);
      lastEnd = it.end;
    }
  }
  return result; // максимальний за розміром набір інтервалів, що не перетинаються
}

// Приклад
const input = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 },
];
console.log(selectActivities(input));

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

Контрприклад до жадібності (coin change)

Жадібний вибір «брати найбільшу монету, що не перевищує залишок» не завжди оптимальний:

Номінали: {1, 3, 4}
Сума: 6
Жадібний: 4 + 1 + 1 = 3 монети
Оптимум: 3 + 3 = 2 монети

Чек-лист на співбесіді

Що оптимізуємо і які обмеження?
Яке локальне правило здається природним?
Чи можна довести властивість жадібного вибору (обміном/розрізом/матроїдом)?
Чи є контрприклади? Якщо так - потрібна динаміка/пошук/наближення.
Складність і структури даних (сортування, черги з пріоритетом).

Не плутати з «жадністю» в регулярках

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

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

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

Premium

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