Chamtivý algoritmus s príkladmi: Chamtivá metóda a Prístup

Obsah:

Anonim

Čo je chamtivý algoritmus?

V chamtivom algoritme je sada zdrojov rekurzívne rozdelená na základe maximálnej okamžitej dostupnosti daného zdroja v ktorejkoľvek danej fáze vykonávania.

Na vyriešenie problému založeného na chamtivom prístupe existujú dve fázy

  1. Skenovanie zoznamu položiek
  2. Optimalizácia

Tieto fázy sú paralelne obsiahnuté v tomto návode na algoritmus Greedy, ktorý sa týka priebehu delenia poľa.

Aby ste pochopili chamtivý prístup, budete musieť mať praktické vedomosti o rekurzii a prepínaní kontextu. To vám pomôže pochopiť, ako vysledovať kód. Chamtivú paradigmu môžete definovať v zmysle svojich vlastných potrebných a dostatočných výrokov.

Chamtivú paradigmu definujú dve podmienky.

  • Každé postupné riešenie musí štruktúrovať problém smerom k svojmu najlepšie prijatému riešeniu.
  • Postačí, ak sa štruktúrovanie problému môže zastaviť v konečnom počte chamtivých krokov.

S pokračujúcim teoretizovaním popíšme históriu spojenú s prístupom hľadania Greedy.

V tomto výučbe algoritmu Greedy sa dozviete:

  • Dejiny chamtivých algoritmov
  • Chamtivé stratégie a rozhodnutia
  • Charakteristika chamtivého prístupu
  • Prečo používať chamtivý prístup?
  • Ako vyriešiť problém s výberom aktivity
  • Architektúra chamtivého prístupu
  • Nevýhody chamtivých algoritmov

Dejiny chamtivých algoritmov

Tu je dôležitý orientačný bod chamtivých algoritmov:

  • Chamtivé algoritmy boli konceptualizované pre mnoho algoritmov chôdze po grafe v 50. rokoch.
  • Esdger Djikstra konceptualizoval algoritmus tak, aby generoval minimálne rozložené stromy. Mal za cieľ skrátiť rozpätie trás v holandskom hlavnom meste Amsterdam.
  • V rovnakom desaťročí dosiahli spoločnosti Prim a Kruskal optimalizačné stratégie, ktoré boli založené na minimalizácii nákladov na trasy pozdĺž zvážených trás.
  • V 70. rokoch americkí vedci Cormen, Rivest a Stein vo svojom klasickom úvode do knihy algoritmov navrhli rekurzívnu subštrukturalizáciu chamtivých riešení.
  • Paradigma hľadania Greedy bola zaregistrovaná ako iný typ optimalizačnej stratégie v záznamoch NIST v roku 2005.
  • Až do dnešného dňa protokoly, ktoré prevádzkujú web, ako napríklad open-shortest-path-first (OSPF) a mnoho ďalších protokolov na prepínanie sieťových paketov, používajú nenásytnú stratégiu na minimalizáciu času stráveného v sieti.

Chamtivé stratégie a rozhodnutia

Logika v jej najjednoduchšej podobe sa zmenila na „nenásytnú“ alebo „nenásytnú“. Tieto vyhlásenia boli definované prístupom prijatým k pokroku v každej etape algoritmu.

Napríklad Djikstrov algoritmus využíval postupnú nenásytnú stratégiu na identifikáciu hostiteľov na internete výpočtom nákladovej funkcie. Hodnota vrátená nákladovou funkciou určovala, či je ďalšia cesta „nenásytná“ alebo „nenáročná“.

Stručne povedané, algoritmus prestáva byť nenásytný, ak v ktorejkoľvek fáze urobí krok, ktorý nie je lokálne nenásytný. Chamtivé problémy sa zastavia bez ďalšieho rozsahu chamtivosti.

Charakteristika chamtivého prístupu

Dôležitými charakteristikami algoritmu chamtivej metódy sú:

  • K dispozícii je zoradený zoznam zdrojov s uvedením nákladov alebo hodnoty. Tieto kvantifikujú obmedzenia v systéme.
  • V čase obmedzenia použijete maximálne množstvo zdrojov.
  • Napríklad v probléme s plánovaním činnosti sú náklady na prostriedky v hodinách a činnosti je potrebné vykonať v poradí.

