Похлепни алгоритам са примерима: Похлепна метода & амп; Приступ

Преглед садржаја:

Anonim

Шта је похлепни алгоритам?

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

Постоје две фазе за решавање проблема заснованог на похлепном приступу

  1. Скенирање листе ставки
  2. Оптимизација

Ове фазе су паралелно обрађене у овом упутству за похлепни алгоритам, током дељења низа.

Да бисте разумели похлепни приступ, мораћете да имате функционално знање о рекурзији и пребацивању контекста. Ово вам помаже да разумете како да пронађете код. Похлепну парадигму можете дефинисати у смислу сопствених потребних и довољних изјава.

Два услова дефинишу похлепну парадигму.

  • Свако постепено решење мора структурирати проблем према његовом најбоље прихваћеном решењу.
  • Довољно је ако се структурирање проблема може зауставити у коначном броју похлепних корака.

Наставком теоретизације, опишимо историју повезану са приступом похлепне потраге.

У овом упутству за похлепни алгоритам научићете:

  • Историја похлепних алгоритама
  • Похлепне стратегије и одлуке
  • Карактеристике похлепног приступа
  • Зашто користити похлепни приступ?
  • Како решити проблем избора активности
  • Архитектура похлепног приступа
  • Мане похлепних алгоритама

Историја похлепних алгоритама

Овде је важан оријентир похлепних алгоритама:

  • Похлепни алгоритми су конципирани за многе алгоритме шетње графом педесетих година.
  • Есдгер Дјикстра је концептуализовао алгоритам за генерисање минимално распрострањених стабала. Циљ му је био да скрати распон рута у холандском главном граду Амстердаму.
  • У истој деценији Прим и Крускал постигли су стратегије оптимизације које су се заснивале на умањивању трошкова пута дуж одмерених рута.
  • Седамдесетих година амерички истраживачи, Цормен, Ривест и Стеин предложили су рекурзивно потструктурирање похлепних решења у свом класичном уводу у књигу алгоритама.
  • Парадигма похлепног претраживања регистрована је као друга врста стратегије оптимизације у евиденцијама НИСТ-а 2005. године.
  • До данас, протоколи који покрећу мрежу, попут отвореног најкраћег пута (ОСПФ) и многи други протоколи за пребацивање мрежних пакета користе похлепну стратегију да минимизирају време проведено на мрежи.

Похлепне стратегије и одлуке

Логика се у свом најлакшем облику сводила на „похлепно“ или „не похлепно“. Ове изјаве су дефинисане приступом за напредовање у свакој фази алгоритма.

На пример, Ђикстрин алгоритам је користио постепену похлепну стратегију идентификовања хостова на Интернету израчунавањем функције трошкова. Вредност коју је вратила функција трошкова одредила је да ли је следећа путања „похлепна“ или „непохлепна“.

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

Карактеристике похлепног приступа

Важне карактеристике алгоритма похлепне методе су:

  • Постоји уређена листа ресурса са атрибутима трошкова или вредности. Ови квантификују ограничења на систему.
  • Узећете максималну количину ресурса у времену када се примењује ограничење.
  • На пример, у проблему заказивања активности, трошкови ресурса су изражени у сатима, а активности треба извршити серијским редоследом.

Зашто користити похлепни приступ?

Ево разлога за употребу похлепног приступа:

  • Похлепни приступ има неколико компромиса, што га може учинити погодним за оптимизацију.
  • Један од истакнутих разлога је да се одмах постигне најизводљивије решење. У проблему избора активности (Објашњено у наставку), ако се може обавити више активности пре завршетка тренутне активности, ове активности могу се обавити у исто време.
  • Други разлог је подела проблема рекурзивно на основу услова, без потребе за комбиновањем свих решења.
  • У проблему избора активности, корак „рекурзивна подела“ постиже се скенирањем листе ставки само једном и разматрањем одређених активности.

Како решити проблем избора активности

У примеру распоређивања активности постоји време „почетка“ и „завршетка“ за сваку активност. Свака активност је индексирана бројем за референцу. Постоје две категорије активности.

  1. разматрана активност : је активност, која представља референцу на основу које се анализира способност обављања више од једне преостале активности.
  2. преостале активности: активности са једним или више индекса испред разматране активности.

Укупно трајање даје трошкове обављања делатности. То је (заврши - започни) даје нам трајање као трошак активности.

Научићете да је похлепни степен број преосталих активности које можете обављати у време разматране активности.

Архитектура похлепног приступа

КОРАК 1)

Скенирајте листу трошкова активности, почевши од индекса 0 као разматраног индекса.

КОРАК 2)

Када до тада може да се заврши више активности, разматрана активност заврши, започните потрагу за једном или више преосталих активности.

КОРАК 3)

Ако више нема преосталих активности, тренутна преостала активност постаје следећа разматрана активност. Поновите 1. и 2. корак са новом разматраном активношћу. Ако нема преосталих активности, пређите на корак 4.

КОРАК 4)

Врати унију разматраних индекса. То су индекси активности који ће се користити за максимализовање протока.

Архитектура похлепног приступа

Објашњење кода

#include#include#include#define MAX_ACTIVITIES 12

