რა არის ხარბი ალგორითმი და რა შემთხვევებში გამოიყენება?

Ճարպային ալգորիթմը՝ դա օպտիմալացման խնդիրների լուծման մոտեցում է, որը յուր քայլում ընտրում է լավագույն տեղական լուծումը (ներկայիս պահի ամենաարդյունավետ տարբերակը) հույսով, որ այս օպտիմալ տեղական լուծումների հաջորդականությունը կհանգեցնի գլոբալապես օպտիմալ լուծման: Նա չի հաշվի առնում ներկայիս ընտրության հնարավոր հետևանքները ապագա քայլերի վրա:

Նկարագրություններ:

• Հեշտություն: Հաճախ ավելի հեշտ է իրականացնել, քան դինամիկ ծրագրավորումը կամ այլ օպտիմալացման մեթոդները:
• Արագություն: Սովորաբար ունի ցածր հաշվարկային բարդություն:
• Օպտիմալության երաշխիք: Չի երաշխավորում միշտ գլոբալապես օպտիմալ լուծում գտնել:

Կիրառվում է այն խնդիրներում, որտեղ ապացուցված է, որ յուրաքանչյուր քայլում տեղական օպտիմալ ընտրությունը հանգեցնում է գլոբալապես օպտիմալ լուծման:

• Գործունեությունների ընտրության խնդիր (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).

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