Увод у похлепни алгоритам
Стратегија која се користи за решавање проблема. Похлепни алгоритам сматра се једним од приступа који се користе за рјешавање проблема. Ово херетичко решавање проблема иде у одабиру избора који се у том тренутку чини најбољим. Овај приступ се најбоље користи за решавање проблема оптимизације. Проблеми оптимизације могу се дефинисати као проблеми који захтевају минималне или максималне резултате. Грееди алгоритам је најједноставнији и најпристранији приступ који се може користити за постизање оптималног решења.
Шта је похлепни алгоритам?
Грееди Алгоритхм је алгоритамска стратегија која се користи да се направи најбољи изборни избор у врло малој фази, а на крају се постигне глобално оптимално рјешење. Овај алгоритам бира најбоље изводљиво решење у том тренутку без обзира на последице. Похлепна метода каже да проблем треба рјешавати у фазама у којима се узима у обзир сваки унос с обзиром да је овај унос изведив. Пошто се овај приступ фокусира само на непосредни резултат без обзира на ширу слику, сматра се похлепним.
Дефинисање основног концепта
До сада знамо шта је похлепни алгоритам и зашто је тако назван. Следећи показивачи ће вас разумети похлепним алгоритмом на бољи начин. До сада је било врло јасно да похлепни алгоритам ради само када постоји проблем; ипак, овај приступ је применљив само ако имамо услов или ограничење за тај проблем.
Врсте проблема
- Проблем минимизације: Решавање проблема је лако с обзиром да су сви услови испуњени. Међутим, када овај проблем захтева минималан резултат, онда се то назива проблем минимизације.
- Проблем са максимизацијом : Проблем који захтева максималан резултат познат је као проблем максимизације.
- Проблем са оптимизацијом: Проблем се назива проблем оптимизације када захтева минималне или максималне резултате.
Врсте решења
- Изводљиво решење: Сада када се појави проблем, имамо много веродостојних решења за овај проблем. Ипак, узимајући у обзир услов постављен на том проблему, бирамо решења која задовољавају дати услов. Оваква решења која нам помажу да постигнемо резултате који испуњавају задати услов назива се Изводљиво решење .
- Оптимално решење: Решење се назива оптималним када је већ изведиво и постиже циљ проблема; најбољи резултат. Овај би циљ могао бити минимални или максимални резултат. Оно што треба примијетити је да ће сваки проблем имати само једно оптимално рјешење.
Следећи пример ће вам олакшати разумевање похлепне методе. Рецимо, неко жели да купи најбољи аутомобил на тржишту. Једна од метода избора овог аутомобила је анализа свих аутомобила на тржишту. Сада, ово захтева много времена, како би се олакшало одабир аутомобила од оних одређених марки у које су заинтересовани да уложе. Категоризирајући то даље, опет би се одабрали жељени модели гледајући на његове карактеристике. Стога је овде коришћен приступ похлепан јер је ово решење било оптимално решење за вас, узимајући у обзир да су вам сви фактори били повољни.
Основне компоненте похлепног алгоритма
Сада када боље разумемо овај механизам, истражимо основне компоненте похлепног алгоритма који га издваја од осталих процеса:
- Скуп кандидата: Одговор се ствара из овог скупа.
- Функција одабира : бира најбољег кандидата који ће бити укључен у решење.
- Функција изводљивости: Овај одељак израчунава да ли се кандидат може користити за допринос решењу.
- Објективна функција: додјељује вриједност цјеловитом или дјеломичном рјешењу.
- Функција решења: користи се за означавање да ли је задовољено правилно решење.
Гдје најбољи похлепни алгоритам најбоље функционише?
Похлепни алгоритам може се примијенити на доље наведене проблеме.
- Похлепни приступ може се користити за проналажење графа минималног распона дрвета помоћу Примовог или Крускаловог алгоритма
- Проналажење најкраћег пута између две врхове је још један проблем који се може решити похлепним алгоритмом. Примјена Дијкстра алгоритма заједно са похлепним алгоритмом ће вам дати оптимално рјешење.
- Хуффман Цодинг
Предности
Највећа предност алгоритма похлепности у односу на друге је та што ју је лако имплементирати и у већини случајева врло ефикасан.
Недостаци
Грееди Алгоритхм у основи гради рјешење по дио и одабир сљедећег дијела на такав начин да одмах нуди најбоље рјешење постојећег проблема. Као резултат, нема бриге или бриге о последицама донесених тренутних одлука. Никада не преиспитујући претходно одабране одлуке, похлепни алгоритам не успе да произведе оптимално решење, иако даје скоро оптимално решење . Проблем са руксаком и проблем продавца путника су примери проблема где похлепни алгоритам не успе да произведе оптимално решење.
- Проблем са руксаком: Најчешћи назив по имену ранац, свакодневни је проблем с којим се суочавају многи људи. Рецимо, поставили смо предмете и свака од њих има различиту тежину и вредност (добит) која се пуни у контејнер или их треба сакупљати на такав начин да је укупна тежина мања или једнака оној у спремнику, док је укупна добит максимална .
Закључак
Похлепни алгоритам најбоље је применити када је потребно решење у реалном времену, а приближни одговори су „довољно добри“. Јасно је да похлепни алгоритам минимизира време, истовремено осигуравајући да се произведе оптимално решење, па је стога и применљивије за употребу у ситуацији када је потребно мање времена. Након читања овог чланка, неко може имати добру идеју о похлепним алгоритамима. Поред тога, у овом посту је објашњено зашто се сматра најбољим оквиром који одговара на готово све програмске изазове заједно са тим што вам помаже да одлучите најоптималније решење у датом тренутку.
Међутим, са грубе стране, за примену теорије похлепног алгоритма потребно је јаче радити да би се знале исправне теме. Иако је научни концепт који има логику, он такође има суштину креативности.
Препоручени чланци
Ово је водич за шта је похлепни алгоритам. Овде смо разговарали о основном концепту, компонентама, предности и недостатку похлепног алгоритма. Можете и да прођете кроз друге наше предложене чланке да бисте сазнали више -
- Алгоритам у програмирању
- Шта је Перл?
- Увод у алгоритам
- Шта је Агиле Спринт?