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

Жадный алгоритм — это самый соблазнительный и самый опасный класс алгоритмов. Соблазнительный, потому что он пишется за пять минут, работает за O(n log n) и часто «выглядит правильным». Опасный — потому что «выглядит правильным» и «правильный» здесь расходятся чаще, чем где бы то ни было. Разница между жадностью, которая всегда даёт оптимум, и жадностью, которая тихо теряет 30% прибыли на редких входах, — это не разница в коде. Это разница в структуре задачи, которую нужно уметь увидеть и доказать.

Эта статья про то, как отличать одно от другого. Не «вот список задач, где жадность работает», а «вот три стандартных способа доказать, что жадность работает, и вот как их применять к своей задаче за 15 минут».

Что вообще такое жадный алгоритм

Формально: у нас есть задача оптимизации, решение которой строится как последовательность выборов. Жадный алгоритм на каждом шаге делает выбор, лучший по некоторому локальному критерию, и никогда его не пересматривает. Нет отката, нет перебора альтернатив, нет таблицы состояний.

Общая схема почти всегда одна:

GREEDY(elements):
    отсортировать elements по ключу приоритета   # или поместить в очередь с приоритетом
    solution = ∅
    для каждого e из elements в этом порядке:
        если solution ∪ {e} допустимо:           # проверка feasibility
            solution = solution ∪ {e}
    вернуть solution

Ключевых компонентов ровно три, и ошибка почти всегда сидит в одном из них:

1. Критерий сортировки — что значит «локально лучший». Это творческая часть; для одной и той же задачи бывает 5 правдоподобных критериев, из которых работает один.
2. Проверка допустимости — можно ли добавить кандидата к уже построенному решению. Иногда это O(1) (сравнить с последним взятым), иногда требует структуры данных (DSU, дерево отрезков).
3. Необратимость — то, что даёт скорость, и то, что делает алгоритм неверным, когда структура задачи этого не позволяет.

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

Два свойства, которые нужны

Классическая формулировка (CLRS, глава про жадные алгоритмы):

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

