Ahne algoritmi esimerkillä: Mikä on, menetelmä ja lähestymistapa

Ymmärtääksesi ahneen lähestymistavan, sinulla on oltava työtiedot rekursiosta ja kontekstin vaihtamisesta. Tämä auttaa sinua ymmärtämään, kuinka koodi jäljitetään. Voit määritellä ahneen paradigman omien tarpeellisten ja riittävien väittämiesi perusteella.

Kaksi ehtoa määrittelee ahneuden paradigman.

• Jokaisen vaiheittaisen ratkaisun on rakennettava ongelma kohti sen parhaiten hyväksyttyä ratkaisua.
• Riittää, jos ongelman strukturointi voi pysähtyä äärellisessä määrässä ahneita vaiheita.

Teorisoinnin jatkuessa kuvataanpa ahneeseen etsintään liittyvää historiaa.

Greedyn historia Algorithms

Tässä on ahneiden algoritmien tärkeä maamerkki:

• Ahneita algoritmeja kehitettiin monille kaavion kävelyalgoritmeille 1950-luvulla.
• Esdger Djikstra käsitteli algoritmin luomaan mahdollisimman vähän virittäviä puita. Hänen tavoitteenaan oli lyhentää Alankomaiden pääkaupungin Amsterdamin reittien jänneväliä.
• Samalla vuosikymmenellä Prim ja Kruskal saavuttivat optimointistrategiat, jotka perustuivat reittikustannusten minimoimiseen punnituilla reiteillä.
• 70-luvulla amerikkalaiset tutkijat Cormen, Rivest ja Stein ehdottivat ahneiden ratkaisujen rekursiivista alirakennetta klassisessa algoritmien johdannossa.
• Greedy-hakuparadigma rekisteröitiin erilaiseksi optimointistrategiaksi NIST-tietueisiin vuonna 2005.
• Tähän asti verkkoa pyörittävät protokollat, kuten open-shortest-path-first (OSPF) ja monet muut verkkopakettien kytkentäprotokollat ​​käyttävät ahneita strategiaa verkossa vietetyn ajan minimoimiseksi.

Ahneet strategiat ja päätökset

Logiikka helpoimmassa muodossaan tiivistettiin "ahneeksi" tai "ei ahneeksi". Nämä lausunnot määriteltiin kunkin algoritmivaiheen etenemiseen käytetyllä lähestymistavalla.

Esimerkiksi Djikstran algoritmi käytti portaittain ahneita strategiaa, joka tunnistaa isännät Internetissä laskemalla kustannusfunktion. Kustannusfunktion palauttama arvo määritti, onko seuraava polku "ahne" vai "ei-ahne".

Lyhyesti sanottuna algoritmi lakkaa olemasta ahne, jos se jossain vaiheessa ottaa askeleen, joka ei ole paikallisesti ahne. Ahneet ongelmat pysähtyvät ilman ahneuden laajuutta.

Greedy-algoritmin ominaisuudet

Greedy-algoritmin tärkeät ominaisuudet ovat:

• Siellä on järjestetty luettelo resursseista kustannus- tai arvomäärityksineen. Nämä mittaavat järjestelmän rajoituksia.
• Käytät enimmäismäärän resursseja rajoituksen voimassaoloaikana.
• Esimerkiksi toimintojen ajoitusongelmassa resurssikustannukset ovat tunteina ja toiminnot on suoritettava sarjajärjestyksessä.

Miksi käyttää Greedy-lähestymistapaa?

Tässä ovat syyt ahneeseen lähestymistapaan:

• Ahneella lähestymistavalla on muutamia kompromisseja, jotka voivat tehdä siitä sopivan optimointiin.
• Yksi näkyvä syy on toteuttamiskelpoisin ratkaisu välittömästi. Aktiviteetin valintatehtävässä (selostettu alla), jos enemmän toimintoja voidaan tehdä ennen nykyisen toiminnon lopettamista, nämä toiminnot voidaan suorittaa samassa ajassa.
• Toinen syy on jakaa ongelma rekursiivisesti ehdon perusteella ilman, että kaikkia ratkaisuja tarvitsee yhdistää.
• Aktiviteetin valintatehtävässä "rekursiivinen jako" -vaihe saavutetaan skannaamalla luettelo kohteista vain kerran ja huomioimalla tietyt toiminnot.