Prečo používať chamtivý prístup?

Tu sú dôvody použitia nenásytného prístupu:

  • Chamtivý prístup má niekoľko kompromisov, vďaka čomu je vhodný na optimalizáciu.
  • Jedným z hlavných dôvodov je okamžité dosiahnutie najuskutočniteľnejšieho riešenia. Ak je možné v probléme s výberom aktivity (vysvetlené nižšie) vykonať viac aktivít pred dokončením aktuálnej aktivity, je možné ich vykonať v rovnakom čase.
  • Ďalším dôvodom je rekurzívne rozdelenie problému na základe podmienky, pričom nie je potrebné kombinovať všetky riešenia.
  • V probléme s výberom aktivity sa krok „rekurzívneho rozdelenia“ dosiahne skenovaním zoznamu položiek iba raz a zvážením určitých aktivít.

Ako vyriešiť problém s výberom aktivity

V príklade plánovania aktivít je pre každú aktivitu čas začatia a ukončenia. Každá aktivita je pre referenciu indexovaná číslom. Existujú dve kategórie aktivít.

  1. uvažovaná aktivita : je Aktivita, čo je referencia, z ktorej sa analyzuje schopnosť vykonávať viac ako jednu zostávajúcu Aktivitu.
  2. zostávajúce činnosti: činnosti v jednom alebo viacerých indexoch pred uvažovanou činnosťou.

Celkové trvanie predstavuje náklady na vykonávanie činnosti. To znamená (dokončenie - začatie), ktoré nám dáva trvanie ako náklady na činnosť.

Dozviete sa, že chamtivý rozsah je počet zostávajúcich aktivít, ktoré môžete vykonať v čase uvažovanej činnosti.

Architektúra chamtivého prístupu

KROK 1)

Naskenujte zoznam nákladov na činnosť počnúc indexom 0 ako uvažovaným indexom.

KROK 2)

Keď bude možné dokončiť viac aktivít v danom čase, príslušná aktivita sa dokončí, začnite hľadať jednu alebo viac zostávajúcich aktivít.

KROK 3)

Ak už žiadne ďalšie aktivity nie sú, aktuálna zostávajúca aktivita sa stane ďalšou zvažovanou aktivitou. Opakujte kroky 1 a 2 s novou uvažovanou aktivitou. Ak už nezostávajú žiadne ďalšie aktivity, prejdite na krok 4.

KROK 4)

Vrátiť spojenie uvažovaných indexov. Toto sú indexy aktivity, ktoré sa použijú na maximalizáciu priepustnosti.

Architektúra chamtivého prístupu

Vysvetlenie kódu

#include#include#include#define MAX_ACTIVITIES 12

Vysvetlenie kódu:

  1. Zahrnuté hlavičkové súbory / triedy
  2. Maximálny počet aktivít poskytovaných používateľom.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Vysvetlenie kódu:

  1. Obor názvov pre operácie streamovania.
  2. Definícia triedy pre TIME
  3. Hodinová časová značka.
  4. Predvolený konštruktér TIME
  5. Premenná hodín.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Vysvetlenie kódu:

  1. Definícia triedy z aktivity
  2. Časové pečiatky definujúce trvanie
  3. Všetky časové značky sú inicializované na 0 v predvolenom konštruktore
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Vysvetlenie kódu:

  1. Časť 1 definície triedy plánovača.
  2. Považovaný index je východiskovým bodom pre skenovanie poľa.
  3. Inicializačný index sa používa na priradenie náhodných časových značiek.
  4. Pole objektov činnosti sa dynamicky alokuje pomocou nového operátora.
  5. Naplánovaný ukazovateľ definuje aktuálne základné umiestnenie pre chamtivosť.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Vysvetlenie kódu:

  1. Konštruktor plánovača - časť 2 definície triedy plánovača.
  2. Uvažovaný index definuje aktuálny začiatok aktuálneho prehľadávania.
  3. Aktuálny chamtivý rozsah je na začiatku nedefinovaný.
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);}… …

Vysvetlenie kódu:

  1. Smyčka for na inicializáciu začiatočných a konečných hodín každej z aktuálne naplánovaných aktivít.
  2. Inicializácia času začiatku.
  3. Inicializácia času ukončenia vždy po alebo presne v začiatočnú hodinu.
  4. Príkaz ladenia na vytlačenie pridelených časov.
