Qənaətkar algoritm nədir və hansı hallarda tətbiq olunur?

Qənaət algoritmi — bu optimallaşdırma məsələlərini həll etmək üçün yanaşmadır və hər mərhələdə ən yaxşı yerli həll (hazırkı an üçün ən sərfəli variant) seçir və ümid edir ki, bu optimal yerli həllərin ardıcıllığı qlobal olaraq optimal həllə gətirib çıxaracaq. O, hazırkı seçimin gələcək mərhələlərə mümkün təsirlərini nəzərə almır.

Xüsusiyyətlər:

• Sadəlik: Adətən dinamik proqramlaşdırmadan və ya digər optimallaşdırma metodlarından daha asan həyata keçirilir.
• Sürət: Tez-tez daha aşağı hesablama mürəkkəbliyinə malikdir.
• Optimalik zəmanəti: Hər zaman qlobal olaraq ən yaxşı həll tapdığını zəmanət etmir. Zəmanət yalnız müəyyən sinif məsələlər üçün keçərlidir.

Bu, hər mərhələdə yerli olaraq ən yaxşı seçimin qlobal olaraq ən yaxşı həllə gətirdiyi sübut olunmuş məsələlərdə tətbiq edilir. Nümunələr:

• Fəaliyyətlərin seçimi problemi: Vaxt baxımından üst-üstə düşməyən ən çox fəaliyyətin seçilməsi.
• Sırt çantası problemi (obyektlərin fraksionlaşdırılması ilə): Əgər obyektlər bölünə bilərsə. Əks halda, bu dinamik proqramlaşdırma problemdir.
• Prim və Kruskal alqoritmləri: Qrafda minimal yayılma ağacını tapmaq üçün.
• Dijkstra alqoritmi: Qrafda mənfi olmayan kənar çəkiləri ilə ən qısa yolu tapmaq üçün.
• Huffman kodlaşdırması: Optimal prefiks kodu qurmaq üçün.

Fəaliyyətlərin seçimi alqoritmi üçün pseudokod nümunəsi:

Funksiya SeçFəaliyyətləri(fəaliyyətlər):
  Fəaliyyətləri bitmə vaxtına görə sırala
  seçilmiş_fəaliyyətlər = boş siyahı
  son_bitmə_vaxtı = 0

  Hər bir fəaliyyət üçün:
    Əgər fəaliyyət.başlama_vaxtı >= son_bitmə_vaxtı:
      Fəaliyyəti seçilmişlərə əlavə et
      son_bitmə_vaxtı = fəaliyyət.bitmə_vaxtı

  Geri qaytar seçilmiş_fəaliyyətlər

Qənaət algoritminin konkret bir məsələyə tətbiq oluna biləcəyini yoxlamaq vacibdir, çünki əks halda o, suboptimum həll verə bilər.