Що означає локально оптимальний вибір у жадібному алгоритмі?

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

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

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

Розгорнута відповідь

Що означає «локально оптимальний вибір»

Це стратегія: з усіх доступних на поточному кроці варіантів обирається той, який здається найкращим за локальним критерієм (наприклад, «найраніша дата закінчення», «найбільша щільність цінності», «найменша вага ребра»). При цьому алгоритм не робить відкатів і не переглядає рішення - він будує відповідь крок за кроком.

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

Коли жадібність дає глобально оптимальну відповідь

Щоб локально оптимальні кроки склалися в глобально оптимальне рішення, зазвичай потрібні дві властивості задачі:

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

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

Де це працює

Відбір інтервалів, що не перетинаються (максимум заходів): обирати активність із мінімальним часом закінчення.
Мінімальний остов (Kruskal/Prim): завжди брати найменше ребро, що не утворює цикл.
Оптимальне префіксне кодування (Хаффман): завжди об'єднувати два найлегші вузли.
Найкоротші шляхи без від'ємних ребер (Дейкстра): обирати невідвідану вершину з мінімальною поточною відстанню.

Де жадібність ламається

Розмін монет для довільних номіналів: за монет [1, 3, 4] і суми 6 жадібний вибір дає 4+1+1 (3 монети), оптимум - 3+3 (2 монети).
Рюкзак 0/1: обирати за максимальною «цінністю/вагою» не завжди оптимально.
Планування з вагами (weighted interval scheduling): потрібне динамічне програмування, жадібності недостатньо.

Шаблон міркування на співбесіді

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

Ілюстрація: відбір інтервалів, що не перетинаються (жадібність працює)

Критерій: завжди брати активність, яка завершується раніше за всі, сумісні з уже вибраними.

function selectActivities(intervals) {
  // intervals: [{ start, end }]
  intervals.sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;
  for (const it of intervals) {
    if (it.start >= lastEnd) {
      result.push(it);
      lastEnd = it.end;
    }
  }
  return result;
}

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

Контрприклад: розмін монет (жадібність ламається)

Для монет [1, 3, 4] і суми 6 жадібність (брати найбільшу монету ≤ залишку) дає неоптимальну відповідь.

function coinChangeGreedy(amount, coins) {
  coins = [...coins].sort((a, b) => b - a);
  const used = [];
  for (const c of coins) {
    while (amount >= c) {
      amount -= c;
      used.push(c);
    }
  }
  return amount === 0 ? used : null; // null, якщо розмін неможливий
}

function coinChangeDP(amount, coins) {
  const dp = Array(amount + 1).fill(Infinity);
  const prev = Array(amount + 1).fill(-1);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a >= c && dp[a - c] + 1 < dp[a]) {
        dp[a] = dp[a - c] + 1;
        prev[a] = c;
      }
    }
  }
  if (!isFinite(dp[amount])) return null;
  const res = [];
  for (let a = amount; a > 0; a -= prev[a]) res.push(prev[a]);
  return res;
}

const coins = [1, 3, 4];
const amount = 6;
console.log('Greedy:', coinChangeGreedy(amount, coins)); // [4, 1, 1]
console.log('DP    :', coinChangeDP(amount, coins));     // [3, 3] (оптимум)

Підсумок

Локально оптимальний вибір - це «найкращий крок зараз» за заданим критерієм. Жадібні алгоритми швидкі й прості, але дають коректний глобально оптимальний результат лише для задач із відповідною структурою (greedy-choice property та оптимальна підструктура). Для інших задач потрібна динаміка, перебір або інший підхід.

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

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

Premium

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