public:Activity * activity_select(int);};

Vysvetlenie kódu:

  1. 4. časť - posledná časť definície triedy plánovača.
  2. Funkcia výberu činnosti berie ako základ index počiatočného bodu a rozdeľuje nenásytné hľadanie na nenásytné podproblémy.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Pomocou operátora rozlíšenia rozsahu (: :) sa poskytuje definícia funkcie.
  2. Uvažovaný index je index volaný podľa hodnoty. Greedy_extent je inicializovaný iba index za uvažovaným indexom.
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++;}… …

Vysvetlenie kódu:

  1. Základná logika - chamtivý rozsah je obmedzený na počet aktivít.
  2. Počiatočné hodiny aktuálnej aktivity sa kontrolujú ako naplánovateľné pred dokončením uvažovanej aktivity (danej uvažovaným indexom).
  3. Pokiaľ je to možné, vytlačí sa voliteľný príkaz ladenia.
  4. Prejsť na ďalší index v poli aktivít
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Vysvetlenie kódu:

  1. Podmienené skontroluje, či boli pokryté všetky činnosti.
  2. Ak nie, môžete svoju chamtivosť reštartovať s aktuálnym bodom považovaným za Index. Toto je rekurzívny krok, ktorý chamtivo rozdeľuje problémové vyhlásenie.
  3. Ak áno, vráti sa volajúcemu bez možnosti rozšírenia nenásytnosti.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Vysvetlenie kódu:

  1. Hlavná funkcia použitá na vyvolanie plánovača.
  2. Je vytvorený nový plánovač.
  3. Funkcia výberu aktivity, ktorá vráti ukazovateľ aktivity typu, sa vráti volajúcemu po ukončení chamtivej úlohy.

Výkon:

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

Nevýhody chamtivých algoritmov

Nie je vhodný pre nenásytné problémy, kde je potrebné riešenie pre každý čiastkový problém, ako je triedenie.

V takýchto problémoch s praktikovaním algoritmu Greedy môže byť metóda Greedy nesprávna; v najhoršom prípade dokonca viesť k neoptimálnemu riešeniu.

Nevýhodou chamtivých algoritmov je preto použitie nevedenia, čo leží pred súčasným chamtivým stavom.

Ďalej je uvedená nevýhoda chamtivej metódy:

V chamtivom skenovaní, ktoré sa tu zobrazuje ako strom (vyššia hodnota, vyššia nenásytnosť), bude stav algoritmu na hodnote: 40 pravdepodobne brať ako ďalšiu hodnotu 29. Ďalej jeho pátranie končí na 12. To predstavuje hodnotu 41.

Ak by sa však algoritmus vydal suboptimálnou cestou alebo prijal stratégiu dobývania. potom by nasledovalo 25 a 40 a celkové zlepšenie nákladov by bolo 65, čo je o 24 bodov vyššie ako neoptimálne rozhodnutie.

Príklady chamtivých algoritmov

Väčšina sieťových algoritmov používa nenásytný prístup. Tu je zoznam niekoľkých príkladov algoritmu Greedy:

  • Algoritmus minimálneho rozpätia stromu Prim
  • Problém s cestujúcim predavačom
  • Graf - vyfarbenie mapy
  • Kruskalov algoritmus minimálneho rozpätia stromov
  • Dijkstraov algoritmus minimálneho rozpätia stromov
  • Graf - vrcholový kryt
  • Problém s batohom
  • Problém s plánovaním práce

Zhrnutie:

Ak to zhrnieme, článok definoval chamtivú paradigmu, ukázal, ako chamtivá optimalizácia a rekurzia vám môžu pomôcť dosiahnuť najlepšie riešenie až do určitej miery. Algoritmus Greedy je široko používaný v aplikáciách na riešenie problémov v mnohých jazykoch, ako je Greedy algoritmus Python, C, C #, PHP, Java atď. Výber aktivity príkladu algoritmu Greedy bol opísaný ako strategický problém, ktorý by mohol dosiahnuť maximálnu priepustnosť pomocou chamtivosti prístup. Na záver boli vysvetlené nevýhody použitia chamtivého prístupu.