Жадные алгоритмы

Жадный алгоритм (greedy algorithm) — стратегия решения задач, при которой на каждом шаге выбирается локально оптимальное решение в надежде получить глобально оптимальный результат.

Зачем нужно

Жадные алгоритмы, когда применимы, дают самые быстрые решения: O(n log n) или лучше, без хранения таблиц DP. Они лежат в основе сжатия данных (Хаффман), сетевых протоколов (алгоритм Крускала для MST), задач планирования. Умение распознать «жадную» задачу — ключевой навык на собеседовании.

Где используется

  • Алгоритмы Крускала и Прима (минимальное остовное дерево)
  • Алгоритм Дейкстры (кратчайший путь)
  • Кодирование Хаффмана (оптимальное сжатие)
  • Задача о расписании (Activity Selection Problem)
  • Задача о сдаче: минимальное число монет (при определённых наборах монет)

Основной контент

Условия применимости

Жадный алгоритм даёт оптимальный результат, если задача обладает:

  1. Greedy choice property: локально оптимальный выбор ведёт к глобально оптимальному решению.
  2. Optimal substructure: оптимальное решение содержит оптимальные решения подзадач.

Если условия не выполнены — нужно Динамическое программирование.

Пример 1: Activity Selection (выбор задач)

// Выбрать максимальное число непересекающихся задач
// Жадный выбор: всегда берём задачу с наименьшим временем окончания

function activitySelection(activities) {
  // activities: [{start, end}]
  const sorted = [...activities].sort((a, b) => a.end() - b.end());
  const selected = [sorted[0]];
  let lastEnd = sorted[0].end();

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i].start() >= lastEnd) {
      selected.push(sorted[i]);
      lastEnd = sorted[i].end();
    }
  }
  return selected;
}

const tasks = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
];
// Результат: [{1,4}, {5,7}, {8,9}] — 3 задачи

Пример 2: Сдача монет (жадный — не всегда оптимален!)

// Для монет [1, 5, 10, 25] — жадный даёт оптимум
// Для монет [1, 3, 4], сумма 6 — жадный даёт [4,1,1]=3 монеты
// но оптимум [3,3]=2 монеты → нужно DP!

function coinChangeGreedy(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a); // от большей к меньшей
  const result = ;
  for (const coin of sorted) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  return amount === 0 ? result : null; // null если нельзя разменять точно
}

Пример 3: Кодирование Хаффмана (идея)

Символы: A(45%), B(13%), C(12%), D(16%), E(9%), F(5%)
→ Строим min-heap по частоте
→ Берём два наименьших, создаём узел-сумму
→ Повторяем до одного корня
→ Левый дочерний = 0, правый = 1
→ A получает самый короткий код (наиболее частый)

Жадный vs DP

Аспект Жадный DP
Скорость Быстрее Медленнее
Применимость Не всегда Шире
Сложность реализации Проще Сложнее
Доказательство корректности Требуется Требуется

Частые ошибки

  • Применять жадный алгоритм без доказательства greedy choice property — может давать неоптимальный результат (пример: монеты с нестандартными номиналами).
  • Считать, что жадный всегда работает для задач о монетах — работает только для «канонических» наборов монет.
  • Путать с DP: если в задаче нужно учитывать все предыдущие решения — жадного недостаточно.

Связанные темы

Ресурсы