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

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

Ты уже встречал жадные алгоритмы — просто ещё не называл их так. Алгоритм Дейкстры из урока 263 на каждом шаге фиксирует ближайшую непосещённую вершину и больше никогда не пересматривает это решение. Алгоритмы Прима и Крускала из урока 265 на каждом шаге добавляют самое дешёвое подходящее ребро в дерево и никогда не убирают его обратно. Все три алгоритма ты изучал как самостоятельные конструкции для конкретных задач на графах — кратчайшие пути, минимальное остовное дерево. Сейчас настало время увидеть их с другой стороны: это не три разрозненных трюка, а три частных случая одной и той же общей стратегии, применённой к разным задачам, и у этой стратегии есть точные, формально доказуемые условия, при которых она гарантированно работает.

Именно здесь жадные алгоритмы напрямую выходят на связь с машинным обучением, причём не абстрактно, а очень конкретно — через устройство одной из самых широко используемых моделей на практике. Когда алгоритм строит дерево решений (decision tree), например CART или ID3, он на каждом шаге выбирает один признак и порог разбиения, которые максимизируют прирост информации (information gain) или минимизируют примесь Джини (Gini impurity) прямо сейчас, для текущего узла — и затем никогда не возвращается, чтобы пересмотреть это разбиение в свете того, как дерево выросло дальше. Это классический, почти учебниковый жадный алгоритм: локально оптимальный выбор на каждом шаге без пересмотра. И, как ты увидишь в конце урока, у этой жадности есть цена — построенное таким способом дерево решений не гарантированно глобально оптимально, и задача построения действительно наилучшего дерева решений вообще доказанно NP-полна. Тем не менее жадный CART работает в scikit-learn, XGBoost и LightGBM для миллионов моделей каждый день, потому что вычислительная эффективность и «достаточно хороший» результат на практике перевешивают недостижимую в разумное время теоретическую оптимальность.

В этом уроке ты разберёшь саму идею жадного выбора, изучишь два формальных условия — свойство жадного выбора (greedy-choice property) и оптимальную подструктуру, — при одновременном выполнении которых жадность доказуемо даёт глобальный оптимум, переосмыслишь алгоритмы Прима, Крускала и Дейкстры именно через призму этих условий, разберёшь классическую задачу о размене монет вместе с контрпримером, который наглядно показывает, что жадность — это не универсальный рецепт, а свойство конкретной задачи с конкретными данными, изучишь задачу о выборе заявок (activity selection) как ещё один пример корректной жадной стратегии, и в конце сравнишь жадный подход с динамическим программированием там, где жадности объективно не хватает и нужен более осторожный перебор вариантов.

История

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

Строгую теоретическую основу под жадные алгоритмы подвёл канадский математик Джек Эдмондс в 1971 году в статье «Matroids and the greedy algorithm» («Матроиды и жадный алгоритм»). Он использовал понятие матроида — абстрактной алгебраической структуры, введённой ещё в 1935 году Хасслером Уитни как обобщение понятия линейной независимости в линейной алгебре на произвольные комбинаторные системы, — и доказал теорему: жадный алгоритм гарантированно находит оптимальное решение задачи максимизации веса «независимого множества» тогда и только тогда, когда система допустимых множеств образует матроид. Множество рёбер графа, не образующих цикл (то есть подмножества леса), — это в точности матроид, и именно поэтому и Крускал, и Прим работают корректно: они, каждый по-своему, жадно строят максимальное независимое множество в графовом матроиде. Эта теорема — не просто красивая математическая абстракция: она даёт точный, проверяемый критерий, по которому можно заранее, до всякого экспериментирования, понять, обречена ли жадная стратегия работать на конкретной задаче или нет. Формальный аппарат матроидов выходит за рамки этого курса, но интуиция, которую он формализует — свойство жадного выбора плюс оптимальная подструктура, — будет в центре внимания следующего раздела.

Параллельно с теорией матроидов складывалась и прикладная традиция задач, на которых жадность разбирают в каждом курсе алгоритмов. Задача о выборе заявок (activity selection problem) — классический пример из учебника Кормена, Лейзерсона, Ривеста и Штайна (CLRS), впервые изданного в 1990 году, — стала одним из самых цитируемых учебных примеров именно потому, что на ней особенно наглядно видно: не любой «интуитивно разумный» жадный критерий работает, и только один конкретный выбор (сортировка по времени окончания) доказуемо ведёт к оптимуму, тогда как соседние, столь же интуитивные варианты (по длительности, по времени начала) регулярно проваливаются. Задача о размене монет, в свою очередь, — куда более древняя, практическая проблема, восходящая ещё к устройству реальных денежных систем: почему в большинстве стран номиналы монет и купюр подобраны так, что кассиру достаточно жадно брать самую крупную подходящую монету, — и это далеко не случайность, а результат сознательного (или исторически сложившегося) проектирования системы номиналов под жадный алгоритм сдачи.

Идея жадного выбора: локальная оптимальность без пересмотра

Интуиция

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

Это резко отличает жадные алгоритмы от полного перебора и от динамического программирования, которые ты изучал в предыдущем уроке. Полный перебор рассматривает вообще все комбинации решений и выбирает лучшую из них — дорого, но надёжно. ДП тоже фактически перебирает все варианты, просто делает это умно, переиспользуя уже посчитанные результаты подзадач через мемоизацию или табулирование, — но оно всё равно на каждом шаге явно сравнивает несколько альтернатив (вспомни dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) из задачи о рюкзаке: это и есть сравнение «взять или не взять», а не слепой выбор одного варианта). Жадный алгоритм не сравнивает ничего, кроме кандидатов на текущем шаге — он никогда не заглядывает вперёд, чтобы понять, как этот выбор скажется на будущих шагах, и никогда не оглядывается назад, чтобы исправить прошлый выбор в свете новой информации.

Алгоритм

Общая схема жадного алгоритма:

1. Определить множество кандидатов — доступных на данный момент вариантов выбора.
2. Определить функцию выбора (selection function), которая на каждом шаге указывает, какой из доступных кандидатов «локально наилучший» — то есть по какому критерию сравнивать варианты (это самая содержательная и самая рискованная часть алгоритма).
3. Определить функцию допустимости (feasibility function), проверяющую, что добавление выбранного кандидата к уже накопленному частичному решению не нарушает ограничения задачи.
4. Пока не исчерпаны кандидаты и решение не завершено: выбрать локально наилучшего допустимого кандидата функцией выбора, добавить его в решение, навсегда исключить его из дальнейшего рассмотрения.
5. Вернуть накопленное решение — без единого шага пересмотра или отмены ранее сделанного выбора.

