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

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

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

Как это работает?

Алгоритм последовательно принимает решения, основываясь только на текущей информации. Например, в задаче о размене монет для суммы 11 с монетами 1, 2, 5 жадный алгоритм выберет 5, затем 5, затем 1 — итого 3 монеты, что оптимально. Однако для монет 1, 3, 4 и суммы 6 он выберет 4, 1, 1 (3 монеты), хотя оптимально 3 + 3 (2 монеты).

Пример кода на Python

def greedy_coin_change(coins, amount):
    coins.sort(reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

print(greedy_coin_change([1, 2, 5], 11))  # [5, 5, 1]

Где применяется?

• Алгоритм Дейкстры для поиска кратчайшего пути в графе.
• Задача о рюкзаке (дробная версия).
• Построение минимального остовного дерева (алгоритмы Прима и Краскала).
• Кодирование Хаффмана для сжатия данных.

Вывод

Жадные алгоритмы эффективны для задач, где локальный оптимум совпадает с глобальным, например, в задачах с оптимальной подструктурой. Их стоит применять, когда важна скорость и простота, но необходимо убедиться, что задача допускает такое решение.