Які задачі класично розв'язуються жадібним алгоритмом?

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

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

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

Інтервальне планування (максимум інтервалів, що не перетинаються, «activity selection»)
Покриття інтервалів точками (мінімум точок/стріл для «проколювання» інтервалів/куль)
Дробовий рюкзак (fractional knapsack)
Монетна здача для канонічних наборів номіналів (напр., {1, 2, 5, 10, 25, 50})
Коди Хаффмана (оптимальні префіксні коди/оптимальне злиття файлів)
Мінімальне остовне дерево (Краскал, Прим)
Найкоротші шляхи з невід'ємними вагами (Дейкстра)
Планування задач із дедлайнами й прибутком (одинична тривалість)
Інтервальне розбиття (мінімум ресурсів/аудиторій)
Маршрут із мінімумом дозаправок (жадібно брати доступну «найбільшу» заправку по дорозі)
Апроксимації: покриття множини, вершинне покриття та ін. (жадібні дають гарантії наближення)

Детальний розбір, ідеї та коректність

1) Інтервальне планування (максимум інтервалів, що не перетинаються)

Задача: обрати максимум інтервалів (зустрічей/завдань), що не перетинаються. Жадібна стратегія: відсортувати за часом закінчення й ітеруватися, обираючи кожен інтервал, чий початок ≥ кінця останнього вибраного.

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

// JS: максимум інтервалів, що не перетинаються (activity selection)
function selectMaxNonOverlapping(intervals) {
  const arr = intervals.slice().sort((a, b) => a.end - b.end);
  const chosen = [];
  let lastEnd = -Infinity;
  for (const it of arr) {
    if (it.start >= lastEnd) {
      chosen.push(it);
      lastEnd = it.end;
    }
  }
  return chosen;
}

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

2) Покриття інтервалів точками (мінімум «стріл»)

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

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

3) Дробовий рюкзак (fractional knapsack)

Задача: за обмеженої місткості можна брати частки предметів. Жадібно: сортуємо за питомою цінністю (value/weight) і набираємо, поки є місце, останній предмет - частково.

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

// JS: дробовий рюкзак
function fractionalKnapsack(capacity, items) {
  const arr = items
    .map(it => ({ ...it, ratio: it.value / it.weight }))
    .sort((a, b) => b.ratio - a.ratio);
  let total = 0;
  const taken = [];
  for (const it of arr) {
    if (capacity <= 0) break;
    const take = Math.min(it.weight, capacity);
    total += it.value * (take / it.weight);
    taken.push({ id: it.id, take });
    capacity -= take;
  }
  return { value: total, taken };
}

// Приклад
const items = [
  { id: 'A', weight: 10, value: 60 },
  { id: 'B', weight: 20, value: 100 },
  { id: 'C', weight: 30, value: 120 }
];
console.log(fractionalKnapsack(50, items));

4) Монетна здача (канонічні номінали)

Жадібно брати максимально можливий номінал, поки можна. Це оптимально для «канонічних» наборів (наприклад, стандартних валют), але не для довільних. Контрприклад: номінали {1, 3, 4}, сума 6: жадібно -> 4+1+1 (3 монети), оптимально -> 3+3 (2 монети).

5) Коди Хаффмана (оптимальні префіксні коди)

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

6) Мінімальне остовне дерево (Краскал, Прим)

Обидві стратегії жадібні: Краскал додає ребра в порядку ваги, уникаючи циклів; Прим розширює дерево, щоразу додаючи найлегше ребро, що виходить із поточного дерева. Обидва використовують властивості розрізу/найлегших ребер; коректність спирається на «cut property».

// JS: Краскал із DSU
class DSU {
  constructor(n) { this.p = Array.from({ length: n }, (_, i) => i); this.r = Array(n).fill(0); }
  find(x) { return this.p[x] === x ? x : (this.p[x] = this.find(this.p[x])); }
  union(a, b) {
    a = this.find(a); b = this.find(b);
    if (a === b) return false;
    if (this.r[a] < this.r[b]) [a, b] = [b, a];
    this.p[b] = a; if (this.r[a] === this.r[b]) this.r[a]++;
    return true;
  }
}
function kruskal(n, edges) { // edges: [u,v,w]
  const es = edges.slice().sort((a, b) => a[2] - b[2]);
  const dsu = new DSU(n);
  const mst = [];
  let cost = 0;
  for (const [u, v, w] of es) {
    if (dsu.union(u, v)) { mst.push([u, v, w]); cost += w; if (mst.length === n - 1) break; }
  }
  return { cost, edges: mst };
}

// Приклад
const n = 4;
const edges = [ [0,1,1], [1,2,2], [0,2,2], [2,3,1], [1,3,3] ];
console.log(kruskal(n, edges));

Покриття множини (Set Cover): жадібно обирати множину, що покриває максимум ще непокритих елементів -> O(log n)-наближення.
Вершинне покриття: жадібно брати вершини, інцидентні ребрам -> 2-наближення.

Коли жадібність не підходить (важливі винятки)

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

Практичні ознаки, що жадібність може спрацювати

Можна сформулювати локальний вибір, який «не погіршує» оптимальність (обмінний аргумент, cut-property, найгірший/найкращий локальний елемент).
Задача вкладається в матроїд (наприклад, остов, activity selection) - клас задач, де жадібність оптимальна.
Є природне сортування: за часом закінчення, за питомою вигодою, за частотою, за вагою ребра тощо.

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

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

Premium

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

Які задачі класично розв'язуються жадібним алгоритмом?

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

Детальний розбір, ідеї та коректність

1) Інтервальне планування (максимум інтервалів, що не перетинаються)

2) Покриття інтервалів точками (мінімум «стріл»)

3) Дробовий рюкзак (fractional knapsack)

4) Монетна здача (канонічні номінали)

5) Коди Хаффмана (оптимальні префіксні коди)

6) Мінімальне остовне дерево (Краскал, Прим)

7) Найкоротші шляхи (Дейкстра, ваги невід'ємні)

8) Планування задач із дедлайнами й прибутком (unit-time jobs)

9) Інтервальне розбиття (мінімум аудиторій/ресурсів)

10) Маршрут із мінімумом дозаправок

Де жадібність дає апроксимації

Коли жадібність не підходить (важливі винятки)

Практичні ознаки, що жадібність може спрацювати

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