Алчен, greedy алгоритъм - задача за плащане с най-малък брой монети
Съществуват няколко названия един особен подклас алгоритми на евристичните: жадни, алчни от англ. greedy.
Характерни особености на алчен алгоритъм:а) за всеки конкретен етап от решението на задачата се взема най-доброто за момента решение като се "надява", че по този начин ще се стигне до глобалния максимум, т.е. реално намира локалния екстремум;
б) не дава възможност за преразглеждане на вече взети решения - главното му отличие от динамичното оптимиране, където решението се взима на базата на всички възможни решения взети до момента;
в) един алчен алгоритъм извежда отговор много близък до оптималния и в повечето случаи е доста ефективен;
г) в общия случай всеки алчен алгоритъм е по-лесен за реализация (за разлика от динамично оптимиране).
Нека разгледаме следната задача илюстрираща работата на алчен алгоритъм:
В България стотинките са с номинална стойност 1, 2, 5, 10, 20 и 50
Да се състави програма, която по въведена сума [10..999] извежда, чрез функция, възможно най-малък брой монети/стотинки, с които може да се плати.
Входни данни: естествено число от интервала [10 .. 999].
Пример: 88 Изход:
50 стотинки - 1 бр.
20 стотинки - 1 бр.
10 стотинки - 1 бр.
5 стотинки - 1 бр.
2 стотинки - 1 бр.
1 стотинкa - 1 бр.
В този случай описваният алчен алгоритъм ще се стреми да ползва най-малък брой монети. Крайният резултат е стремеж за плащане с монети имащи възможно най-голяма номинална стойност.
Следващата примерна програма дава решена задача за алчен, greedy алгоритъм:
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.