Šta je žedni algoritam i u kojim slučajevima se primenjuje?

Жадни алгоритам је приступ решавању оптимизационих задатака који _на сваки корак бира најбоље локално решење (најисплативију варијанту у датом тренутку) у нади да ће ова секвенца оптималних локалних решења довести до глобално оптималног решења. Он не разматра могуће последице тренутног избора на будуће кораке.

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

• Једноставност: Обично је лакше реализовати него динамичко програмирање или друге методе оптимизације.
• Брзина: Често има мању рачунску сложеност.
• Гаранција оптималности: Не увек гарантује проналажење глобално оптималног решења. Гаранција важи само за одређене класе задатака.

Користи се у задацима где је доказано да локално оптималан избор у сваком кораку доводи до глобално оптималног решења. Примери:

• Задача о избору активности (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).

# Овај пример показује да жадни алгоритам не увек доводи до глобалног оптимума,
# ако својства задатка не одговарају његовој применљивости (на пример,
# стандардни номинали валута често омогућавају жадни алгоритам,
# али произвољни номинали - не).