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