Жадные алгоритмы

Жадные алгоритмы строят решение итеративно, многократно выбирая наилучший вариант на текущем шаге, и являются корректными именно тогда, когда такие локально оптимальные выборы доказуемо приводят к глобально оптимальному решению.

Definition

Жадный алгоритм строит решение посредством последовательности выборов, каждый из которых направлен на оптимизацию некоторого локального критерия, никогда не возвращаясь к ранее сделанным выборам; он корректен только тогда, когда локально оптимальные выборы приводят к глобально оптимальному результату.

Scope

Эта тема охватывает жадную парадигму: свойство жадного выбора и оптимальную подструктуру, которые её обосновывают, стандартные методы доказательства (аргументы обмена и матроидный подход), а также канонические жадные алгоритмы, включая кодирование Хаффмана, минимальные остовные деревья (Крускал и Прим), алгоритм Дейкстры для кратчайших путей и интервальное планирование. Также рассматриваются случаи, когда жадные стратегии служат лишь аппроксимационными эвристиками, а не точными методами.

Core questions

• Что такое свойство жадного выбора и как оно доказывается для данной задачи?
• Как аргумент обмена показывает, что жадный выбор безопасен?
• Какие задачи имеют матроидную структуру, гарантирующую жадную оптимальность?
• Когда жадный метод является лишь аппроксимацией, а не точным алгоритмом?
• Как жадный алгоритм соотносится с динамическим программированием для одной и той же задачи?

Key concepts

• свойство жадного выбора
• оптимальная подструктура
• аргумент обмена
• матроиды
• кодирование Хаффмана
• минимальное остовное дерево
• интервальное планирование
• дробный рюкзак

Key theories

Свойство жадного выбора и аргументы обмена

Задача допускает жадное решение, когда глобально оптимальное решение всегда может быть модифицировано таким образом, чтобы оно соответствовало жадному первому выбору без потери оптимальности; аргументы обмена (или «жадный всегда впереди») формализуют это.

Матроиды и жадная оптимальность

Когда допустимые решения образуют независимые множества взвешенного матроида, жадный алгоритм всегда находит независимое множество максимального веса; это объединяет такие результаты, как оптимальность алгоритма Крускала для минимального остовного дерева.

Clinical relevance

Жадные алгоритмы лежат в основе широко используемых систем: кодирование Хаффмана в форматах сжатия данных, алгоритмы минимального остовного дерева в проектировании сетей, алгоритм Дейкстры в маршрутизации и навигации, а также жадные эвристики планирования и покрытия множеств в операционных системах и распределении ресурсов.

History

Жадные рассуждения встречаются в классических результатах, таких как алгоритмы минимального остовного дерева Крускала (1956) и Прима (1957), оптимальные префиксные коды Хаффмана (1952) и алгоритм кратчайшего пути Дейкстры (1959). Матроидно-теоретическое объяснение того, когда жадные методы успешны, было разработано Эдмондсом и другими в 1960-х и 1970-х годах.

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

Почему жадный алгоритм работает для задачи о дробном рюкзаке, но не для задачи о рюкзаке 0/1?

В задаче о дробном рюкзаке предметы могут быть разделены, поэтому выбор предмета с наибольшей ценностью на единицу веса всегда безопасен и доказуемо оптимален. В задаче о рюкзаке 0/1 предметы неделимы, жадный выбор может исключить лучшую комбинацию, и для точного оптимума требуется динамическое программирование.

Как доказать корректность жадного алгоритма?

Двумя стандартными методами являются аргумент обмена, который преобразует любое оптимальное решение в жадное без ухудшения, и аргумент «жадный всегда впереди», который показывает, что жадное частичное решение не хуже любого другого на каждом шаге. Теория матроидов предоставляет общее достаточное условие.