Kuinka ratkaista aktiviteetin valintaongelma

Toiminnan ajoitusesimerkissä jokaiselle toiminnalle on "aloitus" ja "lopetusaika". Jokainen toiminto on indeksoitu viitenumerolla. Toimintakategorioita on kaksi.

1. harkittua toimintaa: on toiminto, joka on viite, jonka perusteella analysoidaan kyky tehdä useampi kuin yksi jäljellä oleva toiminto.
2. jäljellä olevat aktiviteetit: toiminnot yhdellä tai useammalla indeksillä ennen tarkasteltua toimintaa.

Kokonaiskesto antaa toiminnon suorittamisen kustannukset. Eli (lopetus – aloitus) antaa meille keston toiminnan kustannuksella.

Opit, että ahneus on jäljellä olevien toimintojen määrä, jotka voit suorittaa harkitun toiminnan aikana.

ArchiGreedy-lähestymistavan

VAIHE 1) Skannaa luettelo toiminnan kustannuksista alkaen indeksistä 0 tarkasteltuna indeksinä.

VAIHE 2) Kun useampia toimintoja voidaan suorittaa määräaikaan mennessä, harkittu toiminto päättyy, aloita yhden tai useamman jäljellä olevan toiminnon etsiminen.

VAIHE 3) Jos jäljellä ei ole enää toimintoja, nykyisestä jäljellä olevasta toiminnasta tulee seuraava harkittu toiminta. Toista vaiheet 1 ja 2 uuden harkittavan toiminnon kanssa. Jos toimintoja ei ole jäljellä, siirry vaiheeseen 4.

VAIHE 4) Palauta harkittujen indeksien liitto. Nämä ovat aktiivisuusindeksejä, joita käytetään suorituskyvyn maksimoimiseen.

Koodin selitys

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

#define MAX_ACTIVITIES 12

Koodin selitys:

1. Mukana otsikkotiedostot/luokat
2. Enimmäismäärä käyttäjän tarjoamia toimintoja.

using namespace std;

class TIME
{
    public:
    int hours;

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

Koodin selitys:

1. Suoratoistotoimintojen nimiavaruus.
2. Luokan määritelmä kohteelle TIME
3. Tunnin aikaleima.
4. TIME oletuskonstruktori
5. Tuntimäärä vaihtelee.

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

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

Koodin selitys:

1. Luokan määritelmä toiminnasta
2. Aikaleimat, jotka määrittävät keston
3. Kaikki aikaleimat alustetaan 0:ksi oletuskonstruktorissa

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Koodin selitys:

1. Aikataulun luokan määritelmän osa 1.
2. Tarkoitettu indeksi on aloituspiste skannaamiseen ryhmä.
3. Alustusindeksiä käytetään satunnaisten aikaleimien määrittämiseen.
4. Joukko aktiviteettiobjekteja allokoidaan dynaamisesti käyttämällä uutta operaattoria.
5. Ajastettu osoitin määrittää ahneuden nykyisen tukikohdan.

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

Koodin selitys:

1. Aikataulun konstruktori – osa 2 ajoitusluokan määritelmästä.
2. Tarkasteltu indeksi määrittää nykyisen skannauksen nykyisen alun.
3. Nykyinen ahne laajuus on alussa määrittelemätön.

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);
 }
…
…

Koodin selitys:

1. A for-silmukka alustaa jokaisen tällä hetkellä ajoitetun toiminnon aloitus- ja päättymisajat.
2. Aloitusajan alustus.
3. Päättymisajan alustus aina alkamistunnin jälkeen tai täsmälleen sen jälkeen.
4. Virheenkorjauslausunto, jolla tulostetaan varatut kestoajat.

	public:
   		 Activity * activity_select(int);
};

Koodin selitys:

1. Osa 4 – aikataulun luokan määritelmän viimeinen osa.
2. Aktiviteetin valintatoiminto ottaa lähtökohtaindeksin pohjaksi ja jakaa ahneen tehtävän ahneisiin aliongelmiin.

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

1. Toimintomäärittely tarjotaan käyttämällä kaukoresoluutiooperaattoria (::).
2. Tarkasteltu indeksi on arvon mukaan kutsuttu indeksi. Greedy_extent on alustettu vain indeksi tarkasteltavan indeksin jälkeen.

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++;
    	}
…
...

Koodin selitys:

1. Ydinlogiikka- Ahne laajuus rajoittuu toimintojen määrään.
2. Nykyisen toiminnon alkamisajat tarkistetaan ajoitetuiksi ennen kuin tarkasteltu toiminto (joka on annettu tarkastelussa) päättyy.
3. Valinnainen virheenkorjauslausunto tulostetaan niin kauan kuin mahdollista.
4. Siirry seuraavaan hakemistoon toimintotaulukossa

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Koodin selitys:

1. Ehdollinen tarkastaa, onko kaikki toiminnot katettu.
2. Jos ei, voit käynnistää ahneuksesi uudelleen tarkasteltavalla indeksillä nykyisenä pisteenä. Tämä on rekursiivinen askel, joka jakaa ongelman ahneesti.
3. Jos kyllä, se palaa soittajalle ilman mahdollisuutta laajentaa ahneutta.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Koodin selitys:

1. Päätoiminto, jota käytetään ajastimen kutsumiseen.
2. Uusi ajoitus on instantoitu.
3. Aktiviteetin valintatoiminto, joka palauttaa osoittimen, jonka tyyppi aktiviteetti palaa soittajalle, kun ahne tehtävä on ohi.

lähtö:

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

Greedy Techniquen rajoitukset

Se ei sovellu ahneisiin ongelmiin, joissa jokaiseen osaongelmaan, kuten lajitteluun, tarvitaan ratkaisu.

Tällaisissa Greedy-algoritmien käytännön ongelmissa Greedy-menetelmä voi olla väärä; pahimmassa tapauksessa johtaa jopa ei-optimaaliseen ratkaisuun.

Siksi ahneiden algoritmien haittana on se, että ei tiedetä, mitä nykyisen ahneuden tilan edessä on.

Alla on kuvaus Greedy-menetelmän haitoista:

Tässä puuna näytetyssä ahneessa skannauksessa (suurempi arvo korkeampi ahneus) algoritmin tila arvolla 40 ottaa todennäköisesti seuraavan arvon 29. Lisäksi sen tehtävä päättyy kohtaan 12. Tämä vastaa arvoa 41.

Kuitenkin, jos algoritmi valitsi optimaalisen polun tai omaksui valloitusstrategian. silloin 25:tä seuraisi 40, ja kokonaiskustannusten parannus olisi 65, mikä on 24 pistettä korkeampi kuin optimaalinen päätös.

Esimerkkejä Greedystä Algorithms

Useimmat verkkoalgoritmit käyttävät ahneutta. Tässä on luettelo muutamasta Greedy-algoritmiesimerkistä:

• Primin minimaalisen virittävän puun algoritmi
• Matkustavan myyjän ongelma
• Kaavio – Kartan väritys
• Kruskalin minimaalisen virittävän puun algoritmi
• Dijkstran minimaalisen virittävän puun algoritmi
• Kaavio – Vertex Cover
• Reppu ongelma
• Työn aikataulutusongelma

Yhteenveto

Yhteenvetona artikkelissa määriteltiin ahne paradigma, osoitti kuinka ahne optimointi ja rekursio voivat auttaa sinua löytämään parhaan ratkaisun tiettyyn pisteeseen asti. Greedy-algoritmia käytetään laajalti ongelmanratkaisussa monilla kielillä Greedy-algoritmina Python, C, C#, PHP, Javajne. Greedy-algoritmiesimerkin toimintojen valinta kuvattiin strategiseksi ongelmaksi, joka voisi saavuttaa suurimman suorituskyvyn ahneella lähestymistavalla. Lopuksi selitettiin ahneen lähestymistavan käytön haitat.