Разбор примеров

Пример 1 (лёгкий — жадный размен монет, «удобная» система). Дана система номиналов {100, 50, 10, 5, 1} (упрощённо, без копеек) и требуется выдать сдачу 187 рублей минимальным числом монет.

def greedy_change(amount, coins):
    coins = sorted(coins, reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

Трассировка: amount=187. Берём 100 → amount=87, result=[100]. Берём 50 → amount=37, result=[100,50]. Монета 10 подходит трижды: 37→27→17→7, result=[100,50,10,10,10]. Монета 5 подходит один раз: 7→2, result=[...,5]. Монета 1 подходит дважды: 2→1→0, result=[...,1,1].

Ответ: [100, 50, 10, 10, 10, 5, 1, 1] — 8 монет, и это действительно минимально возможное число монет для суммы 187 в этой системе номиналов (проверить меньшим числом монет для этой системы невозможно — любая попытка заменить крупную монету на несколько мелких только увеличивает их общее количество).

Пример 2 (средний — жадный выбор с неверным критерием проваливается). Директору переговорной комнаты нужно провести максимум встреч за день. Есть пять заявок с интервалами времени: A=(1,4), B=(3,5), C=(0,6), D=(5,7), E=(8,9) (в часах). Кажется естественным жадно брать самую короткую по длительности заявку первой — вдруг так поместится больше встреч. Отсортируем по длительности: E (1 час), A (3 часа), B (2 часа), D (2 часа), C (6 часов) → по возрастанию: E=1, B=2, D=2, A=3, C=6.

Берём E=(8,9) — допустимо, добавляем. Берём B=(3,5) — не пересекается с E, допустимо, добавляем. Берём D=(5,7) — начинается в момент 5, B заканчивается в момент 5, не пересекается, допустимо, добавляем. Берём A=(1,4) — пересекается с уже выбранным B=(3,5) (интервалы [1,4) и [3,5) перекрываются на [3,4)), недопустимо, пропускаем. Берём C=(0,6) — пересекается сразу с B и D, недопустимо, пропускаем.

Результат жадности по длительности: {E, B, D} — 3 встречи. Но легко проверить, что можно было бы взять {A, D, E} — тоже 3, или даже переставить и получить не больше 3 в принципе для этого набора данных при сортировке по длительности случайно получился оптимум. Изменим пример: добавим шестую заявку F=(4,5) продолжительностью всего 1 час. Теперь при сортировке по длительности первыми пойдут E=1, F=1; возьмём E=(8,9), затем F=(4,5) — не пересекается с E, берём. Дальше B=(3,5) пересекается с F (интервалы [3,5) и [4,5) перекрываются) — пропускаем. D=(5,7) не пересекается с F, берём. A=(1,4) не пересекается ни с чем выбранным, берём. Итог: {E,F,D,A} — 4 встречи. Здесь сортировка по длительности случайно дала неплохой результат, но в общем случае, как ты увидишь в разделе про задачу о выборе заявок дальше, сортировка по длительности не гарантирует оптимум ни для какого набора интервалов — гарантию даёт только сортировка по времени окончания, и разница между «сработало на этом примере» и «доказуемо работает всегда» — это ровно то, что отличает случайно удачный частный разбор примера (case-study) от алгоритма.

Пример 3 (важный — жадность не заменяет доказательство). Возьмём простую на вид задачу: дан массив [3, 1, 4, 1, 5], нужно выбрать подмассив (непрерывный участок) максимальной суммы, но не длиннее 3 элементов. Жадная идея «на каждом шаге добавляй элемент, если сумма растёт» здесь неприменима буквально, потому что нет пошагового процесса выбора «включать / не включать» с чёткой локальной функцией сравнения — сумма подмассива зависит от совместного набора элементов, а не от независимого решения по каждому элементу. Эта задача решается не жадностью, а прямым перебором всех подмассивов длины ≤3 (их всего $O(n)$) или скользящим окном — вывод из этого примера не в конкретном алгоритме, а в том, что жадность применима только там, где на каждом шаге действительно существует чёткий, независимый от будущего локальный выбор; если такого выбора нет, попытка натянуть жадную схему на задачу бессмысленна ещё до всякого доказательства корректности.

Почему это важно

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

Свойство жадного выбора и оптимальная подструктура: Прим, Крускал и Дейкстра как единый класс

Интуиция

Чтобы жадный алгоритм гарантированно находил глобально оптимальное решение, а не просто «неплохое», задача должна обладать двумя структурными свойствами одновременно. Первое — свойство жадного выбора (greedy-choice property): локально оптимальный выбор на первом шаге всегда можно расширить до глобально оптимального решения всей задачи, то есть жадный выбор никогда не «отрезает» путь к оптимуму. Второе — оптимальная подструктура, то же самое понятие, что ты уже видел в динамическом программировании в прошлом уроке: оптимальное решение задачи целиком содержит в себе оптимальное решение оставшейся после жадного выбора подзадачи. Разница с ДП принципиальна: в ДП оптимальная подструктура используется вместе с перебором всех вариантов первого шага, потому что заранее неизвестно, какой из них ведёт к оптимальной подзадаче. В жадных алгоритмах свойство жадного выбора устраняет саму необходимость перебора — доказано, что конкретный локально наилучший вариант первого шага гарантированно ведёт к оптимальной подзадаче, а значит, перебирать остальные варианты незачем.

Алгоритм

Общая схема доказательства корректности жадного алгоритма (метод обмена, exchange argument):

1. Взять произвольное оптимальное решение задачи $O$ (существование которого предполагается, но конкретный вид — нет).
2. Показать, что можно модифицировать $O$, заменив в нём один элемент на элемент, выбранный жадным алгоритмом на первом шаге, не ухудшив при этом качество решения (не увеличив суммарный вес, не уменьшив суммарную выгоду и так далее).
3. Тем самым построено новое оптимальное решение $O'$, которое уже содержит жадный выбор — то есть жадный выбор безопасен: он не может помешать достичь оптимума.
4. Заметить, что после исключения жадно выбранного элемента остаётся подзадача меньшего размера, и по индукции (опираясь на оптимальную подструктуру) к ней применимо то же рассуждение.
5. Повторить обменное рассуждение для каждого следующего шага — по индукции это доказывает, что вся последовательность жадных выборов даёт глобально оптимальное решение.

Разбор примеров

Пример 1 (переосмысление алгоритма Прима как жадного выбора). В уроке 265 алгоритм Прима описывался как «выращивание дерева от стартовой вершины путём добавления минимального ребра, соединяющего уже построенную часть с новой вершиной». Теперь распознаём в этом описании ровно жадную схему из предыдущего раздела: кандидаты — все рёбра, идущие из уже построенного дерева наружу; функция выбора — минимальный вес ребра; функция допустимости — ребро должно вести к вершине, ещё не входящей в дерево (чтобы не создать цикл); решение о добавлении ребра принимается один раз и никогда не пересматривается. Свойство жадного выбора здесь обеспечивается свойством разреза (cut property) минимального остовного дерева: для любого разреза графа на две части минимальное по весу ребро, пересекающее этот разрез, обязательно входит хотя бы в одно минимальное остовное дерево. Доказательство — классический обмен: если бы оптимальное минимальное остовное дерево (MST, от minimum spanning tree) не содержало это минимальное ребро разреза, в нём нашлось бы другое, более тяжёлое ребро, пересекающее тот же разрез, — заменив его на минимальное ребро, получаем дерево не большего веса, то есть тоже оптимальное, и при этом уже содержащее жадный выбор.

Пример 2 (переосмысление алгоритма Крускала как жадного выбора). Крускал устроен иначе технически — сортирует все рёбра графа по весу и жадно добавляет каждое следующее, если оно не образует цикл с уже добавленными (это и проверяет структура данных «система непересекающихся множеств», Union-Find). Но с точки зрения общей жадной схемы это тот же самый паттерн: кандидаты — все рёбра графа, отсортированные заранее; функция выбора — минимальный ещё не рассмотренный вес; функция допустимости — ребро не должно замыкать цикл. Обоснование корректности тоже опирается на то же свойство разреза: когда рассматривается очередное ребро минимального веса, оно соединяет две разные компоненты связности (иначе замкнуло бы цикл и было бы отброшено), а значит, представляет собой минимальное ребро, пересекающее разрез между этими двумя компонентами, — то же самое обменное рассуждение, что и для Прима, просто применённое в другом порядке обхода рёбер. Не случайно оба алгоритма для графа с попарно различными весами рёбер всегда дают один и тот же результат — они доказуемо решают одну и ту же задачу, опираясь на одно и то же структурное свойство, просто с разных сторон.

Пример 3 (переосмысление алгоритма Дейкстры как жадного выбора и роль условия неотрицательности весов). В уроке 263 корректность жадного выбора Дейкстры (фиксация ближайшей непосещённой вершины как окончательной) была обоснована так: любой альтернативный путь до этой вершины через другую непосещённую вершину не может оказаться короче, потому что он обязан добавить неотрицательный «довесок» к уже не меньшей оценке расстояния. Это в точности доказательство свойства жадного выбора методом обмена, специфичное для этой задачи: заменить любой гипотетический более короткий путь на прямую фиксацию текущей минимальной оценки невозможно, значит, жадный выбор безопасен. А контрпример с отрицательными весами рёбер, разобранный в том же уроке (граф, где релаксация после фиксации вершины неожиданно находит более короткий путь), — это ровно демонстрация того, что происходит, когда свойство жадного выбора перестаёт выполняться: как только веса могут быть отрицательными, зафиксированная как «минимальная» вершина больше не гарантированно оптимальна, обменное рассуждение ломается, и жадный алгоритм Дейкстры перестаёт быть корректным — приходится переходить к алгоритму Беллмана-Форда, который явно перебирает (релаксирует) все рёбра многократно, отказываясь от жадной фиксации вовсе.

Почему это важно

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

Задача о размене монет: жадность работает не всегда

Интуиция

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

Алгоритм

Жадный размен монет:

1. Отсортировать номиналы по убыванию.
2. Для каждого номинала, начиная с самого крупного: пока оставшаяся сумма не меньше номинала, вычитать номинал из суммы и добавлять монету этого номинала в результат.
3. Перейти к следующему по убыванию номиналу.
4. Вернуть список использованных монет, когда сумма обнулится (или сообщить, что размен невозможен, если сумма не обнулилась после прохода по всем номиналам).

Разбор примеров

Пример 1 (жадность работает — канонические номиналы США). Система номиналов {1, 5, 10, 25} (пенни, никель, дайм, четвертак), сумма 41 цент.

def greedy_change(amount, coins):
    coins = sorted(coins, reverse=True)
    result = []
    for coin in coins:
        count = amount // coin
        result.extend([coin] * count)
        amount -= coin * count
    return result

greedy_change(41, [1, 5, 10, 25])

Трассировка: 41 // 25 = 1 → берём 25, остаток 16. 16 // 10 = 1 → берём 10, остаток 6. 6 // 5 = 1 → берём 5, остаток 1. 1 // 1 = 1 → берём 1, остаток 0.

Ответ: [25, 10, 5, 1] — 4 монеты, и это действительно минимально возможное число монет для 41 цента в этой системе — прямым перебором несложно убедиться, что 3 монетами этих номиналов 41 не набрать.

Пример 2 (жадность работает — российские рубли). Система номиналов {1, 2, 5, 10} рублей, сумма 28 рублей. 28 // 10 = 2 → две монеты по 10, остаток 8. 8 // 5 = 1 → одна монета 5, остаток 3. 3 // 2 = 1 → одна монета 2, остаток 1. 1 // 1 = 1 → одна монета 1.

Ответ: [10, 10, 5, 2, 1] — 5 монет, снова минимально возможное число для этой суммы в этой системе. Обе системы, американская и российская, устроены так, что каждый номинал либо кратен предыдущему, либо очень близок к этому (соотношения 1-2-5-10 и 1-5-10-25), и именно эта структура — не случайность, а результат сознательного или исторически устоявшегося проектирования денежной системы — гарантирует, что жадная стратегия оптимальна для любой суммы.

Пример 3 (контрпример — жадность проваливается на произвольной системе). Система номиналов {1, 3, 4}, сумма 6.

greedy_change(6, [1, 3, 4])

Трассировка: 6 // 4 = 1 → берём 4, остаток 2. Номинал 3 не подходит (2 < 3), пропускаем. 2 // 1 = 2 → берём две монеты 1.

Жадный ответ: [4, 1, 1] — 3 монеты. Но существует размен [3, 3] — тоже сумма 6, и всего 2 монеты! Жадный алгоритм дал заведомо неоптимальный результат: он «пожадничал», забрав крупную монету 4 на первом шаге, и тем самым отрезал себе путь к лучшему решению {3, 3}, потому что после вычитания 4 из 6 число 3 уже не помещается в оставшуюся сумму 2. Здесь наглядно нарушается именно свойство жадного выбора из предыдущего раздела: локально наилучший выбор первого шага (монета 4) не может быть расширен до глобально оптимального решения — обменное рассуждение, которое сработало для Прима, Крускала и Дейкстры, для этой системы номиналов попросту неверно, и никакое доказательство его не спасёт, потому что утверждение ложно.

Пример 4 (второй классический контрпример — насколько сильно может ошибиться жадность). Система номиналов {1, 10, 25}, сумма 30.

Жадно: 30 // 25 = 1 → берём 25, остаток 5. Номинал 10 не подходит. 5 // 1 = 5 → пять монет по 1.

Жадный ответ: [25, 1, 1, 1, 1, 1] — 6 монет. Но [10, 10, 10] даёт те же 30 всего тремя монетами! Разрыв здесь не «на одну монету больше», а вдвое хуже оптимума — жадность может ошибаться не символически, а очень существенно, и величина ошибки заранее не ограничена без знания конкретной системы номиналов.

Почему это важно

Этот раздел — прямая иллюстрация тезиса из предыдущего раздела: жадность — это свойство конкретной задачи с конкретными входными данными, а не универсальный алгоритмический приём. Реальные денежные системы неслучайно каноничны: их номиналы веками (а иногда — намеренно, при денежных реформах) подбирались так, чтобы у продавцов и покупателей не было нужды в сложных вычислениях — достаточно жадности. Но стоит алгоритму столкнуться с произвольным набором «номиналов» — а на практике это происходит регулярно, например при расчёте минимального числа купюр/платежей в системах с нестандартными правилами, при расчёте минимального числа прыжков между произвольными контрольными точками, при формировании пакетов доставки из товаров произвольного веса, — как жадная эвристика перестаёт давать какие-либо гарантии. Для произвольной системы номиналов задача решается не жадностью, а динамическим программированием из прошлого урока: dp[amount] = min(dp[amount - coin] + 1) по всем номиналам coin ≤ amount, с базой dp[0] = 0 — тот же самый паттерн, что в задаче о рюкзаке, только на одномерном массиве сумм, и к этому мы вернёмся отдельно в разделе сравнения с ДП.

Задача о выборе заявок (activity selection problem)

Интуиция

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

Логика в следующем: заявка, которая заканчивается раньше всех остальных, освобождает переговорную комнату раньше всех остальных вариантов, а значит, оставляет максимум свободного времени для всех последующих заявок — вне зависимости от того, когда она началась и сколько длилась. Если у тебя пять кандидатов, конкурирующих за первое место в расписании, и один из них заканчивается в 10:00, а другой (пусть даже он начался позже и длится меньше) заканчивается в 10:30, выбор первого варианта никогда не может быть хуже — он освобождает время раньше и оставляет как минимум столько же вариантов на будущее, сколько и второй.

Алгоритм

Жадный выбор заявок (activity selection):

1. Отсортировать все заявки по времени окончания в порядке возрастания.
2. Выбрать первую заявку в отсортированном порядке (с минимальным временем окончания), добавить в результат, запомнить время её окончания как last_finish.
3. Для каждой следующей заявки в отсортированном порядке: если её время начала не меньше last_finish (не пересекается с последней выбранной), добавить её в результат и обновить last_finish временем её окончания; иначе — пропустить эту заявку навсегда.
4. Вернуть накопленный результат — набор попарно непересекающихся заявок максимального размера.

def activity_selection(activities):
    # activities: список пар (start, finish)
    activities = sorted(activities, key=lambda a: a[1])
    selected = [activities[0]]
    last_finish = activities[0][1]

    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected

Разбор примеров

Пример 1 (лёгкий — стандартная трассировка). Заявки [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)] (классический учебный набор). Сортировка по времени окончания даёт порядок: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16) — они уже отсортированы по второй координате.

