Жадный алгоритм строит решение задачи, делая локально оптимальный выбор на каждом шаге в надежде, что этот выбор приведет к глобально оптимальному решению. Он не "смотрит вперед" или "назад", а принимает решение, которое кажется лучшим в данный момент без учета последствий. Примеры:
- Задача о сдаче: Выдать минимальное количество монет для определенной суммы. Жадный алгоритм выбирает самую крупную монету, которая не превышает оставшуюся сумму.
- Алгоритм Дейкстры: Находит кратчайшие пути от одной вершины графа до всех остальных с неотрицательными весами ребер. На каждом шаге выбирает вершину с наименьшим текущим расстоянием.
Жадные алгоритмы не всегда дают оптимальное решение для всех задач, но во многих случаях они просты в реализации и эффективны по времени. Для доказательства оптимальности жадного алгоритма обычно используются два свойства:
- Свойство жадного выбора: Локально оптимальный выбор, сделанный жадным алгоритмом, может быть частью оптимального решения.
- Свойство оптимальной подструктуры: Оптимальное решение задачи содержит оптимальные решения подзадач.
python