Ի՞նչ է գրէդի ալգորիթմը և ինչ դեպքերում է այն կիրառվում:

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

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

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

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

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

# Այս օրինակն ցույց է տալիս, որ ճարպային ալգորիթմը միշտ չի հանգեցնում գլոբալ օպտիմումի,
# եթե խնդիրների հատկությունները չեն համապատասխանում նրա կիրառելիությանը: