Що означає глобально оптимальне рішення в жадібному алгоритмі?

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

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

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

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

Визначення

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

Коли жадібний алгоритм гарантує глобальний оптимум

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

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

Типові задачі, де жадібний дає глобальний оптимум

Вибір максимальної кількості інтервалів (активностей), що не перетинаються - сортування за часом закінчення.
Мінімальне остовне дерево (Kruskal/Prim) - «властивість розрізу» гарантує глобальну мінімальність.
Оптимальне префіксне кодування (Хаффман) - найменші частоти об'єднуються першими.
Розмін монет у «канонічних» системах номіналів (наприклад, 1, 5, 10, 25).

Приклад (жадібний глобально оптимальний): вибір інтервалів, що не перетинаються

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

function selectActivities(intervals) {
  // intervals: [{ start: number, end: number }]
  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 intervals = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 7 },
  { start: 1, end: 2 }
];
console.log(selectActivities(intervals));
// Жадібний дає глобальний максимум за кількістю вибраних інтервалів

Контрприклад (жадібний не дає глобальний оптимум): розмін монет

Номінали 1, 3, 4; сума 6. Жадібний за великими монетами обере 4 + 1 + 1 (3 монети), але глобально оптимально 3 + 3 (2 монети).

function greedyCoins(coins, amount) {
  coins = [...coins].sort((a, b) => b - a);
  const taken = [];
  for (const c of coins) {
    while (amount >= c) {
      amount -= c;
      taken.push(c);
    }
  }
  return { coins: taken, count: taken.length, remainder: amount };
}

console.log(greedyCoins([1, 3, 4], 6));
// { coins: [4, 1, 1], count: 3, remainder: 0 }  <-- не глобальний оптимум

Як усе ж отримати глобальний оптимум, коли жадібний ламається (DP)

Динамічне програмування гарантує глобальний оптимум, перебираючи підзадачі і запам'ятовуючи найкращі результати.

function minCoinsDP(coins, amount) {
  const INF = amount + 1;
  const dp = new Array(amount + 1).fill(INF);
  const prev = new Array(amount + 1).fill(-1);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a >= c && dp[a - c] + 1 < dp[a]) {
        dp[a] = dp[a - c] + 1;
        prev[a] = c;
      }
    }
  }
  if (dp[amount] === INF) return { count: -1, coins: [] };
  const out = [];
  let a = amount;
  while (a > 0) {
    out.push(prev[a]);
    a -= prev[a];
  }
  return { count: out.length, coins: out };
}

console.log(minCoinsDP([1, 3, 4], 6));
// { count: 2, coins: [3, 3] }  <-- глобально оптимально

Практичні поради для співбесіди

Спершу сформулюйте критерій оптимальності і допустиму множину рішень.
Перевірте оптимальну підструктуру і спробуйте сформулювати жадібний критерій вибору.
Спробуйте «обмінний аргумент»: чи можна будь-яку оптимальну структуру перетворити так, щоб перший крок збігався з вашим жадібним?
Якщо швидко знаходите контрприклад - жадібний, ймовірно, не гарантує глобальний оптимум; розгляньте DP/пошук.

Підсумок

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

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

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

Premium

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