Похлепни алгоритам

Похлепни алгоритам је алгоритам који користи метахеуристику за решавање проблема, такву да у сваком понављању поступка бира локално најбоље решење, у нади да ће тако коначно изнаћи глобални оптимум.

На пример, примена стратегије похлепног алгоритма на Проблем трговачког путника даје следећи алгоритам: У сваком кораку посети непосећени град који је најближи тренутном граду.

Скуп кандидата, из кога се налази решење
Функција избора, која бира најбољег кандидата за додавање у решење
Функција изводљивости, која проверава да ли се кандидат може искористити да допринесе решењу
Објективна функција, која додељује вредност решењу, или парцијалном решењу, и
Функција решења, која показује када смо дошли до комплетног решења

Похлепни алгоритми дају добра решења за неке математичке проблеме, али за неке друге нису погодни. Већина проблема за које ова стратегија даје добре резултате има два својства:

Својство похлепног избора: Можемо да направимо који год избор у датом тренутку а да изгледа најбољи, и затим да решимо подпроблеме који се касније јављају. Избор који смо начинили може да зависи од претходних избора, али не и од наредних избора или свих решења потпроблема. Итеративно правимо један похлепни избор за другим, и сводимо сваки дати проблем на мањи проблем. Другим речима, похлепни алгоритам никада не преиспитује своје изборе. То је главна разлика у односу на динамичко програмирање, које је темељније, и гарантује проналажење решења. У сваком кораку, динамичко програмирање даје закључке базиране на свим закључцима у претходном кораку, и може да преиспита алторигамски пут до решења претходног корака.

Оптимална структура: Проблем има оптималну структуру ако оптимално решење проблема садржи оптимална решења потпроблема.

Када стратегија похлепних алгоритама није добра: За многе друге проблеме, похлепни алгоритми могу бити погрешан избор стратегије. Рецимо, у партији шаха, похлепни алгоритам ће увек одиграти онај потез који изгледа најбоље у датом тренутку, не обазирући се на његове последице. На пример, уколико највећу вредност за играча у датој ситуацији има потез у коме он узима противничког ловца, он ће то и учинити, све и ако тај потез отвара противнику могућност да матира играча.

Примене

За већину проблема, похлепни алгоритми углавном (али не и увек) неће успети да нађу глобално оптимално решење, јер они обично не обрађују темељно све могућности. Ови алгоритми врло рано доносе одређене одлуке, које их могу спречити да касније нађу најбоље решење. На пример, сви познати похлепни алгоритми за проблем бојења графа и све остале НП-комплетне проблеме, не налазе увек оптимална решења. Па ипак, они су корисни, јер су у стању да брзо дају добру апроксимацију оптималног решења.

Ако се може доказати да похлепни алгоритам налази глобални оптимум за дату класу проблема, он се обично и користи, јер је бржи од осталих оптимизационих метода, као што је динамичко програмирање. Примери таквих похлепних алгоритама су Крускалов алгоритам и Примов алгоритам за налажење минималног обухватног стабла, Дијкстрин алгоритам за налажење најкраћих путева у графу из једног почетка, алгоритам за налажење оптималног Хафмановог стабла, као и алгоритам за решење проблема избора активности.

Литература

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.

Спољашње везе