Оптимальная подструктура — общее свойство с динамическим программированием (см. https://courses.digitable.life/post/algorithms/07-dynamic-programming/). Разница ровно в первом пункте: ДП перебирает все варианты первого шага, потому что не знает, какой правильный; жадность знает. Жадный алгоритм — это ДП, у которого доказано, что переход всегда один.

Три способа доказать корректность

Это главный раздел статьи. Если вы запомните только его — уже хорошо.

1. Аргумент обмена (exchange argument)

Самый универсальный приём. Схема:

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

Разберём на задаче о выборе заявок (activity selection): дано n отрезков [s_i, f_i), нужно выбрать максимум попарно непересекающихся.

Жадный критерий: брать отрезок с минимальным правым концом. Доказательство обменом:

Пусть OPT = {j₁, j₂, …, j_k} отсортирован по времени, g₁ — отрезок с минимальным f во всём множестве. Тогда f(g₁) ≤ f(j₁). Заменим j₁ на g₁: множество OPT′ = {g₁, j₂, …, j_k} по-прежнему состоит из непересекающихся отрезков (потому что j₂ начинался не раньше f(j₁) ≥ f(g₁)), и |OPT′| = |OPT|. Значит OPT′ тоже оптимально и содержит жадный выбор. Дальше — индукция по подзадаче «отрезки, начинающиеся не раньше f(g₁)». ∎

Почему не работают другие правдоподобные критерии, полезно держать в голове как прививку:

def max_non_overlapping(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Максимум попарно непересекающихся полуинтервалов [s, f).

    Время:  O(n log n) — доминирует сортировка.
    Память: O(n) на отсортированную копию (O(1) дополнительно, если сортировать на месте).
    """
    chosen: list[tuple[int, int]] = []
    last_end = float("-inf")
    # Ключ — правый конец: это и есть доказанный жадный критерий.
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:          # допустимость: не пересекается с последним взятым
            chosen.append((start, end))
            last_end = end
    return chosen

2. Greedy stays ahead («жадный всегда впереди»)

Второй приём: вместо обмена доказываем инвариант доминирования. Утверждение вида «после i шагов частичное решение жадного алгоритма не хуже частичного решения любого другого решения по некоторой мере». Индукция по i.

Для той же задачи о заявках: пусть g₁ … g_i — первые i выбранных жадным, j₁ … j_i — первые i из произвольного допустимого решения. Инвариант: f(g_i) ≤ f(j_i) для всех i. База очевидна; шаг — раз f(g_{i-1}) ≤ f(j_{i-1}), то j_i был доступен жадному алгоритму на шаге i, а тот выбрал минимальный правый конец, значит f(g_i) ≤ f(j_i). Отсюда: если бы существовало решение из k+1 заявок, а жадный взял k, то (k+1)-я заявка начиналась бы не раньше f(j_k) ≥ f(g_k) — и жадный обязан был бы её взять. Противоречие. ∎

Эта техника особенно естественна для задач, где решение — последовательность, и есть числовая характеристика «насколько мы продвинулись»: покрытие точками, задача о заправках, задача о прыжках (jump game), кэширование. Подробный разбор приёма — у Клейнберга и Тардоша, глава 4 (материалы курса).

3. Матроиды: когда корректность следует из структуры

Самый сильный результат. Пусть E — конечное множество, I ⊆ 2^E — семейство «независимых» подмножеств. Пара M = (E, I) называется матроидом, если:

1. ∅ ∈ I;
2. наследственность: A ∈ I и B ⊆ A ⟹ B ∈ I;
3. свойство обмена: если A, B ∈ I и |A| < |B|, то существует x ∈ B \ A такой, что A ∪ {x} ∈ I.

Теорема (Радо–Эдмондс). Жадный алгоритм (сортировать элементы по убыванию веса, брать, если независимость сохраняется) находит независимое множество максимального веса для любой весовой функции тогда и только тогда, когда (E, I) — матроид.

Это «если и только если» — самое ценное. Если жадность работает для всех весов — под ней обязательно лежит матроид; если структура не матроид, найдётся весовая функция, на которой жадность провалится. Классический источник: Jack Edmonds, Matroids and the greedy algorithm, Mathematical Programming, 1971 (DOI).

Примеры матроидов, которые вы уже встречали:

• Графовый матроид: E — рёбра, независимы ациклические подмножества. Жадность = алгоритм Крускала для минимального остовного дерева (см. https://courses.digitable.life/post/algorithms/10-mst-and-flows/).
• Матроид разбиения: E разбито на группы, независимо множество, берущее из каждой группы не больше k_i элементов. Отсюда — задачи вида «выбрать не более 3 задач из каждой команды».
• Трансверсальный матроид: независимы множества вершин, покрываемые паросочетанием в двудольном графе.
• Матроид планирования с дедлайнами: множество работ независимо, если существует расписание, укладывающее их все в срок. Это даёт корректность классической задачи ниже.

Для более широкого класса — гридоидов (Кorte, Lovász) — жадность работает при дополнительных условиях на целевую функцию; на практике проще проверять частные случаи, чем общую теорию.

Каталог классических задач

Дробный рюкзак — и почему целочисленный не поддаётся

Дробный рюкзак: можно брать части предметов. Жадный критерий — удельная ценность v/w. Доказательство обменом: если в оптимуме взята доля предмета с меньшей удельной ценностью при недобранном более ценном, обмен единицы веса не уменьшает суммарную ценность.

def fractional_knapsack(items: list[tuple[float, float]], capacity: float) -> float:
    """items — список (вес, ценность). Разрешено брать дробные части.

    Время: O(n log n). Память: O(n).
    Через nth_element/quickselect по медиане удельных ценностей достижимо O(n).
    """
    total = 0.0
    for w, v in sorted(items, key=lambda it: it[1] / it[0], reverse=True):
        if capacity <= 0:
            break
        take = min(w, capacity)        # берём целиком или сколько влезет
        total += v * take / w
        capacity -= take
    return total

Целочисленный рюкзак (0/1) той же жадностью не решается. Минимальный контрпример: capacity = 10, предметы (w=6, v=7), (w=5, v=5), (w=5, v=5). Удельные ценности 7/6 ≈ 1.17 и 1.0, поэтому жадность берёт первый предмет, после чего свободно 4 — ни один пятикилограммовый уже не влезает, итог 7. Оптимум — 5 + 5 = 10. Причина в том, что дробимость и была тем, что делало обмен безопасным: без неё «долить» остаток лучшим по удельной ценности предметом нельзя. 0/1-рюкзак NP-труден, точное решение — ДП, см. https://courses.digitable.life/post/algorithms/07-dynamic-programming/.

Обратите внимание, насколько мал этот контрпример: три предмета. Именно поэтому первое, что нужно делать с жадной гипотезой, — не размышлять, а гонять её против брутфорса на входах размера 3–8.

Размен монет: жадность зависит от данных, а не от алгоритма

Задача: набрать сумму S минимальным числом монет заданных номиналов.

Для «канонических» систем (евро, рубли, доллар США: 1, 5, 10, 25) жадность оптимальна. Для {1, 10, 25} — нет: 30 = 25+1×5 (6 монет) против 10+10+10 (3 монеты). Существенно, что проверка каноничности сама по себе нетривиальная задача: Дэвид Пирсон построил полиномиальный O(n³) тест (A polynomial-time algorithm for the change-making problem, Operations Research Letters, 2005), основанный на поиске минимального контрпримера. Практический вывод для продакшена: если номиналы приходят из конфига и могут меняться — не используйте жадность, берите ДП, иначе кассовый аппарат однажды начнёт выдавать сдачу горстью мелочи.

Хаффман: жадность, строящая дерево снизу вверх

Задача: построить префиксный код минимальной средней длины для символов с частотами f_i, то есть минимизировать Σ f_i · depth(i).

Жадный шаг: слить два самых редких символа в один узел. Доказательство обменом опирается на лемму: в некотором оптимальном дереве два наименее частых символа — братья на максимальной глубине. Если это не так, обмен их с текущими самыми глубокими листьями не увеличивает стоимость (меньшая частота уходит на большую глубину). Дальше — индукция по числу символов. Оригинал: D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, 1952 (IEEE).

import heapq
from collections import Counter
from itertools import count


def huffman_codes(text: str) -> dict[str, str]:
    """Префиксный код Хаффмана.

    Время:  O(σ log σ), где σ — размер алфавита (n на подсчёт частот).
    Память: O(σ).
    """
    freq = Counter(text)
    if len(freq) == 1:                       # вырожденный случай: один символ
        return {next(iter(freq)): "0"}

    tie = count()                            # tiebreaker: чтобы heapq не сравнивал узлы
    heap = [(f, next(tie), sym) for sym, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)    # два самых редких — жадный выбор
        f2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tie), (left, right)))

    codes: dict[str, str] = {}

    def walk(node, prefix: str) -> None:
        if isinstance(node, tuple):          # внутренний узел
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")
        else:
            codes[node] = prefix

    walk(heap[0][2], "")
    return codes

Дерево слияний удобно смотреть глазами:

Порядок слияний: d+e → 5, затем 5+c → 11, затем 11+b → 25, затем a+25 → 45. Коды: a=0, b=11, c=101, d=1000, e=1001. Средняя длина (20·1 + 14·2 + 6·3 + 2·4 + 3·4)/45 ≈ 1.91 бита против 3 бит у фиксированного кода.

Как это живёт в проде. Хаффман — не учебная игрушка: это половина формата DEFLATE (RFC 1951), на котором стоят gzip, zip, PNG и HTTP-сжатие. В HTTP/2 заголовки жмутся HPACK (RFC 7541) со статической таблицей Хаффмана. Zstandard использует FSE/ANS для энтропийного кодирования, но Хаффман остаётся для литералов (RFC 8878). Практическая деталь: реальные кодеры используют канонический Хаффман — код восстанавливается из одних лишь длин кодов, что экономит место в заголовке и делает декодирование табличным.

Планирование работ с дедлайнами и прибылью

n работ, каждая занимает единичный слот, у работы i дедлайн d_i и прибыль p_i. Максимизировать суммарную прибыль выполненных вовремя работ. Множества выполнимых работ образуют матроид ⇒ жадность по убыванию прибыли корректна. Для проверки допустимости — DSU, ищущий ближайший свободный слот слева.

def schedule_with_deadlines(jobs: list[tuple[int, int]]) -> tuple[int, dict[int, int]]:
    """jobs — список (deadline, profit), дедлайны в единичных слотах 1..D.

    Время:  O(n log n + n·α(D)). Память: O(D).
    Корректность: множества выполнимых работ — матроид разбиения по префиксам слотов.
    """
    max_d = max(d for d, _ in jobs)
    parent = list(range(max_d + 1))          # parent[t] — ближайший свободный слот ≤ t

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # сжатие путей
            x = parent[x]
        return x

    total, plan = 0, {}
    for d, p in sorted(jobs, key=lambda j: j[1], reverse=True):
        slot = find(min(d, max_d))
        if slot > 0:                         # нашёлся свободный слот не позже дедлайна
            plan[slot] = p
            total += p
            parent[slot] = slot - 1          # слот занят, переадресуем влево
    return total, plan

Родственная задача — минимизация максимального опоздания (одна машина, работы с длительностями и дедлайнами): оптимален EDF, Earliest Deadline First — сортировка по дедлайну. Доказательство: у расписания без «простоев» и без «инверсий» (пары, где работа с большим дедлайном стоит раньше) максимальное опоздание одинаково; любое расписание сводится к EDF обменами соседних инверсий, не увеличивая опоздание. EDF — это реальный планировщик реального времени; он же лежит в основе SCHED_DEADLINE в Linux (документация ядра).

Покрытие отрезков точками

«Минимальное число точек, чтобы каждый отрезок содержал хотя бы одну» — двойственная к выбору заявок, и решается тем же жадным критерием (сортировка по правому концу).

def min_stabbing_points(intervals: list[tuple[int, int]]) -> list[int]:
    """Минимум точек, «протыкающих» все отрезки [l, r]. Время O(n log n), память O(n)."""
    points: list[int] = []
    last = float("-inf")
    for l, r in sorted(intervals, key=lambda iv: iv[1]):
        if l > last:                # текущий отрезок ещё не проткнут
            points.append(r)        # ставим точку максимально «поздно»
            last = r
    return points

Прикладное звучание: минимальное число проверок, покрывающих все окна обслуживания; минимальное число опорных кадров, покрывающих все интервалы движения; минимум сенсоров на трассе.

Дейкстра и Прим — тоже жадные

Алгоритм Дейкстры на каждом шаге безвозвратно «фиксирует» вершину с минимальной оценкой расстояния — это жадный выбор, корректность которого доказывается ровно аргументом обмена (и ломается при отрицательных рёбрах, потому что обмен перестаёт быть безопасным). Подробности — в https://courses.digitable.life/post/algorithms/09-shortest-paths/. Прим и Крускал — жадные алгоритмы на графовом матроиде, разбор в https://courses.digitable.life/post/algorithms/10-mst-and-flows/. То, что все три «просто работают», — не случайность, а следствие одной и той же структуры.

Когда жадность не точна, но всё равно полезна

Огромный практический пласт: задача NP-трудна, точное решение недоступно, но у жадности есть доказанная гарантия качества. Это не «авось сойдёт», а контракт.

Покрытие множеств: ln n и почему лучше нельзя

Задача: покрыть универсум U минимальным числом подмножеств. Жадность — каждый раз брать подмножество, покрывающее больше всего ещё не покрытых элементов. Гарантия: H_n ≈ ln n + 1 раз хуже оптимума.

def greedy_set_cover(universe: set, subsets: list[set]) -> list[set]:
    """Приближение с коэффициентом H_n ≈ ln n + 1.

    Время:  O(|subsets| · |U|) в наивной версии; с кучей «по остаточной выгоде»
            и ленивыми обновлениями — существенно быстрее на разреженных данных.
    Память: O(|U| + Σ|S|).
    """
    uncovered = set(universe)
    cover: list[set] = []
    while uncovered:
        # Жадный шаг: максимальная остаточная выгода.
        best = max(subsets, key=lambda s: len(uncovered & s))
        if not (uncovered & best):
            raise ValueError("универсум не покрывается данными подмножествами")
        cover.append(best)
        uncovered -= best
    return cover

Ури Фейге доказал, что улучшить (1 − o(1))·ln n нельзя, если только NP ⊄ DTIME(n^{log log n}) (A threshold of ln n for approximating set cover, JACM 1998, DOI). То есть простой жадный алгоритм — оптимальный из полиномиальных. Это редкий и приятный случай: писать что-то умнее бессмысленно.

Субмодулярная максимизация: гарантия 1 − 1/e

Обобщение: максимизировать монотонную субмодулярную функцию f при ограничении |S| ≤ k. Субмодулярность — формализация «убывающей отдачи»: f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B) при A ⊆ B. Жадность даёт (1 − 1/e) ≈ 0.632 от оптимума (Nemhauser, Wolsey, Fisher, 1978, DOI).

Где это встречается в проде: выбор признаков, размещение сенсоров/кэшей, суммаризация текстов, maximum coverage при выборе рекламных сегментов, выбор seed-узлов для распространения влияния в соцсетях. Практический трюк — lazy greedy (алгоритм CELF): приросты монотонно убывают, поэтому вместо пересчёта всех кандидатов держим кучу верхних оценок и пересчитываем только вершину; ускорение на порядки при том же ответе.

Планирование на m машинах: list scheduling

Раздать n задач на m идентичных машин, минимизировать makespan. Жадность «отдай следующую задачу самой свободной машине» даёт 2 − 1/m от оптимума (Graham, 1966/1969, SIAM J. Appl. Math.). Если сначала отсортировать задачи по убыванию длительности (LPT), гарантия улучшается до 4/3 − 1/(3m). Эти оценки — фундамент практических балансировщиков нагрузки и шедулеров пакетных задач.

Онлайн-жадность и competitive ratio

Отдельный жанр: решения принимаются без знания будущего. Мера качества — competitive ratio. Классика — ski rental: арендовать за 1 в день или купить за B. Стратегия «арендуй B−1 дней, потом купи» 2-конкурентна, и лучше детерминированно нельзя. Тот же скелет лежит в решениях «держать ли соединение открытым», «когда спинить блокировку до перехода в сон», «когда мигрировать данные в другой tier хранилища». LRU-вытеснение — тоже жадная онлайн-эвристика с известным k-конкурентным анализом.

Типичные ошибки

1. Правдоподобный, но неверный критерий. Самая частая. Лечение — не размышления, а стресс-тест:

import random


def dp_min_coins(coins: list[int], amount: int) -> float:
    """Эталон: точный ответ через ДП. O(amount · len(coins))."""
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount]


def greedy_min_coins(coins: list[int], amount: int) -> float:
    cnt = 0
    for c in sorted(coins, reverse=True):
        take, amount = amount // c, amount % c
        cnt += take
    return cnt if amount == 0 else float("inf")


def find_counterexample(trials: int = 20_000) -> tuple | None:
    """Ищем систему номиналов, где жадность врёт. Обычно находится за доли секунды."""
    rng = random.Random(42)
    for _ in range(trials):
        coins = sorted({1, rng.randint(2, 30), rng.randint(2, 30)})
        amount = rng.randint(1, 100)
        if greedy_min_coins(coins, amount) > dp_min_coins(coins, amount):
            return coins, amount
    return None

Правило: не коммить жадный алгоритм, пока он не выжил 10⁵ случайных тестов против эталона. Эталоном может быть brute force, ДП или ILP-решатель. Если брутфорс написать невозможно — это сигнал, что и доказательства у вас нет.

2. Ничьи. Два кандидата с равным ключом — какой брать? Иногда неважно, иногда критично (частая беда в задачах планирования). Задавайте полный порядок: добавляйте вторичный ключ. Заодно это делает результат детерминированным между запусками и языками — Python sorted стабилен, std::sort в C++ нет (см. https://courses.digitable.life/post/algorithms/02-sorting/).

3. Сравнение дробей через деление. v1/w1 > v2/w2 на float даёт ошибки округления и деление на ноль. В целочисленных задачах пишите v1 * w2 > v2 * w1 — и следите за переполнением в языках с фиксированной разрядностью.

4. Проверка допустимости стала узким местом. Жадность за O(n log n) легко превращается в O(n²), если feasibility проверяется линейно. Именно поэтому в задаче с дедлайнами стоит DSU, а не «пройтись по слотам».

5. Отсутствие оптимальной подструктуры. Симптом: после жадного выбора остаток — задача другого типа. Почти верный признак, что нужно ДП.

6. Жадность внутри цикла оптимизации. Даже когда жадность точна, она чувствительна к порядку с плавающей точкой. В финансовых расчётах храните суммы в целых копейках/сатоши.

7. Экстраполяция «работает на моих данных» на «работает всегда». Часто жадность даёт 0.1% отклонения на продовых распределениях и 40% на редком, но дорогом сценарии. Если алгоритм приближённый — измеряйте gap относительно нижней границы (LP-релаксация, тривиальный bound) и мониторьте его как метрику.

Как выбрать между жадностью, ДП и перебором

Практический порядок действий, когда задача новая:

1. Сформулируйте задачу как оптимизацию: что максимизируем, что ограничение.
2. Напишите брутфорс — он же эталон и он же спецификация.
3. Придумайте 2–4 жадных критерия, прогоните каждый стресс-тестом на входах размера 5–9.
4. Выживший критерий попробуйте доказать обменом. Если доказательство не складывается за 15 минут — ищите контрпример активнее (увеличьте размер входа, сделайте веса вырожденными: равными, нулевыми, очень большими).
5. Если жадность не проходит — стройте ДП, взяв «первый шаг» жадности как ось состояний.
6. Если ДП не влезает по памяти/времени — вернитесь к жадности, но уже как к аппроксимации: найдите нижнюю границу и померьте реальный gap.

Как жадность выглядит в продакшене

• Компиляторы. Линейное сканирование при аллокации регистров (linear scan register allocation, Poletto & Sarkar) — жадный алгоритм по интервалам живости; медленнее по качеству кода, чем раскраска графа, но на порядок быстрее компилируется. Именно поэтому он живёт в JIT-компиляторах.
• Планировщики. kube-scheduler выбирает узел жадно: фильтрация (predicates) + скоринг и выбор максимума (документация). Оптимального размещения он не гарантирует — за это отвечает отдельный descheduler, который «чинит» накопившиеся последствия локальных решений.
• Сжатие. DEFLATE, HPACK, zstd — Хаффман и его канонические варианты. Плюс жадный (и «ленивый жадный», lazy matching) выбор длины совпадения в LZ77: чистая жадность берёт самое длинное совпадение, а lazy-эвристика проверяет, не даст ли отказ от него выигрыш на следующем шаге.
• Базы данных. Жадные эвристики выбора порядка join’ов, жадный выбор индексов при index recommendation, жадное слияние SSTable-уровней в LSM-деревьях.
• Сети и биллинг. Bin packing при упаковке VM на хосты (First-Fit Decreasing — жадный, гарантия 11/9·OPT + 6/9), выбор ставок в аукционах, тарификация трафика.
• ML-пайплайны. Жадный отбор признаков, построение решающих деревьев (CART жадно выбирает сплит по максимуму прироста информации — и именно поэтому деревья не оптимальны глобально, что компенсируется ансамблями).

Общий паттерн продакшена: жадность используют не потому, что она точна, а потому что она предсказуема, быстра, инкрементальна и легко объяснима бизнесу. Инкрементальность особенно важна: жадный алгоритм естественно доопределяется на онлайн-поток, тогда как ДП требует пересчёта.

Мини-итог

• Жадный алгоритм = сортировка/куча + необратимый локальный выбор + проверка допустимости.
• Корректность требует двух свойств: свойство жадного выбора и оптимальная подструктура.
• Три инструмента доказательства: аргумент обмена, greedy stays ahead, матроид. Матроидный критерий — единственный, дающий «если и только если».
• Отсутствие доказательства — не «наверное, работает», а «скорее всего, есть контрпример». Стресс-тест против эталона обязателен.
• Когда точность недостижима, жадность часто остаётся лучшим полиномиальным приближением с формальной гарантией (ln n для покрытия, 1 − 1/e для субмодулярных, 2 − 1/m для makespan).
• В проде жадность ценят за скорость, инкрементальность и объяснимость — но приближённую жадность надо мониторить: измерять gap до нижней границы, а не верить, что «на наших данных ок».

Источники

• T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4-е изд., глава «Greedy Algorithms» — MIT Press
• J. Kleinberg, É. Tardos. Algorithm Design, глава 4 — лучший разбор exchange argument и greedy stays ahead: материалы
• J. Erickson. Algorithms, глава «Greedy Algorithms» — бесплатный PDF: jeffe.cs.illinois.edu
• J. Edmonds. Matroids and the greedy algorithm, 1971 — DOI
• D. A. Huffman. A Method for the Construction of Minimum-Redundancy Codes, 1952 — IEEE
• U. Feige. A threshold of ln n for approximating set cover, 1998 — DOI
• G. Nemhauser, L. Wolsey, M. Fisher. An analysis of approximations for maximizing submodular set functions, 1978 — DOI
• R. Graham. Bounds on multiprocessing timing anomalies, 1969 — DOI
• D. Pearson. A polynomial-time algorithm for the change-making problem, 2005 — DOI
• RFC 1951 (DEFLATE) — rfc-editor.org
• Разборы задач и реализации: cp-algorithms.com

Смежные статьи трека: доказательства и инварианты — https://courses.digitable.life/post/algorithms/01-analysis-and-proofs/; сортировка как фундамент жадности — https://courses.digitable.life/post/algorithms/02-sorting/; бинарный поиск по ответу, часто соседствующий с жадной проверкой, — https://courses.digitable.life/post/algorithms/03-searching-and-binary-search/; приближённые алгоритмы и NP-полнота — https://courses.digitable.life/post/algorithms/15-np-and-approximation/.

Что дальше

Жадность отказывается работать ровно там, где локальный выбор нельзя сделать безошибочно. Правильный ответ на этот отказ — не «придумать критерий похитрее», а перебрать все варианты первого шага и запомнить результаты. Это и есть динамическое программирование: Динамическое программирование: от мемоизации до оптимизаций.