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

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

---

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

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

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

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

---

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

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

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

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

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

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

---

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

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

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

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

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

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