Какво е жаден алгоритъм и в кои случаи се прилага…

Жадният алгоритъм е подход към решаването на оптимизационни задачи, който _на всеки етап избира най-доброто локално решение (най-изгодният към текущия момент вариант) в надеждата, че тази последователност от оптимални локални решения ще доведе до глобално оптимално решение. Той не разглежда възможните последици от текущия избор върху бъдещите стъпки.

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

Простота: Обикновено по-лесен за реализиране отколкото динамично програмиране или други методи за оптимизация.
Скорост: Често има по-ниска изчислителна сложност.
Гаранция за оптималност: Не винаги гарантира намирането на глобално оптимално решение. Гаранцията важи само за определени класове задачи.

Използва се при задачи, при които е доказано, че локално оптималният избор на всеки етап води до глобално оптимално решение. Примери:

Задача за избор на дейности (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).

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

Какво е жаден алгоритъм и в кои случаи се прилага?