Ahne algoritm koos näidetega: Ahne meetod & Lähenemine

Lang L: none (table-of-contents):

Anonim

Mis on ahne algoritm?

In Ahne algoritm kogum vahendeid rekursiivselt jagatud põhineb maksimaalsel, kohene kättesaadavus, et ressurss igal täitmise staadiumis.

Ahne lähenemisviisi põhjal probleemi lahendamiseks on kaks etappi

  1. Üksuste loendi skannimine
  2. Optimeerimine

Neid etappe käsitletakse selles ahnete algoritmide õpetuses paralleelselt massiivi jagamise käigus.

Ahne lähenemise mõistmiseks peavad teil olema töökorras teadmised rekursioonist ja konteksti vahetamisest. See aitab teil mõista, kuidas koodi jälgida. Saate määratleda ahne paradigma enda vajalike ja piisavate väidete abil.

Ahne paradigma määratleb kaks tingimust.

  • Iga järkjärguline lahendus peab ülesehitama probleemi kõige paremini aktsepteeritud lahenduse suunas.
  • Piisab sellest, kui probleemi struktureerimine võib peatuda piiratud arvu ahnete sammudega.

Kui teoreetika jätkub, kirjeldagem ahne otsimisviisiga seotud ajalugu.

Selles ahne algoritmi õpetuses saate teada:

  • Ahne algoritmide ajalugu
  • Ahned strateegiad ja otsused
  • Ahne lähenemise omadused
  • Miks kasutada ahne lähenemist?
  • Kuidas lahendada tegevuse valimise probleem
  • Ahne lähenemise arhitektuur
  • Ahnete algoritmide puudused

Ahne algoritmide ajalugu

Siin on ahnete algoritmide oluline maamärk:

  • Ahned algoritmid kontseptualiseeriti 1950. aastatel paljude graafikute kõndimise algoritmide jaoks.
  • Esdger Djikstra kontseptualiseeris algoritmi minimaalsete laiuvate puude genereerimiseks. Tema eesmärk oli lühendada marsruutide ulatust Hollandi pealinnas Amsterdamis.
  • Samal kümnendil saavutasid Prim ja Kruskal optimeerimisstrateegiad, mis põhinesid raja kulude minimeerimisel kaalutud marsruutidel.
  • 70. aastatel pakkusid Ameerika teadlased Cormen, Rivest ja Stein oma algoritmide raamatu klassikalises sissejuhatuses ahnete lahenduste rekursiivset ümberstruktureerimist.
  • Ahne otsinguparadigma registreeriti NIST-kirjetes 2005. aastal teist tüüpi optimeerimisstrateegiana.
  • Kuni kuupäevani kasutavad veebi käitavad protokollid, nagu avatud-lühim tee enne (OSPF) ja paljud teised võrgupakettide vahetamise protokollid, ahnestrateegiat võrgus veedetud aja minimeerimiseks.

Ahned strateegiad ja otsused

Loogika kõige lihtsamal kujul keedeti "ahneks" või "mitte ahneks". Need väited määratleti lähenemisviisiga, mida kasutati igas algoritmi etapis edasi liikumiseks.

Näiteks kasutas Djikstra algoritm astmelist ahnust strateegiat, et tuvastada Internetis hostid, arvutades kulufunktsiooni. Kulufunktsiooni tagastatav väärtus määras kindlaks, kas järgmine tee on "ahne" või "mitte ahne".

Lühidalt öeldes lakkab algoritm olemast ahne, kui see teeb mingis etapis sammu, mis pole kohalikult ahne. Ahned probleemid peatuvad, ilma et ahnus oleks enam laienenud.

Ahne lähenemise omadused

Ahne meetodi algoritmi olulised omadused on järgmised:

  • Seal on ressursside järjestatud loetelu koos kulude või väärtuse omistamisega. Need kvantifitseerivad süsteemi piirangud.
  • Piirangu rakendamise ajal võtate ressursside maksimaalse koguse.
  • Näiteks tegevuse planeerimise probleemi korral on ressursikulud tundides ja tegevused tuleb läbi viia järjestikuses järjekorras.

