Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Які задачі класично розв'язуються жадібним алгоритмом?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

- Інтервальне планування (максимум інтервалів, що не перетинаються, «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));
```

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

Дейкстра жадібно «фіксує» вершини в порядку зростання відомої довжини шляху, покладаючись на відсутність від'ємних ребер. Для від'ємних ребер жадібність ламається - потрібен Беллман-Форд.

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

Задачі тривалістю в 1 слот із дедлайнами: сортуємо за спаданням прибутку й розміщуємо кожну в найпізніший доступний слот до її дедлайну (через DSU/масив/купу). Дає максимум прибутку.

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

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

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

Ідемо станціями зліва направо; поки не дотягуємо до наступної - беремо з max-купи найкращу з уже пройдених станцій (найбільший обсяг палива). Це мінімізує кількість зупинок.

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

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

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

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

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

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

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати1064 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.