Жадный алгоритм — это подход к решению оптимизационных задач, который на каждом шаге выбирает наилучшее локальное решение (наиболее выгодный с точки зрения текущего момента вариант) в надежде, что эта последовательность оптимальных локальных решений приведет к глобально оптимальному решению. Он не рассматривает возможные последствия текущего выбора на будущие шаги.
Характеристики:
- Простота: Обычно проще реализовать, чем динамическое программирование или другие методы оптимизации.
- Скорость: Часто имеют меньшую вычислительную сложность.
- Гарантия оптимальности: Не всегда гарантируют нахождение глобально оптимального решения. Гарантия есть только для определенных классов задач.
Применяется в задачах, где доказано, что локально оптимальный выбор на каждом шаге приводит к глобально оптимальному решению. Примеры:
- Задача о выборе заявок (Activity Selection Problem): Выбор максимального количества непересекающихся по времени активностей.
- Задача о рюкзаке (при дробимости предметов): Когда предметы можно делить. Если нет, то это задача динамического программирования.
- Алгоритм Прима и Крускала: Для поиска минимального остовного дерева в графе.
- Алгоритм Дейкстры: Для поиска кратчайшего пути в графе с неотрицательными весами ребер.
- Кодирование Хаффмана: Для построения оптимального префиксного кода.
Пример псевдокода для алгоритма выбора заявок:
pseudocode
Важно проверить, применим ли жадный алгоритм для конкретной задачи, так как иначе он может дать субоптимальное решение.
python