14. Жадные алгоритмы: сжатие, кэширование, остовные деревья
Жадные алгоритмы — один из фундаментальных методов алгоритмического проектирования. В отличие от динамического программирования, они не рассматривают все возможные комбинации, а принимают решения локально, шаг за шагом.
В этом разделе мы изучим:
- Алгоритм Хаффмана и оптимальное кэширование — два классических примера жадных алгоритмов с доказательством оптимальности через обменный аргумент
- Минимальное остовное дерево — алгоритмы Прима и Краскала, лемма о разрезе, структура данных DSU
Определение
Жадный алгоритм (greedy algorithm) — алгоритм, который на каждом шаге принимает локально оптимальное решение, не возвращаясь к уже сделанному выбору. Жадность корректна, когда локальные оптимумы ведут к глобальному оптимуму.
Свойства
Обменный аргумент (exchange argument) — стандартная техника доказательства корректности жадных алгоритмов:
- Предположим, что существует оптимальное решение, отличающееся от жадного.
- Найдём первое место, где они расходятся, и «обменяем» выбор оптимального решения на жадный.
- Покажем, что после обмена решение не стало хуже.
- Повторяя обмены, превратим оптимальное решение в жадное — значит, жадное тоже оптимально.
Все четыре алгоритма раздела следуют именно этой схеме.
Сводка алгоритмов
| Алгоритм | Задача | Жадный выбор | Время работы |
|---|---|---|---|
| Хаффман | Оптимальное префиксное кодирование | Слияние двух редчайших символов | $O(\lvert\Sigma\rvert \log \lvert\Sigma\rvert)$ |
| Белади | Минимум кэш-промахов | Вытеснение элемента с наибольшим временем до следующего запроса | $O(m \log k)$ |
| Прима | Минимальный остов | Минимальное ребро через разрез $(A, V \setminus A)$ | $O((V+E)\log V)$ |
| Краскала | Минимальный остов | Минимальное ребро, не образующее цикла | $O(E \log V)$ |
- 14.1. Алгоритм Хаффмана и оптимальное кэширование
- 14.2. Минимальное остовное дерево {class=“children children-type-tree children-sort-”}