Објашњење кода:

  1. Укључене датотеке / класе заглавља
  2. Максималан број активности које пружа корисник.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Објашњење кода:

  1. Простор имена за стриминг операције.
  2. Дефиниција класе за ТИМЕ
  3. Ознака сата.
  4. ТИМЕ задани конструктор
  5. Променљива у сатима.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Објашњење кода:

  1. Дефиниција одељења из активности
  2. Временске ознаке које дефинишу трајање
  3. Све временске ознаке су иницијализоване на 0 у подразумеваном конструктору
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Објашњење кода:

  1. 1. део дефиниције класе планера.
  2. Сматрани индекс је почетна тачка за скенирање низа.
  3. Индекс иницијализације се користи за додељивање случајних временских ознака.
  4. Низ објеката активности динамички се додељује помоћу новог оператора.
  5. Заказани показивач дефинише тренутну основну локацију за похлепу.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Објашњење кода:

  1. Конструктор планера - 2. део дефиниције класе планера.
  2. Разматрани индекс дефинише тренутни почетак тренутног скенирања.
  3. Тренутни похлепни обим је на почетку недефинисан.
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++){current_activities[init_index].start.hours =rand() % 12;current_activities[init_index].finish.hours =current_activities[init_index].start.hours +(rand() % 2);printf("\nSTART:%d END %d\n",current_activities[init_index].start.hours,current_activities[init_index].finish.hours);}… …

Објашњење кода:

  1. Петља фор за иницијализацију почетног и завршног сата сваке од тренутно заказаних активности.
  2. Иницијализација времена почетка.
  3. Иницијализација времена завршетка увек након или тачно на почетном сату.
  4. Изјава о отклањању грешака за испис додељених трајања.
public:Activity * activity_select(int);};

Објашњење кода:

  1. Део 4 - последњи део дефиниције класе планера.
  2. Функција одабира активности узима индекс почетне тачке као основу и дели похлепну потрагу у похлепне потпроблеме.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Коришћењем оператора резолуције опсега (: :), дата је дефиниција функције.
  2. Разматрани индекс је индекс који се назива вредност. Грееди_ектент је иницијализовани само индекс након разматраног индекса.
Activity * Scheduler :: activity_select(int considered_index){while( (greedy_extent < MAX_ACTIVITIES ) &&((this->current_activities[greedy_extent]).start.hours <(this->current_activities[considered_index]).finish.hours )){printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",(this->current_activities[greedy_extent]).start.hours,(this->current_activities[greedy_extent]).finish.hours,greedy_extent + 1);greedy_extent++;}… …

Објашњење кода:

  1. Основна логика - Похлепни опсег ограничен је на број активности.
  2. Почетни сати текуће активности се проверавају као планирани пре него што се заврши разматрана активност (дата разматраним индексом)
  3. Све док је то могуће, штампа се опционална изјава за отклањање грешака.
  4. Прелазак на следећи индекс низа активности
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Објашњење кода:

  1. Условна провера да ли су све активности обухваћене.
  2. Ако не, можете поново покренути свог похлепног са наведеним индексом као тренутном тачком. Ово је рекурзивни корак који похлепно дели поделу проблема.
  3. Ако је одговор да, враћа се позиваоцу без могућности за продужење похлепе.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Објашњење кода:

  1. Главна функција која се користи за позивање планера.
  2. Инстанциран је нови роковник.
  3. Функција одабира активности, која враћа показивач на активност типа, враћа се позиваоцу након завршетка похлепне потраге.

Излаз:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

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

Није погодно за похлепне проблеме где се тражи решење за сваки подпроблем попут сортирања.

У таквим проблемима вежбања похлепног алгоритма, похлепна метода може бити погрешна; у најгорем случају чак довести до неоптималног решења.

Стога је недостатак похлепних алгоритама коришћење незнања шта је испред тренутног похлепног стања.

Испод је приказ недостатка похлепне методе:

У похлепном скенирању приказаном овде као стабло (већа вредност већа похлепа), стање алгоритма на вредности: 40, вероватно узима 29 као следећу вредност. Даље, његова потрага се завршава у 12. То износи вредност 41.

Међутим, ако је алгоритам кренуо неоптимално или је усвојио стратегију освајања. тада би 25 следило 40, а укупно побољшање трошкова би било 65, што се процењује за 24 поена више као неоптимална одлука.

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

Већина мрежних алгоритама користи похлепни приступ. Ево листе неколико примера похлепног алгоритма:

  • Примов минимални алгоритам дрвећа у распону
  • Проблем путујућег продавца
  • Графикон - Бојање мапе
  • Крускалов алгоритам минималног распона дрвећа
  • Дијкстрин алгоритам минималног распона стабла
  • Графикон - Вертек Цовер
  • Кнапсацк Проблем
  • Проблем распоређивања послова

Резиме:

Да резимирамо, чланак је дефинисао похлепну парадигму, показао како похлепна оптимизација и рекурзија могу да вам помогну у постизању најбољег решења до одређене тачке. Похлепни алгоритам је широко примењен за решавање проблема на многим језицима као Похлепни алгоритам Питхон, Ц, Ц #, ПХП, Јава итд. Избор активности примера Похлепног алгоритма описан је као стратешки проблем који може постићи максималну пропусност користећи похлепне приступ. На крају су објашњени недостаци употребе похлепног приступа.