Acgöz alqoritm

Acgöz alqoritm (ing.greedy algorithm, ru.жадный алгоритм) — hər bir mərhələdə lokal optimal qərarlar (həllər) qəbul edən və son həllin də optimal olacağı gümanına əsaslanan alqoritm.

Acgöz alqoritm vasitəsilə yalnız {1, 5, 10, 20} dəyərli qəpiklərdən istifadə etməklə 36 məbləğinin alınması)

Məsələ

• Hər hansı dövlərin pul sistemi dəyəri a1 = 1 < a2 < … < an olan qəpiklərdən ibarətdir. S məbləğini mümkün qədər az sayda qəpiklə vermək tələb olunur.

Bu məsələnin həllinin acgöz alqoritmi belə olacaq. Dəyəri an olan qəpiklərdən maksimal mümkün olan sayda götürülür: xn = S/an. Eyni qayda ilə kiçik nominallı neçə qəpik lazım olduğu müəyyən olunur və proses belə davam etdirilir. Bu məsələ üçün acgöz alqoritm həmişə optimal həlli vermir. Məsələn, 1, 5 və 7 qəpik vasitəsilə 24 məbləğini acgöz alqoritm belə xırdalayar: 7 qəp. – 3 ədəd, 1 qəp. – 3 ədəd. Ancaq düzgün həll başqadır: 7 qəp. – 2 ədəd, 5 qəp. – 2 ədəd. Buna baxmayaraq, bütün gerçək pul sistemlərində acgöz alqoritm düzgün həlli verir. Buna səbəb istənilən iki kiçik nominalın cəmi həmişə böyük nominaldan kiçikdir və ya bərabərdir: Nomi-2 + Nomi-1 < Nomi.

Ədəbiyyat

• İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 996 s.

İstinadlar