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

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

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

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

Контент

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

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

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

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

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

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

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

## Детальне пояснення

### Визначення

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

### Зв'язок із жадібними алгоритмами

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

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

- І динамічне програмування (ДП), і жадібні алгоритми потребують оптимальної підструктури.
- Жадібним додатково потрібна властивість жадібного вибору; якщо її немає, застосовується ДП або повний перебір.
- У ДП ми перебираємо множину підрішень із запам'ятовуванням; у жадібному - робимо один «незворотний» вибір і розв'язуємо меншу підзадачу.

### Як розпізнати оптимальну підструктуру

1. Опишіть підзадачу, що залишається після прийняття одного вибору (наприклад, після вибору інтервалу, вершини, ребра тощо).
2. Припустіть існування оптимального рішення O вихідної задачі.
3. Покажіть, що частина O, яка відповідає підзадачі, зобов'язана бути оптимальною для цієї підзадачі; інакше можна замінити її на краще рішення і покращити O (суперечність).
4. Перевірте властивість жадібного вибору: доведіть, що існує оптимальне рішення, яке починається з жадібного кроку; після цього за оптимальною підструктурою рекурсивно продовжуємо.

### Класичні приклади

- Відбір інтервалів (activity selection) за раннім завершенням: після вибору інтервалу, що закінчується раніше за всі, залишається та сама задача на решті сумісних інтервалів; її оптимальне рішення доповнює загальний оптимум.
- Алгоритм Дейкстри: після фіксації вершини з мінімальною поточною відстанню підзадача - знайти найкоротші шляхи в графі із вже зафіксованою множиною; оптимальні шляхи продовжуються оптимально.
- Коди Хаффмана: злиття двох найменших частот створює підзадачу меншого розміру; оптимальна структура дерева зберігається.
- Дробовий рюкзак: після вибору речі з максимальною цінністю на одиницю ваги залишається той самий тип задачі на решті об'єму; оптимальні частки складаються в загальний оптимум.

### Контрприклад: 0/1-рюкзак

0/1-рюкзак має оптимальну підструктуру (ДП працює), але жадібний вибір за ціною/вагою може призвести до неоптимуму. Отже, самої оптимальної підструктури для жадібного алгоритму недостатньо - потрібна ще перевірка «безпечності» жадібного кроку.

### Міні-приклад: відбір інтервалів

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

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

```
// Відбір максимального числа інтервалів, що не перетинаються (жадібний алгоритм)
// intervals: [{ start: number, end: number }]
function selectMaxNonOverlappingIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;

for (const it of sorted) {
    if (it.start >= lastEnd) {
      result.push(it);
      lastEnd = it.end;
    }
  }
  return result;
}

// Приклад
const intervals = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 7 },
  { start: 1, end: 2 }
];

console.log(selectMaxNonOverlappingIntervals(intervals));
// Результат: оптимальний за розміром набір інтервалів (наприклад, [{ start: 1, end: 2 }, { start: 2, end: 5 }])
```

### Чек-лист для співбесіди

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

### Підсумок

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

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

Для рев’юера

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

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