Алгоритмы
Жадные алгоритмы
Цели урока
- Понять парадигму жадных алгоритмов
- Знать условия корректности
- Решать классические задачи
- Отличать Greedy от DP
Предварительные знания
- MST (примеры жадности)
Жадность - один из семи смертных грехов. Но в алгоритмах жадность иногда приводит к идеальному результату! Dijkstra, Huffman, Prim - все они жадные.
- Сжатие данных (Huffman, LZW)
- Планирование задач
- Маршрутизация (Dijkstra)
- Сетевые протоколы (MST)
От кодов Хаффмана к теории матроидов
Жадные алгоритмы существовали задолго до того, как объяснили, почему они работают. В 1952 году Дэвид Хаффман, аспирант MIT, получил выбор между финальным экзаменом и курсовой работой об оптимальных префиксных кодах. Он выбрал работу и нашёл оптимальную жадную конструкцию, которую теперь называют кодированием Хаффмана. Она оказалась лучше метода, которым пользовался его собственный профессор Роберт Фано. Джозеф Краскал (1956) и Роберт Прим (1957) предложили жадные алгоритмы для минимального остовного дерева. Главный вопрос был в том, когда жадный выбор гарантированно даёт оптимум. Ответ пришёл из теории матроидов: в 1971 году Джек Эдмондс доказал, что жадный алгоритм находит оптимум ровно тогда, когда структура задачи образует матроид. Этот результат превратил жадность из удачной эвристики в парадигму с точным условием корректности.
Идея: локальный оптимум
**Жадный алгоритм** на каждом шаге делает локально оптимальный выбор, надеясь прийти к глобальному оптимуму.
**Жадность не всегда работает!** Для монет [1, 3, 4] и суммы 6: жадно 4+1+1=3 монеты, но оптимально 3+3=2 монеты.
**Когда жадность работает:**
- **Жадный выбор:** оптимальное решение включает жадный выбор
- **Оптимальная подструктура:** после выбора остаётся подзадача той же формы
- **Нет «отката»:** выбор нельзя пересмотреть позже
Монеты [1, 5, 6], сумма 10. Жадный даст:
Доказательство корректности
**Два способа доказать, что жадность работает:**
**Пример: Activity Selection (выбор мероприятий)**
**Если не можете доказать - возможно, жадность не работает!** Всегда ищите контрпример.
Для Activity Selection почему нельзя брать интервал с минимальным START?
Классические примеры
**1. Activity Selection (интервальное планирование):**
**2. Fractional Knapsack (дробный рюкзак):**
**3. Huffman Coding:**
| Задача | Жадная стратегия | Сложность |
|---|---|---|
| Activity Selection | Min end time | O(n log n) |
| Fractional Knapsack | Max value/weight | O(n log n) |
| Huffman Coding | Min frequency merge | O(n log n) |
| Dijkstra | Min distance vertex | O((V+E) log V) |
| Prim/Kruskal MST | Min edge weight | O(E log E) |
0/1 Knapsack (нельзя дробить) - жадность работает?
Greedy vs Dynamic Programming
| Greedy | DP | |
|---|---|---|
| Подход | Локально оптимальный выбор | Все подзадачи |
| Доказательство | Exchange / Stays Ahead | Оптимальная подструктура |
| Сложность | Обычно O(n log n) | Обычно O(n²) или O(n×W) |
| Coin Change (стандарт) | ✓ Работает | Не нужно |
| Coin Change (любые) | ✗ Не работает | ✓ Нужно |
| 0/1 Knapsack | ✗ Не работает | ✓ Нужно |
| Fractional Knapsack | ✓ Работает | Избыточно |
**Когда подозревать, что нужен DP:**
- «Минимальное число операций»
- «Сколько способов»
- «0/1 выбор» (брать или нет)
- «Оптимальное разбиение»
«Минимум прыжков, чтобы дойти до конца массива» - это:
Greedy алгоритмы
- Локально оптимальный выбор → глобальный (иногда)
- Нужно доказательство корректности!
- Exchange Argument / Stays Ahead
- Обычно быстрее DP
- Если можно дробить - вероятно Greedy
Связанные темы
Greedy - часто альтернатива DP.
- Dynamic Programming — Когда Greedy не работает
- MST — Kruskal и Prim - жадные
- Dijkstra — Жадный выбор ближайшего
Связанные уроки
- alg-17-mst — Жадные выборы в MST мотивируют жадную парадигму
- alg-14-dijkstra — Дейкстра жадно берёт ближайшую вершину фронта
- alg-21-dp — Когда жадность не работает, ДП гарантирует глобальный оптимум
- mm-04-second-order
- ml-31-transformers