Похлепни алгоритам одређује минимални број новчића, потребних да би се вратио кусур. Ово су кораци које би човек спровео како би емулирао похлепни алгоритам. Похлепност се огледа у бирању прво новчића највеће вредности.
Похлепни алгоритам је алгоритам који користи метахеуристику за решавање проблема, такву да у сваком понављању поступка бира локално најбоље решење, у нади да ће тако коначно изнаћи глобални оптимум.
На пример, примена стратегије похлепног алгоритма на Проблем трговачког путника даје следећи алгоритам: У сваком кораку посети непосећени град који је најближи тренутном граду.
Скуп кандидата, из кога се налази решење
Функција избора, која бира најбољег кандидата за додавање у решење
Функција изводљивости, која проверава да ли се кандидат може искористити да допринесе решењу
Објективна функција, која додељује вредност решењу, или парцијалном решењу, и
Функција решења, која показује када смо дошли до комплетног решења
Похлепни алгоритми дају добра решења за неке математичке проблеме, али за неке друге нису погодни. Већина проблема за које ова стратегија даје добре резултате има два својства:
Својство похлепног избора
Можемо да направимо који год избор у датом тренутку а да изгледа најбољи, и затим да решимо подпроблеме који се касније јављају. Избор који смо начинили може да зависи од претходних избора, али не и од наредних избора или свих решења потпроблема. Итеративно правимо један похлепни избор за другим, и сводимо сваки дати проблем на мањи проблем. Другим речима, похлепни алгоритам никада не преиспитује своје изборе. То је главна разлика у односу на динамичко програмирање, које је темељније, и гарантује проналажење решења. У сваком кораку, динамичко програмирање даје закључке базиране на свим закључцима у претходном кораку, и може да преиспита алторигамски пут до решења претходног корака.
Оптимална структура
Проблем има оптималну структуру ако оптимално решење проблема садржи оптимална решења потпроблема.
Када стратегија похлепних алгоритама није добра
За многе друге проблеме, похлепни алгоритми могу бити погрешан избор стратегије. Рецимо, у партији шаха, похлепни алгоритам ће увек одиграти онај потез који изгледа најбоље у датом тренутку, не обазирући се на његове последице. На пример, уколико највећу вредност за играча у датој ситуацији има потез у коме он узима противничког ловца, он ће то и учинити, све и ако тај потез отвара противнику могућност да матира играча.
Примене
За већину проблема, похлепни алгоритми углавном (али не и увек) неће успети да нађу глобално оптимално решење, јер они обично не обрађују темељно све могућности. Ови алгоритми врло рано доносе одређене одлуке, које их могу спречити да касније нађу најбоље решење. На пример, сви познати похлепни алгоритми за проблем бојења графа и све остале НП-комплетне проблеме, не налазе увек оптимална решења. Па ипак, они су корисни, јер су у стању да брзо дају добру апроксимацију оптималног решења.
Introduction to Algorithms (Cormen, Leiserson, and Rivest) 1990, Chapter 17 "Greedy Algorithms" pp. 329.
Introduction to Algorithms (Cormen, Leiserson, and Rivest) 2001, Chapter 16 "Greedy Algorithms" .
G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.