Miks kasutada ahne lähenemist?

Siin on ahne lähenemise kasutamise põhjused:

  • Ahnel lähenemisel on mõned kompromissid, mis võivad muuta selle optimeerimiseks sobivaks.
  • Üks silmapaistvamaid põhjusi on saavutada võimalikult otstarbekas lahendus kohe. Kui tegevusvaliku probleemis (selgitatud allpool) saab enne praeguse tegevuse lõpetamist teha rohkem tegevusi, saab neid tegevusi teha sama aja jooksul.
  • Teine põhjus on jagada probleem rekursiivselt tingimusel, ilma et oleks vaja kõiki lahendusi kombineerida.
  • Tegevuste valimise probleemis saavutatakse "rekursiivse jagamise" samm, skannides üksuste loendit ainult üks kord ja kaaludes teatud tegevusi.

Kuidas lahendada tegevuse valimise probleem

Tegevuste ajastamise näites on iga tegevuse jaoks ette nähtud algus- ja lõpuaeg. Iga tegevus on viide jaoks indekseeritud numbriga. Tegevuskategooriaid on kaks.

  1. käsitletav tegevus : on tegevus, mis on võrdlusalus, millest analüüsitakse võimet teha rohkem kui ühte järelejäänud tegevust.
  2. ülejäänud tegevused: tegevused ühe või mitme indeksiga enne kavandatud tegevust.

Kogukestus näitab tegevuse sooritamise maksumust. See tähendab (finiš - algus) annab meile tegevuse kestuse kestuse.

Saate teada, et ahne ulatus on järelejäänud tegevuste arv, mida saate kaalutud tegevuse ajal teha.

Ahne lähenemise arhitektuur

SAMM 1)

Skannige tegevuskulude loend, alustades indeksist 0 kui vaadeldav indeks.

2. SAMM)

Kui selleks ajaks saab rohkem tegevusi lõpule viia, on kaalutud tegevus lõpetatud, alustage ühe või mitme järelejäänud tegevuse otsimist.

3. SAMM)

Kui järelejäänud tegevusi enam pole, saab järgmiseks vaadeldavaks tegevuseks praegune järelejäänud tegevus. Korrake 1. ja 2. toimingut uue kaalutletud tegevusega. Kui ülejäänud tegevusi pole jäänud, jätkake 4. sammuga.

4. SAMM)

Tagastab arvestatavate indeksite liidu. Need on aktiivsuse indeksid, mida kasutatakse läbilaskevõime maksimeerimiseks.

Ahne lähenemise arhitektuur

Koodi selgitus

#include#include#include#define MAX_ACTIVITIES 12

Koodi selgitus:

  1. Kaasatud päisefailid / klassid
  2. Kasutaja pakutav maksimaalne arv tegevusi.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Koodi selgitus:

  1. Voogesitustoimingute nimeruum.
  2. TIME klassi määratlus
  3. Tunnine ajatempel.
  4. TIME vaikekonstruktor
  5. Tundide muutuja.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Koodi selgitus:

  1. Klassi määratlus tegevusest
  2. Kestuse määravad ajatemplid
  3. Kõik ajatemplid lähtestatakse vaikekonstruktoris väärtusele 0
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Koodi selgitus:

  1. Planeerija klassi määratluse 1. osa.
  2. Arvestatud indeks on massiivi skannimise lähtepunkt.
  3. Initsialiseerimisindeksit kasutatakse juhuslike ajatemplite määramiseks.
  4. Uue operaatori abil jaotatakse aktiivsusobjektide massiiv dünaamiliselt.
  5. Ajastatud kursor määratleb ahnuse praeguse baaskoha.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Koodi selgitus:

  1. Planeerija konstruktor - ajakava klassi määratluse 2. osa.
  2. Vaadeldav indeks määratleb praeguse skannimise praeguse alguse.
  3. Praegune ahne ulatus pole alguses määratletud.
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);}… …

Koodi selgitus:

  1. A for loop kõigi praegu kavandatud tegevuste algus- ja lõputundide alustamiseks.
  2. Algusaja lähtestamine.
  3. Lõppaja initsialiseerimine alati pärast algustundi või täpselt selle algusaja järgi.
  4. Silumisavaldus eraldatud kestuste printimiseks.
