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

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

Применение:

1. Задача о выборе деятельности (Activity Selection Problem):

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

   # Пример Activity Selection
   # activities = [(start_time, end_time)]
   
   activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
   activities.sort(key=lambda x: x[1]) # Сортируем по времени окончания
   
   selected_activities = []
   last_finish_time = -1
   
   for activity in activities:
       if activity[0] >= last_finish_time:
           selected_activities.append(activity)
           last_finish_time = activity[1]
   
   print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]
   

2. Задача о сдаче мелочи (Coin Change Problem) для канонических наборов монет:

   • Задача: Выдать заданную сумму минимальным количеством монет.
   • Жадное решение: Использовать максимально возможное количество самых больших номиналов монет, пока сумма не будет выдана. Работает только для определенных наборов монет (например, 1, 5, 10, 25).

   # Пример Coin Change (для канонических монет)
   coins = [25, 10, 5, 1]
   amount = 67
   result = {}
   
   for coin in coins:
       while amount >= coin:
           result[coin] = result.get(coin, 0) + 1
           amount -= coin
   
   print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
   

3. Алгоритм Краскала для нахождения минимального остовного дерева (Minimum Spanning Tree):

   • Задача: Найти подмножество ребер связного взвешенного неориентированного графа, соединяющее все вершины с минимальным суммарным весом ребер.
   • Жадное решение: Сортировать все ребра по весу в порядке возрастания. Последовательно добавлять ребра, если они не образуют цикл с уже выбранными ребрами, пока не будет соединено n-1 ребро (где n — количество вершин).

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