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

A mohó megközelítés megértéséhez gyakorlati ismeretekkel kell rendelkeznie a rekurzióról és a kontextusváltásról. Ez segít megérteni, hogyan kell nyomon követni a kódot. A mohó paradigmát a saját szükséges és elégséges állításai alapján határozhatja meg.

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

• Minden lépésenkénti megoldásnak a problémát a legjobban elfogadott megoldás felé kell strukturálnia.
• Elegendő, ha a probléma strukturálása véges számú mohó lépésben meg tud állni.

Folytatva az elméletalkotást, írjuk le a Torkos keresési megközelítéshez kapcsolódó történelmet.

Torkosság története Algorithms

Íme a mohó algoritmusok fontos mérföldköve:

• Az 1950-es években mohó algoritmusokat alkottak meg sok gráfséta algoritmushoz.
• Esdger Djikstra úgy alkotta meg az algoritmust, hogy minimális átívelő fákat hozzon létre. Célja volt, hogy lerövidítse a holland fővároson, Amszterdamon belüli útvonalakat.
• Ugyanebben az évtizedben a Prim és a Kruskal olyan optimalizálási stratégiákat ért el, amelyek az útvonalköltségek minimalizálásán alapultak a mérlegelt útvonalak mentén.
• A '70-es években amerikai kutatók, Cormen, Rivest és Stein a mohó megoldások rekurzív alstruktúráját javasolták az algoritmusok klasszikus bevezetőjében.
• A Greedy keresési paradigmát 2005-ben a NIST rekordokban egy másik típusú optimalizálási stratégiaként regisztrálták.
• Eddig a webet futtató protokollok, mint például az OSPF (Open-shortest-path-first) és sok más hálózati csomagkapcsolási protokoll, a mohó stratégiát használják a hálózaton töltött idő minimalizálására.

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

A logikát a legegyszerűbb formájában a „kapzsi” vagy a „nem mohó” kifejezésre vezették le. Ezeket az állításokat az algoritmus egyes szakaszaiban való előrelépéshez alkalmazott megközelítés határozta meg.

Például Djikstra algoritmusa lépésenkénti mohó stratégiát alkalmazott, amely költségfüggvény kiszámításával azonosította a gazdagépeket az interneten. A költségfüggvény által visszaadott érték határozza meg, hogy a következő útvonal „mohó” vagy „nem mohó”.

Röviden, egy algoritmus megszűnik mohó lenni, ha bármely szakaszában olyan lépést tesz, amely nem lokálisan mohó. A kapzsi problémák megállnak a kapzsiság további terjedelme nélkül.

A mohó algoritmus jellemzői

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

• Van egy rendezett lista az erőforrásokról, költségekkel vagy érték-hozzárendelésekkel. Ezek számszerűsítik a rendszer korlátait.
• Ön a maximális mennyiségű erőforrást fogja igénybe venni a korlátozás hatálya alatt.
• Például egy tevékenységütemezési probléma esetén az erőforrásköltségek órákban vannak megadva, és a tevékenységeket soros sorrendben kell végrehajtani.

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

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

• A mohó megközelítésnek van néhány kompromisszuma, ami alkalmassá teheti az optimalizálásra.
• Az egyik kiemelkedő ok az, hogy azonnal elérjük a legvalószínűbb megoldást. A tevékenységkiválasztási feladatban (magyarázat alább), ha több tevékenység is elvégezhető az aktuális tevékenység befejezése előtt, akkor ezek a tevékenységek ugyanazon időn belül elvégezhetők.
• Egy másik ok a probléma rekurzív felosztása egy feltétel alapján, anélkül, hogy az összes megoldást kombinálni kellene.
• A tevékenységkiválasztási feladatban a „rekurzív osztás” lépést úgy érjük el, hogy egy elemlistát csak egyszer szkennelünk, és figyelembe veszünk bizonyos tevékenységeket.

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

A tevékenységütemezési példában minden tevékenységhez van „kezdési” és „befejezési” időpont. Minden tevékenység egy számmal van indexelve referenciaként. Két tevékenységi kategória van.

1. figyelembe vett tevékenység: a tevékenység, amely az a referencia, amelyből egynél több fennmaradó tevékenység elvégzésének képességét elemzi.
2. fennmaradó tevékenységek: tevékenységek egy vagy több indexen a vizsgált tevékenység előtt.

A teljes időtartam megadja a tevékenység elvégzésének költségét. Azaz (befejezés – kezdés) megadja számunkra az időtartamot, mint egy tevékenység költségét.

Meg fogja tanulni, hogy a mohó mérték a hátralévő tevékenységek száma, amelyeket egy megfontolt tevékenység ideje alatt elvégezhet.

Archia Mohó megközelítés tectúrája

1. LÉPÉS) Vizsgálja meg a tevékenységi költségek listáját, kezdve a 0 indexszel mint figyelembe vett Index.

2. LÉPÉS) Ha több tevékenységet is be lehet fejezni addigra, a vizsgált tevékenység befejeződik, kezdje el keresni egy vagy több fennmaradó tevékenységet.

3. LÉPÉS) Ha nincs több hátralévő tevékenység, az aktuális 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 már nincs hátra tevékenység, folytassa a 4. lépéssel.