Берём (1,4), last_finish=4. (3,5): 3 < 4 — пропускаем. (0,6): 0 < 4 — пропускаем. (5,7): 5 ≥ 4 — берём, last_finish=7. (3,9): 3 < 7 — пропускаем. (5,9): 5 < 7 — пропускаем. (6,10): 6 < 7 — пропускаем. (8,11): 8 ≥ 7 — берём, last_finish=11. (8,12): 8 < 11 — пропускаем. (2,14): 2 < 11 — пропускаем. (12,16): 12 ≥ 11 — берём, last_finish=16.

Ответ: {(1,4), (5,7), (8,11), (12,16)} — 4 заявки, и это действительно максимально возможное число непересекающихся заявок для этого набора данных.

Пример 2 (средний — контрпример к сортировке по времени начала). Заявки [(1,10), (2,3), (4,5), (6,7)]. Отсортируем по времени начала (неправильный критерий) и применим ту же жадную схему: (1,10) — берём первой, last_finish=10. (2,3): 2 < 10 — пропускаем. (4,5): 4 < 10 — пропускаем. (6,7): 6 < 10 — пропускаем.

Результат при сортировке по началу: {(1,10)} — всего 1 заявка. А ведь если бы мы не брали длинную (1,10) первой, все три остальные — (2,3), (4,5), (6,7) — попарно не пересекаются между собой и легко умещаются вместе! Отсортируем этот же набор правильно, по времени окончания: (2,3), (4,5), (6,7), (1,10). Берём (2,3), last_finish=3. (4,5): 4≥3 — берём, last_finish=5. (6,7): 6≥5 — берём, last_finish=7. (1,10): 1<7 — пропускаем.

