Алгоритмы с нуля
Что это жадный алгоритм? Локальный выбор против DP
Тебе нужно набрать 30 центов сдачи монетами США. Почти не думая ты тянешься за четвертаком, потом за пятаком — готово, две монеты. Ты не рисовал дерево решений и не перебирал все комбинации. Ты схватил самую большую монету которая поместилась, потом следующую самую большую, и ни разу не оглянулся. У этого инстинкта есть имя: жадный алгоритм. Это простейший, самый быстрый способ построить решение — и иногда он ровно неверен. В прошлом разделе динамическое программирование тщательно исследовало каждую комбинацию выборов подзадач. Жадный отказывается это делать. Он фиксирует один локальный выбор на каждом шаге и идёт дальше. Весь навык в том чтобы знать когда этот срез пути безопасен.
После этого урока ты можешь определить жадный алгоритм: он строит решение, повторно делая локально лучший выбор и никогда его не пересматривая. Ты можешь назвать два условия которые делают жадный корректным — свойство жадного выбора (глобально оптимальное решение всегда может начинаться с локально лучшего выбора) и оптимальную подструктуру (оптимальное решение содержит оптимальные решения своих подзадач). Ты можешь сравнить жадный с динамическим программированием: DP исследует все комбинации выборов подзадач и хранит лучшую, тогда как жадный фиксирует один выбор и никогда не откатывается — так что жадный быстрее, но корректен лишь иногда. Ты можешь привести пример где жадный работает (размен в канонической системе США 25) и конкретный контрпример где он проваливается (4 для суммы 6: жадный даёт 4+1+1 = 3 монеты, но оптимум это 3+3 = 2 монеты). Ты понимаешь почему это значит что жадный алгоритм должен быть доказан корректным, а не просто предположен — это тема следующего урока. И ты можешь назвать типичную стоимость: когда жадный корректен, он обычно O(n log n), доминирует начальная сортировка.
Что это жадный алгоритм?
Жадный алгоритм строит решение по одной части за раз. На каждом шаге он делает выбор который выглядит лучшим прямо сейчас — локально оптимальный ход — и потом никогда не пересматривает этот выбор. Никакого отката, никаких попыток не пройденной дороги. Он шагает прямо от начала к концу, хватая лучше всего выглядящий вариант на каждой развилке.
Это вся идея, и именно поэтому жадный быстр и прост. Нет дерева рекурсии чтобы исследовать, нет таблицы подзадач чтобы заполнить. Ты сортируешь или сканируешь вход, делаешь лучший выбор, повторяешь.
Жадный против динамического программирования
Динамическое программирование из прошлого раздела и жадный атакуют один вид задачи — построение оптимального решения из выборов подзадач — но в противоположном духе:
- Динамическое программирование исследует все комбинации выборов подзадач, вычисляет лучшую каждой, и хранит общую лучшую. Оно подстраховывается: оно не фиксирует выбор пока не сравнит альтернативы.
- Жадный фиксирует один выбор на каждом шаге — локально лучший — и никогда не сравнивает его с альтернативами потом. Он ставит на то что локально лучший выбор это также часть глобально лучшего ответа.
Эта ставка и есть подвох. Когда ставка всегда срабатывает, жадный получает оптимальный ответ намного быстрее чем DP. Когда ставка может провалиться, жадный возвращает неверный (субоптимальный) ответ, тогда как DP всё ещё был бы прав.
Когда жадный корректен? Два условия
Жадный алгоритм даёт оптимальный ответ только когда задача обладает обоими этими свойствами:
- Свойство жадного выбора. Всегда существует глобально оптимальное решение которое начинается с локально лучшего выбора. Иначе говоря, жадный выбор никогда не загоняет тебя в угол — ты всегда можешь расширить его до оптимума.
- Оптимальная подструктура. После того как ты сделал этот первый выбор, остаток это уменьшенная версия той же задачи, и оптимальное решение целого содержит оптимальное решение этого остатка. (Динамическому программированию это свойство тоже нужно.)
Если любого из свойств нет, жадный может вернуть субоптимальный ответ. Опасность в том что жадный код всегда работает и всегда что-то возвращает — он просто тихо возвращает неверное. Так что ты должен доказать что жадный корректен для твоей задачи; ты не можешь это предполагать. Это доказательство — следующий урок.
Разобранный контрпример: размен монет
Чище всего ощутить разницу на размене наименьшим числом монет.
С канонической системой США 25 жадный работает. Чтобы набрать 30, бери самую большую монету которая помещается (25), потом повтори на оставшихся 5 (бери 5). Две монеты — оптимально.
Теперь переключись на странную систему монет 4 и набери 6. Жадный всё так же хватает самую большую монету которая помещается каждый раз:
Coins available: {1, 3, 4} Target: 6
Greedy:
take 4 -> remaining 2 (4 is the largest coin <= 6)
take 1 -> remaining 1 (no 3 or 4 fits in 2, take 1)
take 1 -> remaining 0
result: 4 + 1 + 1 = 3 coins
Optimal:
3 + 3 = 2 coinsЖадный взял локально лучшую монету (четвёрку) и застрял: четвёрка заблокировала ему использование двух троек. Оптимум вообще не использует четвёрку. Это ровно провал свойства жадного выбора — здесь локально лучший первый ход (взять 4) не часть никакого оптимального решения. Система 4 просто не обладает этим свойством, так что жадный неверен на ней. Канонические системы как 25 обладают им, так что жадный прав на них. Тот же алгоритм, другие монеты, противоположные исходы — именно поэтому корректность надо проверять, а не предполагать.
Жадный размен монет
Алгоритм короткий: отсортируй монеты от большей к меньшей, потом для каждой монеты бери столько сколько помещается перед переходом к следующей. Он фиксирует каждую монету и никогда не пересматривает.
1
function greedyChange(coins, amount) {
2
// Sort coins largest-first so we always try the biggest that fits
3
const sorted = [...coins].sort((a, b) => b - a);
4
let remaining = amount;
5
const picks = [];
6
// Walk coins from largest to smallest, never going back
7
for (const coin of sorted) {
8
// Take this coin as many times as it fits into the remainder
9
while (remaining >= coin) {
10
remaining -= coin;
11
picks.push(coin);
12
}
13
}
14
return picks; // the coins greedy chose (may not be optimal!)
15
}
- L3 Сортируй по убыванию чтобы первая монета которую мы пробуем на каждом шаге была локально лучшей (самой большой). Эта сортировка и делает всё O(n log n).
- L7 Сканируй монеты от большей к меньшей. Раз оставив монету позади, мы никогда к ней не возвращаемся — это часть 'никогда не пересматривай' жадного.
- L9 Жадная фиксация: хватай эту монету пока она ещё помещается, даже не взглянув на меньшие монеты.
- L13 Верни то что жадный выбрал. Для {1,3,4} суммы 6 это 3 монеты — субоптимально. Жадный всегда возвращает ЧТО-ТО; это что-то оптимально только когда задача обладает свойством жадного выбора.
Запуск: успех на канонических монетах, провал на 4
Смотри как та же функция выигрывает на системе США и проигрывает на 4. Код идентичен; меняется только набор монет.
На системе США жадный точно попадает в оптимум (63 нужно 6 монет, и жадный находит 6). На 4 та же самая логика возвращает 3 монеты когда хватило бы 2. Ничего не упало, ничего тебя не предупредило — жадный просто уверенно вернул худший ответ. Эта тишина и есть ровно причина почему жадное решение надо доказывать корректным для его конкретной области входов.
Давай протрассируем жадный на провальном случае — монеты {1, 3, 4}, сумма 6 — шаг за шагом, чтобы ты мог увидеть ровно где локально лучший выбор уводит его в сторону.
1
sorted = {4, 3, 1} // largest first
2
remaining = 6, picks = []
3
coin 4: while remaining >= 4 -> take 4
4
coin 3: 3 > remaining? skip
5
coin 1: while remaining >= 1 -> take 1
6
return picks
Время: O(n log n), обычно доминирует сортировка
Жадный алгоритм делает один проход по выборам, выполняя O(1) (или почти O(1)) работы на шаг, так что сам скан это O(n) для n элементов. Но большинство жадных алгоритмов сначала сортируют вход чтобы поставить локально лучший выбор впереди — самые большие монеты первыми, самые короткие работы первыми, самые ранние дедлайны первыми — и эта сортировка стоит O(n log n). Сортировка доминирует, так что заглавная стоимость это:
total time = O(n log n) (sort) + O(n) (greedy scan) = O(n log n)Пример с разменом монет даже дешевле потому что число номиналов монет крошечное и фиксированное (4 монеты для системы США), так что “n” которое сортируется это маленькая константа — но общий жадный шаблон это “сортируй, потом подметай”, и это O(n log n).
Почему жадный настолько быстрее чем DP
Скорость берётся целиком из неисследования альтернатив. Жадный фиксирует один выбор на шаг, так что он делает один линейный проход. Динамическое программирование, напротив, вычисляет много комбинаций выборов подзадач и хранит лучшую, так что оно платит за таблицу состояний.
what it does typical time
greedy take locally-best choice, no backtrack O(n log n)
dynamic prog explore all subproblem-choice combos O(states x work) often O(n*amount)Для размена монет с целевой суммой amount, DP который всегда корректен заполняет таблицу размера amount и это O(coins x amount). Жадный пропускает всё это. Так что когда жадный доказуемо корректен, ты меняешь O(coins x amount) у DP на почти O(n log n) у жадного — большой выигрыш. Цена этого выигрыша в том что жадный корректен только на задачах со свойством жадного выбора; иначе его скорость покупает тебе неверный ответ.
Вывод о стоимости
Жадный быстр потому что он неглубок: один проход, без сомнений. Когда бы ты ни тянулся к жадному, реальный вопрос никогда не “достаточно ли он быстр” (почти всегда да), а “корректен ли он для этой задачи” — это ровно то чему следующий урок учит тебя доказывать.
Какое единственное правило определяет жадный алгоритм?
Чем жадный отличается от динамического программирования на одном виде задачи?
Какими ДВУМЯ свойствами должна обладать задача чтобы жадный алгоритм был корректен?
Для монет {1, 3, 4} и суммы 6 жадный возвращает 4 + 1 + 1 = 3 монеты. Каково оптимальное число монет, и почему жадный его упускает?
Какова типичная временная сложность корректного жадного алгоритма, и почему?
Жадный код для задачи БЕЗ свойства жадного выбора будет:
Используя жадный на канонической системе США {1, 5, 10, 25}, сколько монет нужно чтобы набрать 30 центов (бери самую большую монету которая помещается, повторяй)?
Почему это работает
Зачем учить жадный если он может быть неверен? Потому что когда он корректен, он драматически проще и быстрее чем динамическое программирование — один проход вместо целой таблицы — и многие классические задачи (выбор активностей, кодирование Хаффмана, минимальные остовные деревья, дробный рюкзак, кратчайшие пути Дейкстры) построены на доказуемо корректных жадных выборах. Ценность жадного не в “используй его везде”; она в “распознай редкие задачи где локальный выбор доказуемо глобален, и эксплуатируй их ради огромного ускорения”. Подвох — знание какие это задачи — и есть то что делает навык доказательства (следующий урок) настоящим содержанием этого раздела.
Частая ошибка
Ошибка: предположение что жадный корректен потому что он “ощущается правильным” или проходит пару тестов. Жадный на 4 работает для многих сумм (от 1 до 5 в порядке) и проваливается лишь на конкретных целях вроде 6. Горстка проходящих примеров ничего не доказывает — жадный алгоритм корректен только если ты можешь доказать что свойство жадного выбора держится для каждого входа. Никогда не выпускай жадное решение на силе пары зелёных тестов; неверный ответ который он возвращает тихий и его легко пропустить.
Граничные случаи
Тот же жадный может быть прав на одном наборе входов и неверен на другом. Размен монет это учебниковый пример: жадный оптимален на канонической системе США 25, но субоптимален на 4. Корректность это свойство экземпляра задачи (здесь — номиналов монет), а не жадного кода. Так что “корректен ли жадный для размена монет?” не имеет единого ответа — ты должен спросить “корректен для какой системы монет?”. Является ли система монет “канонической” (безопасной для жадного) — это сам по себе вопрос требующий проверки.
Ещё практика
Чек-лист жадного. Перед использованием жадного алгоритма спроси: (1) Могу ли я сформулировать локально лучший выбор на каждом шаге? (2) Держится ли свойство жадного выбора — может ли каждый оптимум начинаться с этого выбора? (3) Держится ли оптимальная подструктура — является ли остаток меньшим экземпляром той же задачи? (4) Могу ли я доказать (2), или хотя бы не найти контрпример после упорных попыток? Если ты не можешь это доказать, либо найди контрпример (как 4 сумма 6) либо откатись к динамическому программированию, которое корректно без свойства жадного выбора. Скорость это дар жадного; корректность тебе надо заработать.
Объясни что это жадный алгоритм, чем он отличается от динамического программирования, два условия которые ему нужны для корректности, случай где он работает и где проваливается, и его типичную временную сложность.
Жадный алгоритм строит решение повторно делая локально лучший выбор и никогда не пересматривая его. Никакого отката, никакого исследования альтернатив — просто один прямой проход, хватая лучший вариант на каждом шаге.
Жадный против динамического программирования:
- DP исследует все комбинации выборов подзадач и хранит лучшую (оно подстраховывается).
- Жадный фиксирует один локальный выбор на шаг и никогда не сравнивает альтернативы потом (он ставит).
DP корректен шире; жадный быстрее, но корректен только когда его ставка всегда срабатывает.
Жадный корректен только с двумя свойствами:
- Свойство жадного выбора — глобально оптимальное решение всегда может начинаться с локально лучшего выбора.
- Оптимальная подструктура — оптимальное решение содержит оптимальные решения своих подзадач.
Если любое проваливается, жадный всё равно работает и всё равно возвращает что-то — просто тихо субоптимальное. Так что жадный надо доказывать корректным, никогда не предполагать.
Демонстрация на размене монет:
- Каноническая система США 25: жадный оптимален (30 = 25 + 5 = 2 монеты).
- Система 4, сумма 6: жадный даёт 4 + 1 + 1 = 3 монеты, но оптимум это 3 + 3 = 2 монеты. Свойство жадного выбора проваливается потому что локально лучший первый ход (взять 4) не в каком оптимальном решении.
Сложность: когда корректен, жадный обычно O(n log n) — доминирует начальная сортировка, потом один проход O(n) — намного дешевле таблицы DP.
Дальше: урок 02 показывает как доказать жадный алгоритм корректным (аргумент обмена), чтобы ты мог отличить случаи 25 от ловушек 4 до того как выпустишь.