Mohó algoritmus példával: Mi az, módszer és megközelítés

Mi az a mohó algoritmus?

A Mohó algoritmus rekurzívan oszt fel egy erőforrás-halmazt az adott erőforrás végrehajtás bármely szakaszában maximális azonnali elérhetősége alapján.

A mohó megközelítéssel történő problémamegoldás két szakaszból áll:

1. Az elemek listájának beolvasása
2. Optimalizálás

Mindkét szakasz párhuzamosan fut, miközben a bemeneti tömböt fokozatosan felosztják.

A mohó megközelítés követéséhez a rekurzió és a kontextusváltás ismerete segít. traca kódot. A mohó paradigma leírható egy szükséges és egy elégséges állítás párjával.

Két feltétel határozza meg a mohó paradigmát.

• Minden lépésenkénti választásnak a problémát a legmegfelelőbb megoldás felé kell terelnie.
• A problémastruktúrának véges számú mohó lépésben meg kell állnia.

Miután az elmélet a helyére került, nézzük meg a mohó keresési megközelítés mögött álló történelmet.

Torkosság története Algorithms

Íme a mohó algoritmusok történetének fontos mérföldkövei:

• A mohó algoritmusok fogalmát először az 1950-es években fogalmazták meg gráfséta algoritmusokhoz.
• Edsger Dijkstra kifejlesztette a legrövidebb útvonal algoritmusát, hogy lerövidítse az útvonalakat a holland fővároson, Amszterdamon keresztül.
• Ugyanebben az évtizedben Prim és Kruskal optimalizálási stratégiákat dolgoztak ki, amelyek minimalizálják az útvonalköltségeket a súlyozott útvonalak mentén, minimális feszítőfákat építve.
• A 70-es években az amerikai kutatók, Cormen, Leiserson, Rivest és Stein, klasszikus munkájukban a mohó megoldások rekurzív alstrukturálását írták le. Introduction to Algorithms tankönyv.
• A mohó keresési paradigmát 2005-ben a NIST feljegyzései különálló optimalizálási stratégiaként katalogizálták.
• A mai napig olyan webprotokollok, mint az OSPF (Open Shortest Path First) és számos csomagkapcsolási protokoll a mohó stratégiát alkalmazzák a hálózaton belüli átviteli idő minimalizálására.

Mohó stratégiák és döntések

A logika minden szakaszban bináris választási lehetőségre redukálódik – „kapzsi” vagy „nem kapzsi” – attól függően, hogy az algoritmus milyen irányba halad előre.

Például Dijkstra algoritmusa minden lépésben egy költségfüggvény kiértékelésével azonosítja az interneten található hosztokat. A költségfüggvény által visszaadott érték dönti el, hogy a következő útvonal „mohó” vagy „nem mohó” lesz-e.

Röviden, egy algoritmus abban a pillanatban megszűnik mohó lenni, amikor egy nem lokálisan optimális lépést tesz, és a mohó problémák akkor állnak le, amikor további mohó lépés nem lehetséges.

A mohó algoritmus jellemzői

A Greedy algoritmus fontos jellemzői a következők:

• Az erőforrások rendezett listája költség- vagy érték-hozzárendeléseket tartalmaz, amelyek számszerűsítik a rendszerre vonatkozó korlátozásokat.
• Az algoritmus a korlátozás érvényességi ideje alatt a lehető legtöbb erőforrást használja fel.
• Például egy tevékenységütemezési problémában az erőforrásköltségeket órákban mérik, és a tevékenységeket sorrendben kell végrehajtani.

Miért használjuk a mohó megközelítést?

Íme a mohó megközelítés használatának okai:

• A mohó megközelítésnek olyan kompromisszumai vannak, amelyek jól alkalmassá teszik az optimalizálásra.
• A legnyilvánvalóbb ok az, hogy azonnal megvalósítható megoldást kell előállítani. Az alább tárgyalt tevékenységkiválasztási problémában, ha több tevékenység is elfér a jelenlegi tevékenység befejezése előtt, akkor azok ugyanabban az ablakban ütemezhetők.
• Egy másik ok az, hogy egy problémát rekurzívan oszt fel egy feltétel alapján, anélkül, hogy az almegoldásokat össze kellene vonni.
• A tevékenységkiválasztási problémában a rekurzív osztási lépést úgy érjük el, hogy a listát egyszer átfutjuk, és csak a jogosult tevékenységeket vesszük figyelembe.

Hogyan oldjuk meg a tevékenységkiválasztási problémát

A tevékenységütemezési példában minden tevékenységnek van kezdési és befejezési időpontja, és egy számmal van indexelve referenciaként. Két tevékenységkategória létezik:

1. Figyelembe vett tevékenység: a referenciatevékenység, amelyből a fennmaradó tevékenységek illesztésének képességét mérik.
2. Hátralévő tevékenységek: tevékenységek egy vagy több indexen a vizsgált tevékenység előtt.

Egy tevékenység elvégzésének költsége az időtartama, amelyet a (befejezés – kezdet) képlettel számítanak ki.

A mohó mérték egyszerűen a fennmaradó tevékenységek száma, amelyek egy figyelembe vett tevékenység ideje alatt elvégezhetők.

Archia Mohó Megközelítés elmélete

Step 1) Vizsgálja át a tevékenységi költségek listáját, a 0. indexszel kezdve, mint figyelembe vett indexszel.

Step 2) Amikor a szóban forgó tevékenység végére több tevékenység is befejeződhet, keresse meg a fennmaradó tevékenységeket.

