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

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

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

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

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

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

4.1.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Глава 4 Жадные алгоритмы:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Глава 8. Глава государства в зарубежных странах
  13. Глава рода
  14. Глава рода
  15. Глава 1
  16. Глава 2