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

Mikä on ahne algoritmi?

A Ahne algoritmi jakaa rekursiivisesti joukon resursseja kyseisen resurssin suurimman välittömän saatavuuden perusteella missä tahansa suoritusvaiheessa.

Ahneen lähestymistavan ongelman ratkaiseminen tapahtuu kahdessa vaiheessa:

1. Kohdeluettelon skannaus
2. Optimointi

Molemmat vaiheet toimivat rinnakkain, kun syöttömatriisia jaetaan asteittain.

Ahneen lähestymistavan noudattamiseksi rekursion ja kontekstinvaihdon tuntemus auttaa sinua tracAhne paradigma voidaan kuvata välttämättömän ja riittävän lauseen parilla.

Kaksi ehtoa määrittelee ahneuden paradigman.

• Jokaisen askelmaisen valinnan on ohjattava ongelmaa kohti parhaiten hyväksyttävää ratkaisua.
• Ongelmarakenteen on pysähdyttävä äärellisen määrän ahneiden askelten jälkeen.

Teorian pohjalta tarkastellaan ahneen hakumenetelmän historiaa.

Greedyn historia Algorithms

Tässä ovat tärkeät virstanpylväät ahneiden algoritmien historiassa:

• Ahneita algoritmeja käsitteellistettiin ensimmäisen kerran graafikävelyalgoritmeja varten 1950-luvulla.
• Edsger Dijkstra kehitti lyhimmän reitin algoritminsa lyhentääkseen reittejä Alankomaiden pääkaupungin Amsterdamin läpi.
• Samalla vuosikymmenellä Prim ja Kruskal kehittivät optimointistrategioita, jotka minimoivat polkukustannukset painotetuilla reiteillä rakentaakseen mahdollisimman vähän virittäviä puita.
• 70-luvulla amerikkalaiset tutkijat Cormen, Leiserson, Rivest ja Stein kuvasivat ahneiden ratkaisujen rekursiivista alirakenteiden luomista klassisessa teoksessaan Introduction to Algorithms oppikirja.
• Ahne hakuparadigma luetteloitiin erilliseksi optimointistrategiaksi NIST-tietueissa vuonna 2005.
• Tähän päivään asti verkkoprotokollat, kuten Open Shortest Path First (OSPF) ja monet pakettikytkentäprotokollat, käyttävät ahneutta strategiaa verkon siirtoajan minimoimiseksi.

Ahneet strategiat ja päätökset

Logiikka supistuu binääriseen valintaan jokaisessa vaiheessa — ”ahne” tai ”ei ahne” — algoritmin etenemissuunnan perusteella.

Esimerkiksi Dijkstran algoritmi tunnistaa internetin isännät arvioimalla kustannusfunktion jokaisessa vaiheessa. Kustannusfunktion palauttama arvo ratkaisee, onko seuraava polku "ahne" vai "ei-ahne".

Lyhyesti sanottuna algoritmi lakkaa olemasta ahne heti, kun se ottaa askeleen, joka ei ole lokaalisti optimaalinen, ja ahneet ongelmat pysähtyvät, kun ahneet askeleet eivät ole enää mahdollisia.

Greedy-algoritmin ominaisuudet

Greedy-algoritmin tärkeät ominaisuudet ovat:

• Järjestetty resurssiluettelo sisältää kustannus- tai arvoattribuutioita, jotka kvantifioivat järjestelmän rajoitteet.
• Algoritmi käyttää resursseja rajoitteen voimassaoloajassa niin paljon kuin mahdollista.
• Esimerkiksi aktiviteettien aikataulutusongelmassa resurssikustannukset mitataan tunneissa ja aktiviteetit on suoritettava peräkkäisessä järjestyksessä.

Miksi käyttää ahneutta?

Tässä ovat syyt ahneeseen lähestymistapaan:

• Ahneella lähestymistavalla on kompromisseja, jotka tekevät siitä hyvin sopivan optimointiin.
• Ilmeisin syy on tuottaa mahdollinen ratkaisu välittömästi. Alla käsiteltävässä aktiviteettien valintaongelmassa, jos useampi aktiviteetti mahtuu ennen nykyisen aktiviteetin päättymistä, ne voidaan ajoittaa samaan ikkunaan.
• Toinen syy on, että se jakaa ongelman rekursiivisesti ehdon perusteella ilman tarvetta yhdistää aliratkaisuja.
• Aktiviteettien valintaongelmassa rekursiivinen jakolaskuvaihe saavutetaan käymällä lista läpi kerran ja ottamalla huomioon vain kelvolliset aktiviteetit.

Kuinka ratkaista aktiviteetin valintaongelma

Aktiviteettien aikataulutusesimerkissä jokaisella aktiviteetilla on alkamis- ja päättymisaika, ja ne on merkitty numerolla viitteenä. Aktiviteetit voidaan jakaa kahteen luokkaan:

1. Harkittu toiminta: vertailuaktiviteetti, josta mitataan kykyä sovittaa lisää jäljellä olevia aktiviteetteja.
2. Jäljellä olevat aktiviteetit: toiminnot yhdellä tai useammalla indeksillä ennen tarkasteltua toimintaa.

Toiminnan suorittamisen kustannukset ovat sen kesto, joka lasketaan kaavalla (loppu – alku).

Ahne laajuus on yksinkertaisesti jäljellä olevien toimintojen lukumäärä, jotka voidaan suorittaa tarkasteltavan toiminnon ajassa.

ArchiGreedy Approach -tektikko

Vaihe 1) Käy läpi toimintakustannusten luettelo alkaen indeksistä 0 tarkasteltuna indeksinä.

