Що таке «оптимальна підструктура» в жадібному алгоритмі?

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

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

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

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

Визначення

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

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

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

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

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

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

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

Відбір інтервалів (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-рюкзак): підструктура є, жадібний вибір не працює.
Коротко опишіть доведення через заміну підоптимального фрагмента на оптимальний (аргумент від протилежного).
Сформулюйте наслідки: якщо жадібний вибір безпечний - використовуємо жадібний алгоритм, інакше - ДП.

Підсумок

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

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

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

Premium

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