4. LÉPÉS ) Adja vissza a figyelembe vett indexek unióját. Ezek azok az aktivitási indexek, amelyeket az átviteli teljesítmény maximalizálására használunk.

Kód 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 biztosított 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. A streamelési műveletek névtere.
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. A tevékenységből származó osztálydefiníció
2. Időtartamot meghatározó időbélyegek
3. Minden időbélyeg 0-ra inicializálódik az alapértelmezett konstruktorban

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 figyelembe vett index a szkennelés kiindulópontja sor.
3. Az inicializálási index véletlenszerű időbélyegek hozzárendelésére szolgál.
4. A tevékenységobjektumok tömbje dinamikusan kerül kiosztásra az új operátor segítségével.
5. Az ütemezett mutató meghatározza a mohóság jelenlegi bázishelyét.

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

A kód magyarázata:

1. Az ütemező konstruktor – az ütemező osztálydefiníció 2. része.
2. A figyelembe vett index határozza meg az aktuális vizsgálat aktuális kezdetét.
3. A jelenlegi mohó mértéke kezdetben meghatározatlan.

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

A kód magyarázata:

1. A for ciklus az aktuálisan ütemezett tevékenységek kezdési és befejezési óráinak inicializálásához.
2. Kezdési időpont inicializálása.
3. Befejezési időpont inicializálása mindig a kezdési óra után vagy pontosan a kezdési órában.
4. Hibakeresési utasítás a hozzárendelt időtartamok kinyomtatásához.

	public:
   		 Activity * activity_select(int);
};

A kód magyarázata:

1. 4. rész – az ütemező osztálydefiníciójának utolsó része.
2. A tevékenységválasztó funkció a kiindulási pont indexét veszi alapul, és a mohó küldetést mohó 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 felbontási operátor (::) használatával a függvénydefiníciót adjuk meg.
2. A figyelembe vett Index az érték által nevezett index. A greedy_extent az inicializált csak egy index a figyelembe vett index után.

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

A kód magyarázata:

1. Az alapvető logika- A mohó mértéke a tevékenységek számára korlátozódik.
2. A rendszer az aktuális tevékenység kezdési óráit ütemezhetőként ellenőrzi, mielőtt az érintett tevékenység (a figyelembe vett index alapján) befejeződik.
3. Amíg ez lehetséges, egy opcionális hibakeresési utasítás kerül kinyomtatásra.
4. Továbblépés a tevékenységtömb következő indexére

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

A kód magyarázata:

1. A feltételes ellenőrzi, hogy az összes tevékenységet lefedték-e.
2. Ha nem, akkor újraindíthatja a mohóját úgy, hogy aktuális pontként a figyelembe vett Indexet használja. Ez egy rekurzív lépés, amely mohón megosztja a problémafelvetést.
3. Ha igen, akkor visszatér a hívóhoz, és nincs lehetősége a kapzsiság kiterjesztésére.

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. Az ütemező meghívásához használt fő funkció.
2. Egy új ütemező példányosodik.
3. A tevékenységválasztó funkció, amely egy olyan típusú mutatót ad vissza, amely a mohó küldetés befejeztével visszajön a hívóhoz.

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

Nem alkalmas Mohó problémákra, ahol minden részproblémára, például a rendezésre megoldásra van szükség.

Az ilyen Greedy-algoritmus-gyakorlati problémákban a Greedy-módszer hibás lehet; legrosszabb esetben akár nem optimális megoldáshoz is vezethet.

Ezért a mohó algoritmusok hátránya az, hogy nem tudják, mi vár a jelenlegi mohó állapot előtt.

Az alábbiakban bemutatjuk a Greedy módszer hátrányait:

Az itt faként bemutatott mohó letapogatásban (nagyobb érték nagyobb kapzsiság) a 40-es értékű algoritmus állapota valószínűleg 29-et vesz fel következő értékként. Továbbá a küldetése 12-nél ér véget. Ez 41-et jelent.

Ha azonban az algoritmus az optimálistól eltérő utat választott, vagy hódító stratégiát választott. akkor a 25-öt 40 követné, a teljes költségjavulás pedig 65 lenne, amit 24 ponttal magasabbra értékelnek, mint szuboptimális döntést.

Példák a Greedy-re Algorithms

A legtöbb hálózati algoritmus a mohó megközelítést használja. Íme néhány példa a Greedy algoritmusra:

• Prim minimális feszítőfa algoritmusa
• Utazó eladó probléma
• Grafikon – Térképszínezés
• Kruskal minimális feszítőfa algoritmusa
• Dijkstra minimális feszítőfa algoritmusa
• Grafikon – Csúcsborító
• Hátizsák probléma
• Munkaütemezési probléma

Összegzésként

Összefoglalva, a cikk meghatározta a mohó paradigmát, bemutatta, hogy a mohó optimalizálás és rekurzió hogyan segíthet egy bizonyos pontig a legjobb megoldás megtalálásában. A Greedy algoritmust sok nyelven széles körben alkalmazzák problémamegoldásra Greedy algoritmusként Python, C, C#, PHP, Javastb. A Greedy algoritmus példájának tevékenységválasztását stratégiai problémaként írták le, amely a mohó megközelítéssel maximális áteresztőképességet tud elérni. Végül a mohó megközelítés alkalmazásának hátrányait magyarázták meg.