Правильный ответ: {(2,3), (4,5), (6,7)} — 3 заявки, втрое больше, чем при сортировке по времени начала. Этот пример наглядно показывает, что интуитивно правдоподобный критерий «бери самое раннее из доступного» без уточнения «раннее по какому концу интервала» может катастрофически ошибиться — разница между «раньше начинается» и «раньше заканчивается» здесь решает всё.

Пример 3 (важный — обменное доказательство оптимальности критерия по времени окончания). Пусть a₁ — заявка с минимальным временем окончания среди всех заявок, а O — произвольное оптимальное (максимальное по размеру) решение задачи, не обязательно содержащее a₁. Пусть a — заявка из O с минимальным временем окончания среди заявок самого O. По выбору a₁ (минимальное время окончания среди всех заявок вообще) выполняется finish(a₁) ≤ finish(a). Заменим в O заявку a на a₁, получив новый набор O' того же размера, что и O. Поскольку a была первой (по времени окончания) в наборе O, все остальные заявки O начинаются не раньше finish(a), а значит, и не раньше finish(a₁) (так как finish(a₁) ≤ finish(a)) — то есть замена a на a₁ не создаёт новых конфликтов с остальными заявками O. Набор O' — тоже допустимое решение того же размера, что и O, то есть тоже оптимальное, и при этом уже содержит a₁.

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

