Что такое жадный алгоритм и в каких случаях он применяется?

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

Характеристики:

• Простота: Обычно проще реализовать, чем динамическое программирование или другие методы оптимизации.
• Скорость: Часто имеют меньшую вычислительную сложность.
• Гарантия оптимальности: Не всегда гарантируют нахождение глобально оптимального решения. Гарантия есть только для определенных классов задач.

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

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

Пример псевдокода для алгоритма выбора заявок:

Function SelectActivities(activities):
  Sort activities by finish time
  selected_activities = empty list
  last_finish_time = 0

  For each activity in activities:
    If activity.start_time >= last_finish_time:
      Add activity to selected_activities
      last_finish_time = activity.finish_time

  Return selected_activities

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

# Простой пример задачи, где жадный алгоритм не оптимален
# Задача о сдаче: выдать наименьшее количество монет
# Доступные монеты: [1, 5, 10, 25] USD
# Выдать: например, 30 центов

# Жадный алгоритм:
#  Берем наибольшую монету <= 30 (25) -> остаток 5
#  Берем наибольшую монету <= 5 (5) -> остаток 0
#  Результат: 2 монеты (25 + 5). Оптимально здесь.

# Доступные монеты: [1, 6, 10]
# Выдать: 12 центов

# Жадный алгоритм:
#  Берем наибольшую монету <= 12 (10) -> остаток 2
#  Берем наибольшую монету <= 2 (1) -> остаток 1
#  Берем наибольшую монету <= 1 (1) -> остаток 0
#  Результат: 3 монеты (10 + 1 + 1).
#  Оптимальное решение: 2 монеты (6 + 6).

# Этот пример показывает, что жадный алгоритм не всегда приводит к глобальному оптимуму,
# если свойства задачи не соответствуют его применимости (например,
# стандартные номиналы валют часто позволяют жадный алгоритм,
# но произвольные номиналы - нет).