public:Activity * activity_select(int);};

Koodi selgitus:

  1. 4. osa - ajakava klassi definitsiooni viimane osa.
  2. Funktsiooni Aktiivsuse valimine võtab aluseks lähtepunkti indeksi ja jagab ahne ülesande ahneteks alamprobleemideks.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Kasutades ulatuseralduse operaatorit (: :), antakse funktsiooni määratlus.
  2. Vaadeldav indeks on väärtus, mida nimetatakse väärtuseks. Greedy_extent on initsialiseeritud just indeks pärast vaadeldavat indeksit.
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++;}… …

Koodi selgitus:

  1. Põhiloogika - ahne ulatus piirdub tegevuste arvuga.
  2. Praeguse tegevuse algustunde kontrollitakse ajastatavana enne, kui kaalutud tegevus (antud indeksi järgi) lõpeb.
  3. Niikaua kui see on võimalik, prinditakse valikuline silumisväljavõte.
  4. Edasi aktiivsusmassi järgmise indeksi juurde
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Koodi selgitus:

  1. Tingimuslik kontroll, kas kõik tegevused on hõlmatud.
  2. Kui ei, siis võite oma ahne taaskäivitada, kui praegune punkt on kaalutud indeks. See on rekursiivne samm, mis jagab ahnelt probleemilause.
  3. Kui jah, naaseb see helistajale, ilma et oleks võimalik ahnust laiendada.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Koodi selgitus:

  1. Põhifunktsioon, mida kasutatakse ajakava kutsumiseks.
  2. Uus ajakava koostatakse kohe.
  3. Funktsiooni tegevuse valimine, mis tagastab tüübilise tegevuse osuti, tuleb helistajale tagasi pärast ahne ülesande lõppu.

Väljund:

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

Ahnete algoritmide puudused

See ei sobi ahnete probleemide korral, kus on vaja lahendust igale alamprobleemile nagu sortimine.

Sellistes Ahne algoritmipraktika probleemides võib Ahne meetod olla vale; halvimal juhul viia isegi mitteoptimaalse lahenduseni.

Seetõttu on ahnete algoritmide puuduseks teadmatuse kasutamine praegusest ahnest seisundist ees.

Allpool on toodud ahne meetodi puudused:

Siin puuna näidatud ahne skaneerimise korral (suurema väärtusega suurem ahnus) võtab algoritmi olek väärtusel 40 tõenäoliselt järgmise väärtusena 29. Lisaks lõpeb tema ülesanne kell 12. See ulatub väärtuseni 41.

Kui aga algoritm läks optimaalsest madalamale rajale või võttis kasutusele vallutusstrateegia. siis järgneks 25-le 40 ja kulude üldine paranemine oleks 65, mis on optimaalseima otsusena hinnatud 24 punkti kõrgemale.

Näited ahnetest algoritmidest

Enamik võrguühenduse algoritme kasutab ahne lähenemist. Siin on loetelu vähestest ahnete algoritmide näidetest:

  • Primi minimaalse laiuva puu algoritm
  • Reisiva müügimehe probleem
  • Graafik - kaardi värvimine
  • Kruskali minimaalse laiuva puu algoritm
  • Dijkstra minimaalse laiuva puu algoritm
  • Graafik - tipu kate
  • Seljakotiprobleem
  • Töö planeerimise probleem

Kokkuvõte:

Kokkuvõtteks võib öelda, et artiklis määratleti ahne paradigma, näidati, kuidas ahne optimeerimine ja rekursioon aitavad teil saavutada parima lahenduse kuni hetkeni. Ahne algoritm on laialdaselt rakendatud probleemide lahendamiseks paljudes keeltes, nagu ahne algoritm Python, C, C #, PHP, Java jne. Greedy algoritmi näite tegevuste valikut kirjeldati kui strateegilist probleemi, mis võib ahnuse abil saavutada maksimaalse läbilaskevõime lähenemisviisi. Lõpuks selgitati ahne lähenemise kasutamise halbu külgi.