Ahne algoritm koos näitega: mis on, meetod ja lähenemisviis

Ahne lähenemisviisi mõistmiseks peavad teil olema tööteadmised rekursiooni ja konteksti vahetamise kohta. See aitab teil mõista, kuidas koodi jälgida. Ahne paradigma saate määratleda oma vajalike ja piisavate väidete kaudu.

Ahne paradigma määratlevad kaks tingimust.

• Iga järkjärguline lahendus peab struktureerima probleemi kõige paremini aktsepteeritud lahenduse suunas.
• Piisab, kui probleemi struktureerimine saab seiskuda piiratud arvu ahnete sammudega.

Kui teoretiseerimine jätkub, kirjeldagem ahne otsingu lähenemisviisiga seotud ajalugu.

Ahne ajalugu Algorithms

Siin on ahnete algoritmide oluline maamärk:

• Ahned algoritmid loodi 1950. aastatel paljude graafiku läbimise algoritmide jaoks.
• Esdger Djikstra kujundas algoritmi minimaalse ulatusega puude genereerimiseks. Tema eesmärk oli lühendada liinide ulatust Hollandi pealinnas Amsterdamis.
• Samal kümnendil saavutasid Prim ja Kruskal optimeerimisstrateegiad, mis põhinesid teekulude minimeerimisel kaalutud marsruutidel.
• 70ndatel pakkusid Ameerika teadlased Cormen, Rivest ja Stein oma klassikalises algoritmide sissejuhatuses välja ahnete lahenduste rekursiivse alamstruktureerimise.
• Ahne otsinguparadigma registreeriti NIST-i kirjetes teist tüüpi optimeerimisstrateegiana 2005. aastal.
• Seni kasutavad veebi käitavad protokollid, näiteks avatud lühima tee-first (OSPF) ja paljud teised võrgupakettide vahetamise protokollid ahnet strateegiat, et minimeerida võrgus veedetud aega.

Ahned strateegiad ja otsused

Loogika selle kõige lihtsamal kujul taandati sõnadeks "ahne" või "mitte ahne". Need väited määratleti igas algoritmi etapis edasiliikumiseks kasutatud lähenemisviisiga.

Näiteks Djikstra algoritm kasutas järkjärgulist ahnet strateegiat, mis tuvastas Internetis olevad hostid kulufunktsiooni arvutamise teel. Kulufunktsiooni tagastatud väärtus määras, kas järgmine tee on "ahne" või "mitteahne".

Lühidalt öeldes lakkab algoritm olemast ahne, kui ta mõnes etapis astub sammu, mis ei ole kohapeal ahne. Ahnused probleemid peatuvad ilma ahnuse edasise ulatuseta.

Ahne algoritmi omadused

Greedy algoritmi olulised omadused on järgmised:

• Seal on järjestatud ressursside loend koos kulude või väärtuse omistamisega. Need kvantifitseerivad süsteemi piiranguid.
• Piirangu kehtivusaja jooksul kasutate maksimaalselt ressursse.
• Näiteks tegevuste ajastamise probleemi puhul on ressursikulud tundides ja tegevused tuleb sooritada järjestikuses järjekorras.

Miks kasutada ahne lähenemisviisi?

Siin on ahne lähenemisviisi kasutamise põhjused:

• Ahne lähenemisviis sisaldab mõningaid kompromisse, mis võivad muuta selle optimeerimiseks sobivaks.
• Üks silmapaistev põhjus on viivitamatult kõige teostatavama lahenduse leidmine. Tegevuse valiku ülesandes (Selgitatud allpool), kui enne praeguse tegevuse lõpetamist saab teha rohkem tegevusi, saab need tegevused sooritada sama aja jooksul.
• Teine põhjus on probleemi rekursiivne jagamine tingimuse alusel, ilma et oleks vaja kõiki lahendusi kombineerida.
• Tegevuse valiku ülesandes saavutatakse “rekursiivse jagamise” samm, skaneerides üksuste loendit ainult üks kord ja võttes arvesse teatud tegevusi.

Kuidas lahendada tegevuse valiku probleemi

Tegevuse ajakava näites on iga tegevuse jaoks "alguse" ja "lõpu" aeg. Iga tegevus on viitamiseks indekseeritud numbriga. Tegevuskategooriaid on kaks.

1. kaalutletud tegevus: on tegevus, mis on viide, mille põhjal analüüsitakse võimet teha rohkem kui üks järelejäänud tegevus.
2. ülejäänud tegevused: tegevused ühe või mitme indeksiga enne vaadeldavat tegevust.

Kogukestus annab tegevuse sooritamise maksumuse. See tähendab (lõpeta – algus) annab meile tegevuse kuluna kestvuse.

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

ArchiAhne lähenemisviisi

SAMM 1) Skannige tegevuskulude loendit, alustades vaadeldava indeksina indeksist 0.

SAMM 2) Kui selleks ajaks saab rohkem tegevusi lõpetada, siis vaadeldav tegevus lõppeb, alustage ühe või mitme järelejäänud tegevuse otsimist.

SAMM 3) Kui järelejäänud tegevusi enam pole, saab praegusest järelejäänud tegevusest järgmine arvestatav tegevus. Korrake samme 1 ja 2 uue vaadeldava tegevusega. Kui järelejäänud tegevusi pole, minge 4. sammu juurde.