Почему это важно

Задача о выборе заявок — не абстрактное упражнение, а прямая модель систем бронирования переговорных комнат, планирования использования оборудования (станков, серверов, GPU для обучения моделей), составления расписания эфирного времени и авиарейсов — везде, где ограниченный ресурс с единственным «слотом времени» нужно распределить между максимальным числом заявок без пересечений. И одновременно этот раздел закрепляет главный методологический урок всего блока про жадные алгоритмы: правильный жадный критерий редко очевиден интуитивно с первого взгляда, разные, на вид одинаково разумные, критерии сортировки (по началу, по длительности, по окончанию) дают радикально разные результаты, и единственный надёжный способ выбрать правильный — формально доказать через обменное рассуждение, что именно этот критерий обладает свойством жадного выбора для этой конкретной задачи.

Сравнение с динамическим программированием: когда жадности недостаточно

Интуиция

Есть пары задач, которые выглядят почти идентично сформулированными, но одна из них решается жадно с гарантией оптимальности, а вторая требует полноценного динамического программирования — и разница между ними именно в том, обладает ли задача свойством жадного выбора. Классическая пара для иллюстрации — дробный рюкзак (fractional knapsack) и рюкзак 0/1 (0/1 knapsack) из прошлого урока. В дробном рюкзаке предметы можно брать частично (скажем, зерно, нефть, любую делимую субстанцию) — и для него существует доказуемо корректная жадная стратегия. В рюкзаке 0/1 (ноутбуки, книги, неделимые предметы — либо берём целиком, либо не берём вовсе) та же самая жадная идея перестаёт быть оптимальной, и её нужно заменить на полноценное ДП из урока 270.

Сравнение (таблица компромиссов)

Разбор примеров

Пример 1 (дробный рюкзак — жадность работает). Три предмета: вес/ценность (10, 60), (20, 100), (30, 120), вместимость рюкзака 50. Жадный критерий — отношение ценность/вес: 60/10=6, 100/20=5, 120/30=4. Сортируем по убыванию отношения: предмет 1 (6), предмет 2 (5), предмет 3 (4).

Берём предмет 1 целиком: вес 10, ценность 60, остаток вместимости 40. Берём предмет 2 целиком: вес 20, ценность 100, остаток 20. Предмет 3 весит 30, а осталось только 20 — берём 20/30 его доли: ценность 120 × (20/30) = 80.

Ответ (дробный рюкзак): 60 + 100 + 80 = 240, и это доказуемо оптимально — свойство жадного выбора для дробного рюкзака доказывается тем же обменным рассуждением: если оптимальное решение не берёт предмет с максимальным отношением ценность/вес первым (полностью, пока хватает места), его можно заменить на эквивалентный по весу кусочек этого предмета без потери ценности, а часто и с выигрышем, потому что делимость снимает все комбинаторные ограничения.

Пример 2 (рюкзак 0/1 — та же жадность проваливается). Те же три предмета, та же вместимость 50, но теперь предметы неделимы. Тот же жадный алгоритм по отношению ценность/вес: берём предмет 1 целиком (вес 10, ценность 60, остаток 40), берём предмет 2 целиком (вес 20, ценность 100, остаток 20), предмет 3 весит 30 — не помещается в оставшиеся 20, взять частично нельзя, пропускаем.

Жадный ответ (0/1): 60 + 100 = 160, вес 30 из 50 использован, 20 вместимости пропало впустую. Но переберём альтернативу: предметы 2 и 3 вместе весят 20+30=50 — влезают ровно, суммарная ценность 100+120=220. Оптимум 220 — заметно выше жадных 160. Динамическое программирование из урока 270 (dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])) корректно находит именно 220, потому что явно сравнивает вариант «не брать предмет 1» с вариантом «брать» — то есть не отрезает себе путь к решениям, где выгоднее пропустить предмет с лучшим соотношением ради пары предметов, которые вместе используют вместимость эффективнее.

Пример 3 (размен монет — ДП чинит то, что сломала жадность). Возвращаемся к контрпримеру из раздела про монеты: номиналы {1, 3, 4}, сумма 6. Жадность дала [4,1,1] — 3 монеты, хотя оптимум [3,3] — 2 монеты. Решим ту же задачу динамическим программированием, тем же паттерном, что и в уроке 270:

def min_coins_dp(amount, coins):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount]

min_coins_dp(6, [1, 3, 4])

Трассировка ключевых значений: dp[0]=0. dp[1]=dp[0]+1=1 (монета 1). dp[2]=dp[1]+1=2 (монета 1 дважды). dp[3]=min(dp[2]+1, dp[0]+1)=min(3,1)=1 (монета 3 целиком). dp[4]=min(dp[3]+1, dp[1]+1, dp[0]+1)=min(2,2,1)=1 (монета 4 целиком). dp[5]=min(dp[4]+1, dp[2]+1, dp[1]+1)=min(2,3,2)=2 (например, 4+1 или 3+1+1→ берём минимум 2). dp[6]=min(dp[5]+1, dp[3]+1, dp[2]+1)=min(3,2,3)=2 (это dp[3]+1, то есть 3+3).

Ответ: dp[6]=2, совпадает с истинным оптимумом {3,3}, в отличие от жадных 3 монет. ДП явно рассматривает все варианты последней монеты (1, 3, 4) для каждой промежуточной суммы и берёт минимум — то есть делает ровно то, чего жадность принципиально не делает: сравнивает альтернативы вместо того, чтобы слепо фиксировать первый локально удачный вариант.

Почему это важно

