Жадные алгоритмы — это разновидность алгоритмов, которые на каждом шаге принимают локально оптимальное решение в надежде, что это приведет к глобально оптимальному решению.
Ключевые особенности:
- Локальный оптимум: На каждом шаге выбирается решение, которое кажется наилучшим в данный момент, без учета будущих последствий.
- Отсутствие обратного хода: Принятые решения не могут быть пересмотрены на более поздних этапах.
- Эффективность: Часто просты в реализации и имеют較高的 эффективность по сравнению с более сложными методами.
Примеры задач, для которых подходят жадные алгоритмы:
- Задача о сдаче (размен монет)
- Задача о выборе заявок (Interval Scheduling)
- Некоторые задачи о минимальном остовном дереве (например, алгоритм Прима или Краскала)
Пример жадного подхода к задаче о сдаче (размен 100 рублей монетами 50, 10, 5, 1):
- Взять максимально возможное количество монет 50 рублей (2 * 50 = 100).
- Остаток: 0. Решение найдено.
Пример, когда жадный алгоритм не дает оптимального решения (размен 82 рублей монетами 50, 25, 10):
Жадный подход:
- 1 * 50 = 50. Остаток: 32.
- 1 * 25 = 25. Остаток: 7.
- 0 * 10 = 0. Остаток: 7.
Решение: 1 монета 50р, 1 монета 25р, 0 монет 10р (неполноценный размен)
Оптимальный подход:
- 0 * 50 = 0. Остаток: 82.
- 3 * 25 = 75. Остаток: 7.
- 0 * 10 = 0. Остаток: 7.
Решение: 3 монеты 25р (неполноценный размен)
В данном случае最优解可能存在, но жадный алгоритм его не находит.
Жадные алгоритмы работают корректно только для жадных задач, обладающих свойствами:
- Свойство оптимальной подструктуры: Опитимальное решение задачи содержит в себе оптимальные решения подзадач.
- Свойство жадного выбора: Локально оптимальный выбор на каждом шаге приводит к глобально оптимальному решению.
python