Жадный алгоритм: где локальная оптимальность становится ловушкой

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

---

Где жадный алгоритм ломается

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

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

Это называется неканонической монетной системой. Не NP. Просто не тот инструмент.

---

Концептуальная ошибка, которую повторяют везде

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

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

Разница принципиальная:

— Неканоническая монетная система: жадный не подходит → возьми динамическое программирование → задача решена точно и быстро.

— NP-задача: жадный не подходит → динамическое программирование не поможет → точное решение за разумное время неизвестно.

Это не один класс. Это два разных мира.

---

Почему это важно для понимания пределов алгоритмов

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

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

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

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

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