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

Введение

В отличие от динамического программирования, рассматривающего все возможные варианты решения подзадач, жадный алгоритм на каждом шаге делает локально оптимальный выбор, никогда не пересматривая его позже — в этой статье разберём, когда такой простой, «недальновидный» подход всё же даёт глобально оптимальное решение, и когда это предположение ошибочно.

Концепция

Жадный алгоритм применим корректно только для задач со специальным свойством — локально оптимальный выбор на каждом шаге действительно ведёт к глобально оптимальному решению всей задачи в целом (это свойство, в отличие от ДП, не выполняется для большинства произвольных задач, и его наличие нужно явно доказать или, как минимум, тщательно проверить для конкретной задачи, прежде чем доверять жадному подходу). Классический пример, где жадный подход корректен — задача выдачи минимального количества монет для заданной суммы при определённых, «удачных» номиналах монет (как стандартный набор номиналов многих валют), но для произвольного, не «удачного» набора номиналов та же жадная стратегия может дать неоптимальный результат, требуя вместо неё динамического программирования.

Пример кода

// Жадный алгоритм для выдачи монет — корректен для "удачного" набора номиналов
QVector<int> greedyCoinChange(int amount, const QVector<int> &denominations)
{
    QVector<int> sortedDenoms = denominations;
    std::sort(sortedDenoms.begin(), sortedDenoms.end(), std::greater<int>()); // от большего к меньшему

    QVector<int> usedCoins;
    for (int coin : sortedDenoms) {
        while (amount >= coin) { // берём максимально возможное количество текущего номинала
            amount -= coin;
            usedCoins.append(coin);
        }
    }
    return usedCoins; // для номиналов {25, 10, 5, 1} жадный подход всегда даёт оптимальный результат
}

// Демонстрация СБОЯ жадного подхода для неудачного набора номиналов
// Номиналы {1, 3, 4}, требуемая сумма 6:
// Жадный подход: 4 + 1 + 1 = 3 монеты
// Оптимальное решение: 3 + 3 = 2 монеты — жадный подход НЕ нашёл его!
QVector<int> badDenominations = {4, 3, 1};
QVector<int> result = greedyCoinChange(6, badDenominations);
qDebug() << "Жадный результат:" << result.size() << "монет"; // 3 монеты — НЕ оптимально!
// Для этого случая правильным решением была бы динамическая программирование (статья 463),
// рассматривающая ВСЕ комбинации, а не только локально "очевидный" жадный выбор

// Корректное применение жадного подхода — задача планирования непересекающихся интервалов
struct Interval { int start, end; };

int maxNonOverlappingIntervals(std::vector<Interval> intervals)
{
    std::sort(intervals.begin(), intervals.end(),
              [](const Interval &a, const Interval &b) { return a.end < b.end; });
    // Жадная стратегия: всегда выбирать интервал с НАИМЕНЬШИМ временем окончания —
    // это доказуемо оптимальная стратегия именно для этой конкретной задачи

    int count = 0;
    int lastEnd = std::numeric_limits<int>::min();
    for (const auto &interval : intervals) {
        if (interval.start >= lastEnd) {
            count++;
            lastEnd = interval.end;
        }
    }
    return count;
}

Пояснения к коду

greedyCoinChange для номиналов {25, 10, 5, 1} показывает случай, где жадный подход (всегда брать максимально возможное количество самого крупного оставшегося номинала) действительно даёт оптимальный результат — это специфическое свойство именно этого, «удачного» набора номиналов, а не общее свойство задачи выдачи монет как таковой. Демонстрация сбоя для номиналов {4, 3, 1} явно показывает контрпример — жадный выбор крупнейшего номинала (4) для суммы 6 оставляет остаток 2, требующий двух монет номиналом 1, тогда как недоступный жадному алгоритму вариант (две монеты по 3) даёт лучший, оптимальный результат, который жадная стратегия принципиально не способна обнаружить из-за своей «недальновидности». maxNonOverlappingIntervals показывает корректное применение жадной стратегии для другой задачи (максимизация числа непересекающихся интервалов) — выбор интервала с наименьшим временем окончания на каждом шаге доказуемо оптимален именно для этой конкретной формулировки задачи, что принципиально отличается от задачи выдачи монет, где аналогичная «жадность» не гарантирует оптимальности в общем случае.

Подводные камни

Применение жадного алгоритма к задаче без предварительной проверки или доказательства, что локально оптимальные решения действительно ведут к глобально оптимальному результату для этой конкретной задачи — пример с номиналами {4, 3, 1} явно демонстрирует, что интуитивно «очевидный» жадный подход может дать неоптимальный результат без какого-либо явного сигнала об ошибке (код выполняется и даёт результат, просто не оптимальный), что особенно опасно, если корректность жадного подхода была лишь предположена, а не строго проверена или доказана для конкретной формулировки задачи.
Путаница между задачами, где жадный подход корректен, и похожими, но принципиально иными задачами, где он не работает — задача выдачи монет для конкретных, «удачных» номиналов (где жадность работает) и задача выдачи монет для произвольных номиналов (где не работает) выглядят почти идентично по формулировке, но требуют принципиально разных алгоритмических подходов, и автоматический перенос жадной стратегии из одной успешной задачи на похожую, но иную задачу без отдельной проверки — частая, легко допускаемая ошибка.
Недостаточно тщательное тестирование жадного алгоритма только на «удобных» тестовых случаях, не выявляющих потенциальную неоптимальность для менее очевидных, особенно граничных комбинаций входных данных — для задачи выдачи монет с произвольными номиналами стоит явно протестировать жадный алгоритм против полного, исчерпывающего (или ДП-решения) перебора на разнообразных тестовых наборах номиналов, прежде чем доверять жадному подходу в production-коде, особенно если набор возможных номиналов/параметров заранее не полностью предсказуем.
Отказ от рассмотрения жадного подхода вовсе из-за общего, неточного убеждения, что «жадные алгоритмы никогда не дают оптимального решения» — это столь же неверная крайность, как и излишнее доверие жадности без проверки: для многих реальных задач (как демонстрация с непересекающимися интервалами) жадная стратегия действительно доказуемо оптимальна и при этом значительно проще и быстрее реализуется и работает по сравнению с полноценным динамическим программированием, и отказ от рассмотрения этого более простого варианта там, где он реально корректен, означает неоправданное усложнение решения без необходимости.