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

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

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

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

Контент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### Де це працює

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

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

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

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

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

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

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

```js
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 жадібність (брати найбільшу монету ≤ залишку) дає неоптимальну відповідь.

```js
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, якщо розмін неможливий
}

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 та оптимальна підструктура). Для інших задач потрібна динаміка, перебір або інший підхід.

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

Для рев’юера

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

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