SAMM 4) Tagasta vaadeldavate indeksite liit. Need on aktiivsusindeksid, mida kasutatakse läbilaskevõime maksimeerimiseks.

Koodi selgitus

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Koodi selgitus:

1. Kaasatud päisefailid/klassid
2. Maksimaalne kasutaja pakutavate tegevuste arv.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Koodi selgitus:

1. Voogesitustoimingute nimeruum.
2. Klassi määratlus TIME jaoks
3. Tunni ajatempel.
4. Vaikekonstruktor TIME
5. Tunnid muutuvad.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Koodi selgitus:

1. Klassimääratlus tegevusest
2. Kestust määravad ajatemplid
3. Kõik ajatemplid lähtestatakse vaikekonstruktoris 0-ks

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 skannimise lähtepunkt massiivi.
3. Initsialiseerimisindeksit kasutatakse juhuslike ajatemplite määramiseks.
4. Tegevusobjektide massiiv eraldatakse dünaamiliselt uue operaatori abil.
5. Ajastatud kursor määrab ahnuse praeguse baasasukoha.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Koodi selgitus:

1. Planeerija konstruktor – planeerija klassi definitsiooni 2. osa.
2. Vaadeldav indeks määrab praeguse skannimise praeguse alguse.
3. Praegune ahne ulatus on alguses määratlemata.

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. Silmus for iga hetkel ajastatud tegevuse algus- ja lõpuajad lähtestamiseks.
2. Algusaja lähtestamine.
3. Lõpuaja lähtestamine alati pärast või täpselt algustunnil.
4. Silumisavaldus eraldatud kestuste printimiseks.

	public:
   		 Activity * activity_select(int);
};

Koodi selgitus:

1. 4. osa – planeerija klassi määratluse viimane osa.
2. Tegevuse valimise funktsioon võtab aluseks lähtepunktiindeksi ja jagab ahne otsingu ahneteks alamprobleemideks.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
… 

1. Kasutades ulatuse eraldusvõime operaatorit (::), esitatakse funktsiooni definitsioon.
2. Vaadeldav indeks on väärtuse järgi kutsutav indeks. Greedy_extent on initsialiseeritud lihtsalt 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 on piiratud tegevuste arvuga.
2. Praeguse tegevuse algusaegu kontrollitakse ajakavana enne, kui vaadeldav tegevus (antud indeksi järgi) lõppeb.
3. Niikaua kui võimalik, prinditakse valikuline silumisavaldus.
4. Liikuge tegevuste massiivi järgmisele registrile

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Koodi selgitus:

1. Tingimused kontrollivad, kas kõik tegevused on kaetud.
2. Kui ei, saate oma ahnuse taaskäivitada, võttes praeguseks punktiks vaadeldava indeksi. See on rekursiivne samm, mis probleemipüstitust ahnelt poolitab.
3. Kui jah, naaseb see helistaja juurde, 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 käivitamiseks.
2. Moodustatakse uus plaanija.
3. Tegevuse valimise funktsioon, mis tagastab osuti tüüpi tegevus tuleb helistajale tagasi pärast ahne otsingu lõppemist.

Väljund:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

Ahne tehnika piirangud

See ei sobi ahnete probleemide jaoks, kus on vaja lahendust igale alamprobleemile, näiteks sortimisele.

Sellistes Greedy algoritmi praktikaülesannetes võib Greedy meetod olla vale; halvimal juhul viia isegi mitteoptimaalse lahenduseni.

Seetõttu on ahnete algoritmide miinuseks see, et ei tea, mis praegusest ahnusest ees ootab.

Allpool on kujutatud Greedy meetodi puudust:

Siin puuna näidatud ahne skannimise korral (kõrgem väärtus, suurem ahnus) võtab algoritmi olek väärtusega 40 järgmise väärtusena tõenäoliselt 29. Lisaks lõpeb selle ülesanne 12-ga. See on väärtus 41.

Kui aga algoritm valis mitteoptimaalse tee või võttis kasutusele vallutusstrateegia. siis 25-le järgneks 40 ja üldine kulude paranemine oleks 65, mis on ebaoptimaalse otsusena 24 punkti kõrgem.

Ahne näited Algorithms

Enamik võrgualgoritme kasutab ahnet lähenemist. Siin on loetelu mõnest Greedy algoritmi näidetest:

• Primi minimaalse ulatuva puu algoritm
• Reisiva müügimehe probleem
• Graafik – kaardi värvimine
• Kruskali minimaalne ulatuva puu algoritm
• Dijkstra minimaalne ulatuva puu algoritm
• Graafik – tipukate
• Seljakoti probleem
• Probleem töö planeerimisel

kokkuvõte

Kokkuvõtteks võib öelda, et artikkel defineeris ahne paradigma, näitas, kuidas ahne optimeerimine ja rekursioon võivad aidata teil kuni punktini parimat lahendust leida. Greedy algoritmi kasutatakse paljudes keeltes probleemide lahendamisel laialdaselt ahne algoritmina Python, C, C#, PHP, Javajne. Ahne algoritmi näite tegevuste valikut kirjeldati kui strateegilist probleemi, mis võib ahne lähenemisviisi kasutades saavutada maksimaalse läbilaskevõime. Lõpuks selgitati ahne lähenemisviisi kasutamise puudusi.