Vaihe 2) Kun useampia aktiviteetteja voi valmistua tarkasteltavan aktiviteetin päättymiseen mennessä, etsi jäljellä olevat aktiviteetit.

Vaihe 3) Jos enempää aktiviteetteja ei voida ajoittaa, nykyisestä jäljellä olevasta aktiviteetista tulee seuraava harkittava aktiviteetti. Toista vaiheet 1 ja 2 uudella harkittavalla aktiviteetilla. Jos aktiviteetteja ei ole jäljellä, siirry vaiheeseen 4.

Vaihe 4) Palauta tarkasteltujen indeksien yhdistelmä — nämä ovat aktiivisuusindeksejä, jotka maksimoivat läpimenon.

ArchiGreedy Approach -tektikko

Code Selitys

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

#define MAX_ACTIVITIES 12

Koodin selitys:

1. Mukana otsikkotiedostot/luokat
2. Käyttäjän määrittämien aktiviteettien enimmäismäärä.

using namespace std;

class TIME
{
    public:
    int hours;

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

Koodin selitys:

1. Määrittää suoratoistotoimintojen vakionimiavaruuden.
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. Activityn luokan määritelmä.
2. Aikaleimat, jotka yhdessä määrittävät keston.
3. Kaikki aikaleimat alustetaan arvoon 0 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. considered_index on taulukon skannauksen aloituskohta.
3. init_index-muuttujaa käytetään satunnaisten aikaleimojen määrittämiseen asennuksen aikana.
4. Activity-objektien taulukko allokoidaan dynaamisesti new-operaattorilla.
5. Ajoitettu osoitin sisältää nykyisen ahneen tuloksen.

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

Koodin selitys:

1. Aikatauluttajan konstruktori — luokan määritelmän osa 2.
2. considered_index merkitsee nykyisen skannauksen alkua.
3. Ahneuden laajuus on aluksi 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);
 }
&#8230;
&#8230;

Koodin selitys:

1. For-silmukka alustaa jokaisen ajoitetun toiminnon aloitus- ja lopetusajat.
2. Alustaa aloitusajan.
3. Alustaa lopetusajan joko aloitustunnin mukaiseksi tai sen jälkeen.
4. Virheenjäljityslauseke tulostaa varatut kestot.

	public:
   		 Activity * activity_select(int);
};

Koodin selitys:

1. Osa 4 — Scheduler-luokan määrittelyn viimeinen osa.
2. activity_select() ottaa lähtöindeksin pohjaksi ja jakaa ahneen tehtävän aliohjelmiin.

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

1. Soveltamisalan erotusoperaattori (::) linkittää funktion määritelmän Scheduler-luokkaan.
2. considered_index välitetään arvon mukaan, ja greedy_extent alustetaan välittömästi sitä seuraavaksi indeksiksi.

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++;
    	}
&#8230;
...

Koodin selitys:

1. Ydinlogiikka — ahneen toiminnan laajuus on rajattu arvoon MAX_ACTIVITIES.
2. Nykyisen toiminnon aloitusaikaa verrataan tarkasteltavan toiminnon päättymisaikaan.
3. Niin kauan kuin ehto on voimassa, tulostetaan valinnainen debug-lauseke.
4. Ahne laajuus siirtyy sitten aktiviteettitaulukon seuraavaan indeksiin.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Koodin selitys:

1. Ehdollinen tarkistus tarkistaa, onko kaikki toiminnot käsitelty.
2. Jos ei, algoritmi käynnistää ahneen tehtävän uudelleen nykyisestä indeksistä – rekursiivinen vaihe, joka jakaa ongelman ahneesti.
3. Jos kyllä, kontrolli palautuu soittajalle eikä ahneudelle ole enää mahdollisuuksia.

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

Koodin selitys:

1. Pääfunktio kutsuu ajastinta.
2. Uusi Scheduler-objekti luodaan.
3. activity_select()-funktio palauttaa kutsujalle Activity-osoittimen, kun ahne tehtävä päättyy.

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

Ahne lähestymistapa ei sovellu ongelmiin, jotka vaativat optimaalisen ratkaisun jokaiselle osaongelmalle, kuten lajitteluun.

Tällaisissa tapauksissa ahne menetelmä voi olla väärä – pahimmassa tapauksessa se tuottaa epäoptimaalisen ratkaisun.

Ahneiden algoritmien keskeinen haittapuoli on, että ne valitsevat tietämättä, mitä on edessä nykyisen ahneen tilan edessä.

Alla oleva kaavio havainnollistaa ahneen menetelmän tätä haittaa.

Tässä puuna esitetyssä ahneessa skannauksessa (korkeampi arvo tarkoittaa suurempaa ahneutta) algoritmi arvolla 40 valitsisi seuraavaksi luvun 29 ja päättäisi sitten lukuun 12, jolloin kokonaismääräksi tulisi 41.

Sitä vastoin hajoita ja hallitse -strategiassa luku 25 seuraisi 40:llä, jolloin kokonaisluku olisi 65, mikä on 24 pistettä enemmän kuin paikallisesti ahneessa vaihtoehdossa.

Esimerkkejä Greedystä Algorithms

Useimmat verkkoalgoritmit perustuvat ahneuteen. Yleisiä ahneiden algoritmien esimerkkejä ovat:

• Primin pienimmän virityspuun algoritmi
• Myyntimiehen ongelma (likimääräinen)
• Graafikartan väritys
• Kruskalin pienimmän virityspuun algoritmi
• Dijkstran lyhimmän polun algoritmi
• Graafin kärkipään peite
• Reppu ongelma
• Työjärjestys määräaikojen kanssa

UKK