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

В культовом фильме 1980-х годов «Уолл-стрит» Майкл Дуглас встает перед залом, заполненным акционерами, и провозглашает: «Жадность… это хорошо. Жадность — это правильно. Жадность работает».

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

Мы постараемся рассмотреть нескольких вычислительных задач через призму одних и тех же вопросов: жадность — это действительно хорошо? Жадность действительно работает?

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

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

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

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

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

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

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

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

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

Также будут исследованы интересные отношения между минимальными остовными деревьями и давно изучавшейся задачей кластеризации. Напоследок будет рассмотрен более сложный пример — задача ориентированного дерева минимальной стоимости, которая расширит наши представления о жадных алгоритмах.