Этот раздел закрывает главный практический вопрос всего урока: как понять, обойдёшься ли ты быстрым жадным алгоритмом или придётся писать полноценное ДП с квадратичной (или большей) сложностью. Ответ — не интуиция и не «попробовать на паре примеров», а формальная проверка свойства жадного выбора для конкретной постановки задачи с конкретными входными ограничениями (делимость предметов, каноничность системы номиналов, знак весов рёбер). Именно поэтому в машинном обучении построение дерева решений — жадная процедура: доказать свойство жадного выбора для разбиения по информационному критерию на каждом шаге в общем случае невозможно (выбор лучшего признака для текущего узла не гарантирует глобально наилучшее дерево — ранние удачные с виду разбиения могут «запереть» алгоритм в структурно неоптимальной ветке), и разработчики CART, ID3 и C4.5 сознательно выбрали жадность не потому, что она оптимальна, а потому что полный перебор всех возможных деревев решений вычислительно неподъёмен: Хайафил и Ривест в 1976 году формально доказали, что построение оптимального бинарного дерева решений — NP-полная задача. Жадность здесь — не заблуждение, а осознанный инженерный компромисс между гарантированной оптимальностью и практической выполнимостью за разумное время, и умение опознать этот компромисс — именно то, что должен уметь любой специалист по данным, работающий не только с готовыми библиотеками, но и понимающий, что происходит внутри DecisionTreeClassifier.fit().

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Жадным алгоритмом набрать сумму 27 рублей монетами номиналов {1, 2, 5, 10}, записав последовательность выбранных монет.

Задание 2: Своими словами объяснить, чем жадный алгоритм принципиально отличается от динамического программирования на уровне того, что происходит на каждом шаге.

Задание 3: Жадным алгоритмом набрать сумму 48 центов монетами номиналов США {1, 5, 10, 25} и проверить, что это действительно минимальное число монет.

Задание 4: Дан набор заявок [(1,3), (2,4), (3,5), (0,7)]. Применить жадный алгоритм выбора заявок по времени окончания и указать выбранное максимальное подмножество.

Задание 5: Объяснить на конкретном контрпримере, почему сортировка заявок по времени начала не гарантирует оптимальное решение задачи о выборе заявок.

Задание 6: Своими словами (без формул) объяснить суть обменного рассуждения (exchange argument), которым доказывается свойство разреза для минимального остовного дерева.

Задание 7: Для номиналов {1, 3, 4} жадно разменять сумму 6, затем найти истинно оптимальный размен и сравнить число монет.

Задание 8: Сформулировать два условия, при одновременном выполнении которых жадный алгоритм гарантированно даёт глобально оптимальное решение.

Задание 9: Три предмета для дробного рюкзака: вес/ценность (5, 30), (10, 40), (15, 45), вместимость 20. Найти жадное (оптимальное) решение по отношению ценность/вес.

Задание 10: Объяснить в одном предложении, чем задача о выборе заявок (activity selection) похожа на задачу о минимальном остовном дереве с точки зрения общей жадной схемы.

Средние задания (11–20)

Задание 11: Кратко записать обменное доказательство, почему заявка с минимальным временем окончания всегда безопасно включить в оптимальное решение задачи о выборе заявок.

Задание 12: Для номиналов {1, 10, 25} жадно разменять сумму 30, затем найти истинный оптимум и сравнить.

Задание 13: Реализовать функцию жадного размена монет на Python и применить её к сумме 63 и номиналам {1, 5, 10, 25, 50}.

def greedy_change(amount, coins):
    coins = sorted(coins, reverse=True)
    result = []
    for coin in coins:
        count = amount // coin
        result.extend([coin] * count)
        amount -= coin * count
    return result

greedy_change(63, [1, 5, 10, 25, 50])

Задание 14: Переосмыслить алгоритм Прима как жадный алгоритм: указать кандидатов, функцию выбора и функцию допустимости на каждом шаге.

Задание 15: Переосмыслить алгоритм Крускала как жадный алгоритм: что сортируется, какой критерий выбора и какая структура данных обеспечивает допустимость.

Задание 16: Переосмыслить алгоритм Дейкстры как жадный алгоритм и объяснить, почему нарушение неотрицательности весов рёбер ломает свойство жадного выбора.

Задание 17: Для предметов 0/1 рюкзака (10,60), (20,100), (30,120) и вместимости 50 показать, что жадность по отношению ценность/вес даёт результат хуже оптимума, и найти оптимум.

Задание 18: Реализовать функцию activity_selection на Python и применить к заявкам [(5,9), (1,2), (3,4), (0,6), (8,11), (5,7), (3,9)].

def activity_selection(activities):
    activities = sorted(activities, key=lambda a: a[1])
    selected = [activities[0]]
    last_finish = activities[0][1]
    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    return selected

activity_selection([(5,9),(1,2),(3,4),(0,6),(8,11),(5,7),(3,9)])

Задание 19: Придумать собственный небольшой набор из 3 номиналов монет, для которого жадный размен даёт неоптимальный результат, и показать это на конкретной сумме.

Задание 20: Объяснить, в каком именно смысле построение дерева решений (выбор признака и порога с максимальным приростом информации на каждом узле) — это жадный алгоритм, и что означает «не пересматривать решение» применительно к структуре дерева.

Продвинутые задания (21–30)

Задание 21: Дать полное формальное обменное доказательство свойства разреза для минимального остовного дерева (граф с попарно различными весами рёбер).

Задание 22: Реализовать ДП-решение задачи о размене монет (минимальное число монет) для номиналов {1, 3, 4} и суммы 6, подтвердив, что результат совпадает с истинным оптимумом 2.

def min_coins_dp(amount, coins):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount]

min_coins_dp(6, [1, 3, 4])

Задание 23: Реализовать восстановление конкретного набора монет (а не только их числа) для ДП-решения задачи о размене монет.

def min_coins_with_set(amount, coins):
    dp = [float('inf')] * (amount + 1)
    used = [None] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1
                used[a] = coin

    result, a = [], amount
    while a > 0:
        result.append(used[a])
        a -= used[a]
    return result, dp[amount]

min_coins_with_set(6, [1, 3, 4])

Задание 24: Сравнить асимптотическую сложность жадного размена монет и ДП-размена и объяснить, чем приходится платить за гарантию оптимальности.

Задание 25: Объяснить, почему для задачи о выборе заявок «с весами» (у каждой заявки есть своя ценность, а не просто единичный вклад в счётчик) простой жадный выбор по времени окончания перестаёт гарантировать оптимум, и какой подход нужен вместо него.

