Что такое жадный алгоритм и когда он подводит
Жадный алгоритм всегда хватает то, что прямо сейчас выглядит выгоднее всего. Иногда это гениально просто, а иногда заводит прямо в тупик. Разбираемся, когда жадности можно доверять, а когда она тебя подведёт.
Представь, что ты идёшь по лабиринту и на каждой развилке выбираешь тот проход, который кажется самым широким и светлым. Звучит разумно? А теперь представь, что именно эта привычка хвататься за лучшее прямо сейчас привела тебя в тупик. Вот это и есть жадный алгоритм со всеми его сильными и слабыми сторонами.
Жадность как стратегия
Жадный алгоритм — это способ решать задачу, при котором на каждом шаге ты делаешь выбор, который выглядит лучшим в данный момент, и никогда не пересматриваешь его потом. Никаких сомнений, никакого «а вдруг другой путь был бы выгоднее». Схватил самое вкусное — и пошёл дальше.
Звучит почти как лень, но на самом деле это очень мощная идея. Жадные алгоритмы обычно простые, быстрые и не требуют хранить кучу вариантов в памяти. Ты просто двигаешься вперёд, шаг за шагом принимая локально оптимальное решение.
Классический пример — выдача сдачи. Допустим, ты кассир и тебе нужно выдать 87 рублей монетами номиналом 50, 10, 5, 2 и 1. Что ты сделаешь? Возьмёшь самую крупную монету, которая ещё помещается: сначала 50, потом 10, ещё 10, потом 5, потом 2. Итого пять монет — и ты ни разу не задумался о других комбинациях. Это чистая жадность в действии.
Где жадность работает блестяще
Жадный подход не зря так любят. В целом ряде задач он даёт не просто хороший, а математически наилучший ответ — и при этом работает очень быстро.
- Сдача монетами. Для привычных нам наборов номиналов жадность всегда выдаёт минимальное число монет.
- Планирование дел по дедлайнам. Если у тебя куча задач и нужно успеть как можно больше, часто помогает простое правило: бери ту, что заканчивается раньше всех.
- Прокладка дешёвых сетей. Когда нужно соединить города дорогами с минимальными затратами, алгоритмы вроде Прима и Краскала на каждом шаге жадно выбирают самое дешёвое подходящее ребро — и приходят к идеальному результату.
Секрет в том, что у этих задач есть особое свойство: цепочка локально лучших выборов складывается в глобально лучший ответ. Математики называют такие задачи обладающими свойством жадного выбора. Если оно есть — жадность не просто удобна, она доказуемо права.
Жадный алгоритм — это спортсмен, который бежит изо всех сил на каждом метре, ни разу не оглядываясь. Иногда это и есть путь к победе. А иногда — прямой путь сойти с дистанции.
А теперь — как она подводит
Беда в том, что жадность близорука. Она видит только следующий шаг и совершенно не думает о том, что будет дальше. И есть задачи, где сиюминутная выгода оборачивается общим проигрышем.
Вернёмся к сдаче, но поменяем монеты. Пусть у нас есть номиналы 1, 3 и 4, и надо набрать сумму 6. Жадный кассир хватает самую крупную монету — 4. Остаётся 2, которые он добирает двумя монетами по 1. Итого три монеты: 4 + 1 + 1. А ведь можно было взять 3 + 3 — и обойтись всего двумя! Жадность схватила вкусную четвёрку в начале и из-за этого проиграла.
Ещё нагляднее — задача о рюкзаке, где можно класть только целые предметы. Представь, что у тебя рюкзак на 10 килограммов и три вещи: одна весит 6 кг и стоит 6 монет, две другие — по 5 кг и по 5 монет каждая. Жадность, которая хватает самую дорогую вещь первой, возьмёт шестёрку. После этого останется место всего на 4 кг — и больше ничего не влезает, итог 6 монет. А если бы ты отказался от соблазнительной первой вещи и взял две по пять, получилось бы 10 монет. Жадный выбор в начале закрыл дорогу к лучшему решению.
Откуда вообще берётся ловушка
Главная причина провалов в том, что жадный алгоритм никогда не отменяет свои решения. Сделал выбор — забыл о других вариантах навсегда. Если правильный ответ требует когда-то пожертвовать сиюминутной выгодой ради будущего, жадность этого просто не умеет.
Это очень похоже на жизнь. Иногда выгоднее не съесть конфету прямо сейчас, а потерпеть и получить целую пачку завтра. Иногда выгоднее не идти в самый широкий проход лабиринта, потому что он ведёт в тупик. Умение жертвовать малым ради большего — как раз то, чего жадному алгоритму катастрофически не хватает.
Для таких «коварных» задач придумали другие инструменты. Динамическое программирование аккуратно перебирает и запоминает промежуточные результаты, чтобы потом собрать из них действительно лучший ответ. Перебор с возвратом (бэктрекинг) умеет откатываться назад и пробовать другую ветку, если зашёл в тупик. Они медленнее и сложнее жадности, зато не попадаются в её ловушки.
Как понять, можно ли жадничать
Значит ли всё это, что жадность — плохая идея? Вовсе нет. Это один из самых элегантных приёмов в программировании, просто пользоваться им надо с умом.
Прежде чем доверить задачу жадному алгоритму, стоит задать себе пару вопросов:
- Правда ли, что лучший выбор на каждом шаге складывается в лучший ответ в целом? Это нужно доказать, а не понадеяться.
- Можно ли придумать пример, где жадность ошибётся? Если придумывается — значит, она тут не подходит.
Хорошая привычка — проверять жадное решение на маленьких хитрых примерах, особенно на тех, где «очевидный» выбор в начале выглядит слишком уж заманчиво. Если на всех каверзных случаях ответ совпадает с правильным и ты понимаешь почему — поздравляю, жадность здесь твой друг.
А в следующий раз, когда будешь хвататься за самое выгодное прямо сейчас — в коде или в жизни — вспомни про лабиринт с самым широким проходом. Иногда быстрый путь оказывается самым длинным.