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

Разбираем подход, который на каждом шаге хватает самое выгодное прямо сейчас.

Сдача монетами

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

Где жадность выигрывает

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

Где жадность ошибается

Но жадность близорука. Иногда выгодный сейчас шаг закрывает путь к лучшему решению потом. На некоторых наборах монет жадный алгоритм даёт не минимальное число монет. В таких случаях нужны другие подходы, которые заглядывают вперёд. Умение распознать, когда жадность подводит, — признак зрелого мышления.

Частые вопросы

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

С чего начать изучение алгоритмов? С наглядных пошаговых задач. В игре Дрон Кодер легко проверять, приводит ли выбранная стратегия к цели.