Жадный алгоритм: где локальная оптимальность становится ловушкой
Жадный алгоритм — один из самых элегантных инструментов в computer science. Принцип прост: на каждом шаге выбирай лучшее из доступного прямо сейчас, не оглядываясь назад. Никакого перебора, никакой памяти о прошлых решениях. Если задача устроена правильно — получаешь глобальный оптимум почти бесплатно. Но в большинстве реальных задач мир устроен иначе. Где жадный алгоритм ломается Классический пример — размен монет. Монеты достоинством 1, 5 и 7. Нужно разменять 24. Жадный алгоритм берёт максимально возможное количество самых крупных купюр: три семёрки (21) и три единицы (3). Итого шесть монет. Оптимальное решение — две семёрки и две пятёрки. Четыре монеты. Жадный алгоритм ошибся. Но здесь важно то, что обычно остаётся за кадром: оптимальное решение существует и находится — динамическим программированием — за полиномиальное время. Задача решаема. Просто жадный подход для неё не подходит. Это называется неканонической монетной системой. Не NP. Просто не тот инструмент. Концептуал...