Задание 26: Кратко описать шаги жадного построения кода Хаффмана по частотам символов {a:5, b:9, c:12, d:13, e:16, f:45} (объединение двух наименьших частот на каждом шаге) без полной трассировки до конца.

Задание 27: Объяснить практическое значение теоремы Хайафила и Ривеста (1976) о NP-полноте построения оптимального дерева решений для того, почему scikit-learn использует именно жадный алгоритм CART, а не точный перебор.

Задание 28: Кратко изложить обменное доказательство оптимальности жадного алгоритма для дробного рюкзака (сортировка по отношению ценность/вес).

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

для amount от 1 до некоторого MAX:
    greedy_count = число монет в greedy_change(amount, coins)
    dp_count = min_coins_dp(amount, coins)
    если greedy_count != dp_count:
        вывести amount как контрпример

Задание 30: Сформулировать общий чек-лист из нескольких пунктов: как для новой, ранее не встречавшейся задачи оптимизации решить, можно ли применить жадный алгоритм, или необходимо динамическое программирование.

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

Ошибка 1. Применяют жадный алгоритм к новой задаче только потому, что он сработал на паре тестовых примеров, без формального доказательства свойства жадного выбора.

Как выглядит: код проходит собственноручно придуманные тесты, но ломается на скрытых тестах или реальных данных с другой структурой.

Почему возникает: жадная идея почти всегда интуитивно понятна и приятно проста в реализации, из-за чего кажется самоочевидно верной, а контрпримеры (как {1,3,4} для монет) на маленьких «удобных» тестах просто не всплывают случайно.

Как правильно: прежде чем доверять жадности, попытаться формально доказать свойство жадного выбора методом обмена или явно поискать контрпример для граничных случаев входных данных.

Ошибка 2. В задаче о выборе заявок сортируют по времени начала или по длительности вместо времени окончания.

Как выглядит: алгоритм технически реализован верно (жадный проход, проверка пересечений), но даёт неоптимальный результат на конкретных наборах интервалов.

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

Как правильно: использовать единственный доказанный критерий — сортировку по времени окончания, и явно опираться на обменное доказательство из раздела про выбор заявок, а не на интуицию.

Ошибка 3. Используют жадный алгоритм по отношению ценность/вес для рюкзака 0/1, забывая, что предметы неделимы.

Как выглядит: реализация выглядит идентично корректному алгоритму для дробного рюкзака, но применяется к задаче, где предметы нельзя дробить.

Почему возникает: формулировки дробного и 0/1 рюкзака отличаются одним словом («можно брать частично» или нет), и это отличие легко упустить, скопировав знакомый жадный подход по аналогии.

Как правильно: для 0/1 рюкзака всегда использовать динамическое программирование из урока 270; жадность по отношению ценность/вес корректна только тогда, когда предметы делимы.

Ошибка 4. Применяют жадный размен монет к произвольной, не проверенной на каноничность системе номиналов и считают результат оптимальным без доказательства.

Как выглядит: код работает и даёт «какой-то» результат для любой суммы, ошибка незаметна, пока кто-то не сравнит результат с истинным минимумом.

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

Как правильно: для системы номиналов, каноничность которой не доказана явно, использовать ДП-решение dp[amount] = min(dp[amount-coin]+1), которое корректно для любой системы номиналов, канонической или нет.

Ошибка 5. Путают локальный оптимум с глобальным, считая, что раз каждый шаг алгоритма был «лучшим из возможных на этом шаге», то и итоговый результат обязан быть лучшим из возможных в принципе.

Как выглядит: аргумент вида «на каждом шаге я брал самое выгодное — значит, в сумме получилось самое выгодное», без проверки, не отрезал ли ранний выбор путь к лучшей общей комбинации.

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

Как правильно: держать в голове контрпример с монетами {1,3,4}: жадный выбор 4 на первом шаге был локально лучшим (уменьшал остаток сильнее всего), но отрезал путь к глобально лучшему решению {3,3} — «лучше сейчас» не равно «лучше в итоге» без формального обоснования.

Ошибка 6. Считают, что жадное построение дерева решений (CART, ID3) находит наилучшее возможное дерево, и удивляются, когда переставленный порядок признаков или изменённые пороги дают другое дерево с иным качеством.

Как выглядит: ожидание, что DecisionTreeClassifier из scikit-learn всегда выдаёт теоретически наилучшую модель для датасета, и попытка «починить» её точечными изменениями гиперпараметров вместо понимания, что жадность в принципе не даёт такой гарантии.

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

Как правильно: помнить, что задача построения оптимального дерева решений NP-полна (Хайафил и Ривест, 1976), жадный CART находит лишь локально разумное, а не доказуемо наилучшее дерево, и компенсировать это ансамблевыми методами (случайный лес, бустинг), а не ожиданием глобальной оптимальности от одного дерева.

Главное запомнить

• Жадный алгоритм на каждом шаге выбирает единственный локально оптимальный вариант по заданному критерию и никогда не пересматривает уже сделанный выбор — в отличие от ДП, которое явно сравнивает альтернативы на каждом шаге.

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

• Алгоритмы Прима, Крускала и Дейкстры — не три разрозненных трюка, а три конкретных примера одной и той же жадной схемы: у Прима и Крускала свойство жадного выбора обосновывается свойством разреза MST, у Дейкстры — неотрицательностью весов рёбер.

• Задача о размене монет жадностью решается корректно только для канонических систем номиналов (например, российские рубли, американские центы); для произвольной системы (классический пример — номиналы {1,3,4}) жадность может дать заведомо неоптимальный результат.

• Задача о выборе заявок (activity selection) решается жадно и корректно только при сортировке по времени окончания — сортировка по времени начала или по длительности не гарантирует оптимум, что доказывается конкретными контрпримерами.

• Формальное доказательство корректности жадного алгоритма строится методом обмена (exchange argument): показывается, что произвольное оптимальное решение можно преобразовать так, чтобы оно содержало жадный выбор, без потери качества.

• Дробный рюкзак решается жадно (по отношению ценность/вес) и доказуемо оптимально; рюкзак 0/1 с той же жадной идеей может давать результат, заметно хуже оптимума, и требует динамического программирования.

• Для произвольной системы номиналов задача о размене монет корректно решается ДП: dp[amount] = min(dp[amount-coin] + 1) по всем допустимым номиналам — тот же паттерн, что и рюкзак из урока 270.