Step 3) Ha nem ütemezhető be több tevékenység, akkor a jelenlegi fennmaradó tevékenység lesz a következő figyelembe vett tevékenység. Ismételje meg az 1. és 2. lépést az új figyelembe vett tevékenységgel. Ha nem maradnak tevékenységek, folytassa a 4. lépéssel.

Step 4) Adja vissza a figyelembe vett indexek unióját — ezek azok az aktivitási indexek, amelyek maximalizálják az átviteli sebességet.

Archia Mohó Megközelítés elmélete

Code Magyarázat

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

#define MAX_ACTIVITIES 12

A kód magyarázata:

1. Tartalmazott fejlécfájlok/osztályok
2. A felhasználó által konfigurálható tevékenységek maximális száma.

using namespace std;

class TIME
{
    public:
    int hours;

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

A kód magyarázata:

1. Deklarálja a streamelési műveletek szabványos névterét.
2. A TIME osztálydefiníciója
3. Egy órás időbélyeg.
4. Egy TIME alapértelmezett konstruktor
5. Az óra változó.

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

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

A kód magyarázata:

1. Az Activity osztálydefiníciója.
2. Időbélyegek, amelyek együttesen határozzák meg az időtartamot.
3. Az alapértelmezett konstruktorban minden időbélyeg 0-ra van inicializálva.

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

A kód magyarázata:

1. Az ütemező osztálydefiníciójának 1. része.
2. A considered_index a tömb beolvasásának kiindulópontja.
3. Az init_index paraméterrel véletlenszerű időbélyegeket rendelhetünk a beállítás során.
4. Egy Activity objektumokból álló tömböt dinamikusan lefoglalunk az new operátorral.
5. Az ütemezett mutató az aktuális mohó eredményt tartalmazza.

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

A kód magyarázata:

1. Az ütemező konstruktora — az osztálydefiníció 2. része.
2. A considered_index az aktuális vizsgálat kezdetét jelöli.
3. A mohó mérték kezdetben nincs meghatározva.

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;

A kód magyarázata:

1. Egy for ciklus inicializálja minden ütemezett tevékenység kezdési és befejezési óráját.
2. Inicializálja a kezdési időpontot.
3. A befejezési időpontot a kezdő órához vagy azt követően inicializálja.
4. Egy hibakeresési utasítás kinyomtatja a lefoglalt időtartamokat.

	public:
   		 Activity * activity_select(int);
};

A kód magyarázata:

1. 4. rész — az Ütemező osztály definíciójának befejező része.
2. Az activity_select() egy kezdő indexet vesz alapul, és a mohó küldetést részproblémákra osztja.

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

1. A hatókör-feloldási operátor (::) a függvénydefiníciót a Scheduler osztályhoz kapcsolja.
2. A considered_index értékenként kerül átadásra, a greedy_extent pedig közvetlenül utána az indexre inicializálódik.

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;
...

A kód magyarázata:

1. Az alapvető logika az, hogy a mohó mérték MAX_ACTIVITIES-ben van korlátozva.
2. Az aktuális tevékenység kezdési óráját összevetik a figyelembe vett tevékenység befejezési órájával.
3. Amíg a feltétel fennáll, egy opcionális hibakeresési utasítás kerül kiírásra.
4. A mohó kiterjedés ezután a tevékenységtömb következő indexére lép.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

A kód magyarázata:

1. A feltételes feltétel ellenőrzi, hogy minden tevékenység lefedett-e.
2. Ha nem, akkor az algoritmus újraindítja a mohó küldetést az aktuális indextől – ez egy rekurzív lépés, amely mohón felosztja a problémát.
3. Ha igen, az irányítás visszakerül a hívóhoz, a kapzsiság kiterjesztésének lehetősége nélkül.

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

A kód magyarázata:

1. A fő függvény meghívja az ütemezőt.
2. Egy új Ütemező objektum példányosításra kerül.
3. Az activity_select() függvény egy Activity pointert ad vissza a hívónak, miután a mohó küldetés véget ért.

output:

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

A mohó technika korlátai

A mohó megközelítés nem alkalmas olyan problémákra, amelyek minden részproblémára optimális megoldást igényelnek, például a rendezésre.

Ilyen esetekben a mohó módszer hibás lehet – a legrosszabb esetben nem optimális megoldást eredményez.

A mohó algoritmusok fő hátránya, hogy anélkül választanak, hogy tudnák, mi vár a jelenlegi mohó állapotra.

Az alábbi ábra a mohó módszer ezen hátrányát szemlélteti.

Az itt faként ábrázolt mohó letapogatásban (magasabb érték nagyobb mohóságot jelent) egy 40-es értékű algoritmus a 29-et választaná következőként, majd 12-nél fejezné be, így összesen 41 lenne.

Ezzel szemben egy oszd meg és uralkodj stratégia a 25-öt 40-nel követné, így összesen 65 lenne, ami 24 ponttal magasabb, mint a helyileg kapzsi választás.

Példák a Greedy-re Algorithms

A legtöbb hálózati algoritmus mohó megközelítésen alapul. Gyakori mohó algoritmus példák:

• Prim minimális feszítőfa algoritmusa
• Utazó Ügynök Probléma (Közelítő)
• Grafikon térkép színezése
• Kruskal minimális feszítőfa algoritmusa
• Dijkstra legrövidebb út algoritmusa
• Gráf csúcsborítás
• Hátizsák probléma
• Munkarendek határidőkkel

GYIK