Что такое жадные алгоритмы?

Жадный алгоритм строит решение задачи, делая локально оптимальный выбор на каждом шаге в надежде, что этот выбор приведет к глобально оптимальному решению. Он не "смотрит вперед" или "назад", а принимает решение, которое кажется лучшим в данный момент без учета последствий. Примеры:

• Задача о сдаче: Выдать минимальное количество монет для определенной суммы. Жадный алгоритм выбирает самую крупную монету, которая не превышает оставшуюся сумму.
• Алгоритм Дейкстры: Находит кратчайшие пути от одной вершины графа до всех остальных с неотрицательными весами ребер. На каждом шаге выбирает вершину с наименьшим текущим расстоянием.

Жадные алгоритмы не всегда дают оптимальное решение для всех задач, но во многих случаях они прос