• Жадное построение дерева решений (выбор признака и порога с максимальным приростом информации на каждом узле) — практически важный, но не оптимальный алгоритм: задача построения наилучшего дерева решений доказанно NP-полна, поэтому жадность здесь — инженерный компромисс, а не гарантия.

• Прежде чем доверять жадному алгоритму для новой задачи, нужно формально проверить свойство жадного выбора или явно поискать контрпример — успех на паре тестовых примеров ничего не доказывает.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается на прошлый урок 270 про динамическое программирование — понимание оптимальной подструктуры и перекрывающихся подзадач было обязательным условием, чтобы увидеть, чем жадный подход отличается от ДП, а не просто выглядит как его упрощённая версия. Не менее важны уроки 263 (алгоритм Дейкстры) и 265 (минимальное остовное дерево, алгоритмы Прима и Крускала) — этот урок не вводил их заново, а переосмысливал уже знакомые тебе алгоритмы через единую формальную рамку свойства жадного выбора и оптимальной подструктуры.

Что изучить дальше

Следующий урок 272 разбирает стратегию «разделяй и властвуй» (divide and conquer) — ты уже частично видел эту идею в быстрой сортировке и сортировке слиянием (уроки 267–268), но урок 272 формализует её как самостоятельную парадигму и покажет, что она сравнима по духу с жадными алгоритмами и ДП, но решает задачи, не сводящиеся ни к одной, ни к другой схеме: там, где задача естественно распадается на независимые подзадачи одинаковой структуры, не связанные пересекающимися подпроблемами. Дальше в курсе, при более глубоком изучении деревьев решений (урок 316) и ансамблевых методов (случайный лес, урок 317), ты вернёшься к жадному построению разбиений на новом уровне — увидишь, как случайный лес компенсирует ограничения жадности одного дерева усреднением множества независимо построенных деревьев, а бустинг — последовательной коррекцией ошибок предыдущих деревьев.

Где это нужно в жизни

🤖 Машинное обучение. Жадное построение дерева решений (CART, ID3, C4.5) — самый прямой пример из этого урока: выбор признака и порога с максимальным приростом информации на каждом узле, без пересмотра в свете дальнейшего роста дерева. Ровно та же жадность лежит в основе градиентного бустинга (каждое следующее дерево жадно строится, чтобы исправить текущие ошибки ансамбля, без пересмотра уже добавленных деревьев) и в основе многих алгоритмов отбора признаков (forward/backward feature selection жадно добавляет или убирает по одному признаку за шаг).

📡 Сжатие данных. Алгоритм Хаффмана — классический жадный алгоритм (объединение двух узлов с наименьшей частотой на каждом шаге), лежащий в основе множества форматов сжатия без потерь, включая ZIP, JPEG и MP3, и используемый почти в каждой системе передачи данных, сжимающей информацию перед отправкой по сети.

🗓️ Планирование и логистика. Задача о выборе заявок напрямую моделирует системы бронирования переговорных комнат, расписания использования оборудования и GPU-кластеров для обучения моделей, составление расписаний конференций и авиарейсов — везде, где нужно максимизировать число непересекающихся использований ограниченного ресурса.

💳 Финансовые и платёжные системы. Задача о размене монет — не только учебный пример: расчёт минимального числа купюр или транзакций при выплатах, кэшбэках и переводах в системах с нестандартными номиналами или лимитами регулярно требует явной проверки, каноническая ли используется система значений, — иначе жадный алгоритм сдачи будет незаметно давать неоптимальные (более дорогие в обработке) результаты.

Интересные факты

• Теоретическая основа, объясняющая, почему жадность работает для одних задач и не работает для других, — теория матроидов, введённая Хасслером Уитни в 1935 году как алгебраическое обобщение линейной независимости, и связанная с жадными алгоритмами Джеком Эдмондсом в 1971 году: жадный алгоритм гарантированно оптимален для задачи максимизации веса независимого множества тогда и только тогда, когда допустимые множества образуют матроид.

• Алгоритм Хаффмана, придуманный в 1952 году Дэвидом Хаффманом ещё во время учёбы в MIT как решение задачи в рамках курсовой работы (вместо сдачи финального экзамена по теории информации), — один из самых распространённых жадных алгоритмов в истории: он используется внутри форматов ZIP, JPEG, PNG, MP3 и множества сетевых протоколов сжатия данных прямо сейчас, пока ты читаешь этот текст.

• Тот факт, что построение доказуемо наилучшего дерева решений — NP-полная задача, был формально установлен Лораном Хайафилом и Рональдом Ривестом в 1976 году (тем самым Рональдом Ривестом, чья фамилия — буква «R» в названии алгоритма шифрования RSA); именно эта теорема объясняет, почему все современные библиотеки машинного обучения строят деревья решений жадно, а не точным перебором.

• Каноничность системы монетных номиналов — не случайное совпадение, а изученное математическое свойство: для системы номиналов вида {1, c, c², c³, ...} (каждый следующий номинал в фиксированное число раз больше предыдущего) жадный алгоритм гарантированно оптимален при любом c ≥ 2, что объясняет, почему десятичные системы номиналов вида «1-2-5-10-20-50» так распространены по всему миру — они спроектированы (или естественно выродились за века использования) под жадную арифметику в голове у кассира.

Лайфхаки

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

• Если для задачи существует несколько интуитивно правдоподобных критериев сортировки (по началу, по концу, по длительности, как в задаче о выборе заявок), выпиши для каждого отдельный маленький контрпример вручную — почти всегда только один из критериев выдерживает такую проверку.

• Держи под рукой готовую пару контрпримеров для размена монет — {1,3,4} с суммой 6 и {1,10,25} с суммой 30 — как быстрый тест: если жадный код проходит оба, это ещё ничего не значит для произвольной системы, но если не проходит хотя бы один — система точно не каноническая.

• Для задач, где неочевидно, работает ли жадность, напиши параллельно жадное и ДП-решение и сравни результаты на большом наборе случайных входов — расхождение результатов на любом входе немедленно опровергает жадность, а совпадение на многих входах (хотя формально ничего не доказывает) даёт практическую уверенность быстрее, чем попытка провести доказательство вручную.

• При работе с деревьями решений в scikit-learn или похожих библиотеках помни, что жадность CART — источник нестабильности модели: небольшое изменение обучающих данных может привести к совсем другому дереву из-за того, что раннее разбиение было выбрано жадно и чуть иначе на новых данных; для устойчивости используй ансамбли (случайный лес, бустинг), а не одно жадно построенное дерево.

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

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

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