Kapzsi algoritmus példákkal: Kapzsi módszer & Megközelítés

Tartalomjegyzék:

Anonim

Mi az a kapzsi algoritmus?

A Kapzsi algoritmusban egy erőforrás-készlet rekurzívan fel van osztva az adott erőforrás maximális, azonnali rendelkezésre állása alapján a végrehajtás bármely szakaszában.

A kapzsi megközelítésen alapuló probléma megoldása két szakaszból áll

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

Ezeket a szakaszokat párhuzamosan tárgyalja ez a kapzsi algoritmus oktatóanyag, a tömb felosztása során.

A kapzsi megközelítés megértéséhez működőképes ismeretekkel kell rendelkeznie a rekurzióról és a kontextusváltásról. Ez segít megérteni a kód nyomon követését. Meghatározhatja a kapzsi paradigmát saját szükséges és elégséges állításai alapján.

Két feltétel határozza meg a kapzsi 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ú kapzsi lépésben megállhat.

Az elméletek folytatásával írjuk le a kapzsi keresés megközelítéséhez kapcsolódó történelmet.

Ebben a Kapzsi algoritmus bemutatóban megtudhatja:

  • Kapzsi algoritmusok története
  • Kapzsi stratégiák és döntések
  • A kapzsi szemlélet jellemzői
  • Miért érdemes használni a kapzsi megközelítést?
  • A tevékenység kiválasztási probléma megoldása
  • A kapzsi megközelítés felépítése
  • A kapzsi algoritmusok hátrányai

Kapzsi algoritmusok története

Itt van a kapzsi algoritmusok fontos mérföldköve:

  • A kapzsi algoritmusokat az ötvenes években sok grafikonos járási algoritmus számára fogalmazták meg.
  • Esdger Djikstra koncepcionálta az algoritmust, hogy minimális átfedő fákat generáljon. Célja az útvonalak lerövidítése a holland fővárosban, Amszterdamban.
  • Ugyanebben az évtizedben Prim és Kruskal olyan optimalizálási stratégiákat értek el, amelyek a nyomon követett utak költségeinek minimalizálásán alapultak.
  • A 70-es években amerikai kutatók, Cormen, Rivest és Stein az algoritmusok könyvének klasszikus bevezetésében a kapzsi megoldások rekurzív alstrukturálását javasolták.
  • A kapzsi keresési paradigmát egy másik típusú optimalizálási stratégiaként regisztrálták a NIST nyilvántartásaiban 2005-ben.
  • A dátumig az internetet futtató protokollok, például az open-shortest-path-first (OSPF) és sok más hálózati csomagváltási protokoll a kapzsi stratégiát használják a hálózatra fordított idő minimalizálására.

Kapzsi stratégiák és döntések

A logika a legegyszerűbb formájában "mohó" vagy "nem mohó" volt. Ezeket az állításokat az egyes algoritmus-szakaszokban való előrehaladáshoz alkalmazott megközelítés határozta meg.

Például Djikstra algoritmusa lépésenkénti kapzsi stratégiát használt fel az internet gazdagépeinek azonosítására egy költségfüggvény kiszámításával. A költségfüggvény által visszaadott érték meghatározta, hogy a következő útvonal "kapzsi" vagy "nem kapzsi".

Röviden: egy algoritmus nem lesz mohó, ha bármely szakaszában megtesz egy olyan lépést, amely nem helyileg mohó. A kapzsi problémák megállnak, a kapzsiság további mértéke nélkül.

A kapzsi szemlélet jellemzői

A Greedy módszer algoritmusának fontos jellemzői a következők:

  • Rendezett erőforráslista található, költségekkel vagy érték-hozzárendelésekkel. Ezek számszerűsítik a rendszer korlátjait.
  • Az erőforrások maximális mennyiségét a korlátozás időtartama alatt veszi fel.
  • Például egy tevékenységütemezési probléma esetén az erőforrás költségei órákban vannak megadva, és a tevékenységeket soros sorrendben kell végrehajtani.

Miért érdemes használni a kapzsi megközelítést?

Itt vannak a kapzsi megközelítés okai:

  • A kapzsi megközelítésnek néhány kompromisszuma van, ami alkalmassá teheti az optimalizálásra.
  • Az egyik kiemelkedő ok a lehető legmegvalósíthatóbb megoldás azonnali elérése. A tevékenységválasztási problémában (az alábbiakban elmagyarázva), ha további tevékenységeket lehet elvégezni az aktuális tevékenység befejezése előtt, ezeket a tevékenységeket ugyanabban az idő alatt elvégezhetjük.
  • Egy másik ok az, hogy a problémát rekurzív módon osztjuk fel egy feltétel alapján, és nem szükséges az összes megoldást kombinálni.
  • A tevékenységválasztási problémában a "rekurzív felosztás" lépést úgy érjük el, hogy az elemek listáját csak egyszer szkenneljük be, és bizonyos tevékenységeket figyelembe veszünk.

A tevékenység kiválasztási probléma megoldása

A tevékenységütemezési példában minden tevékenységhez tartozik egy "kezdési" és "befejezési" idő. Minden tevékenységet hivatkozással egy szám indexel. Két tevékenységi kategória létezik.

  1. tekinthető tevékenység : az 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 elemzik.
  2. fennmaradó tevékenységek: a figyelembe vett tevékenységet megelőző egy vagy több indexű tevékenységek.

A teljes időtartam adja meg a tevékenység végrehajtásának költségeit. Vagyis (befejezés - kezdet) megadja nekünk az időtartamot, mint egy tevékenység költségét.

Megtudhatja, hogy a kapzsi mérték a fennmaradó tevékenységek száma, amelyet elvégezhet egy figyelembe vett tevékenység idején.

A kapzsi megközelítés felépítése

1. LÉPÉS)

Olvassa be a tevékenység költségeinek listáját, kezdve a 0 indexszel, mint figyelembe vett index.

2. LÉPÉS)

Amikor több tevékenység befejeződik, az érintett tevékenység befejeződik, kezdje el keresni egy vagy több megmaradt tevékenységet.

3. LÉPÉS

Ha nincs több hátralévő tevékenység, akkor az aktuális fennmaradó tevékenység lesz a következő figyelembe vett tevékenység. Ismételje meg az 1. és a 2. lépést az új figyelembe vett tevékenységgel. Ha nem marad fenn 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, amelyek az átbocsátás maximalizálására szolgálnak.

A kapzsi megközelítés építészete

Kód Magyarázat

#include#include#include#define MAX_ACTIVITIES 12

A kód magyarázata:

  1. Tartalmazott fejlécfájlokat / osztályokat
  2. A felhasználó által végzett 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 streaming műveletek névtere.
  2. A TIME osztálydefiníciója
  3. Egy órás időbélyeg.
  4. A TIME alapértelmezett konstruktor
  5. Az órák változója.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

A kód magyarázata:

  1. Osztálymeghatározás a tevékenységből
  2. Időbélyegek, amelyek meghatározzák az időtartamot
  3. Az összes 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 tekintett index a tömb szkennelésének kiindulópontja.
  3. Az inicializáló indexet véletlenszerű időbélyegek hozzárendelésére használják.
  4. Az aktivitásobjektumok tömbjét dinamikusan hozzárendelik az új operátorhoz.
  5. Az ütemezett mutató meghatározza a kapzsiság jelenlegi alaphelyét.
Scheduler(){considered_index = 0;scheduled = NULL;… …

A kód magyarázata:

  1. Az ütemező konstruktor - az ütemező osztály definíciójának 2. része.
  2. A figyelembe vett index meghatározza az aktuális vizsgálat aktuális kezdetét.
  3. A jelenlegi kapzsi mértéket a kezdetekkor még nem határozták meg.
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 a jelenleg ütemezett tevékenységek kezdési és befejezési óráinak inicializálásához.
  2. Kezdési idő inicializálása.
  3. A befejezési idő inicializálása mindig a kezdési óra után vagy pontosan abban az időpontban történik.
  4. Hibakeresési utasítás a kiosztott időtartamok kinyomtatásához.
public:Activity * activity_select(int);};

A kód magyarázata:

  1. 4. rész - az ütemező osztály definíciójának utolsó része.
  2. Az Activity select funkció egy kiindulási indexet vesz alapul, és kapzsi részproblémákra osztja a kapzsi küldetést.
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ás operátor (: :) használatával megadjuk a függvény-meghatározást.
  2. A figyelembe vett index az index szerint meghívott index. A greedy_extent csak egy index inicializálódik 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. A fő logika- A kapzsi mérték csak a tevékenységek számára korlátozódik .
  2. Az aktuális tevékenység kezdési óráit ütemezhetőként ellenőrizzük, mielőtt az adott tevékenység (a figyelembe vett index által megadott) befejeződik.
  3. Amíg ez lehetséges, nyomtat egy opcionális hibakeresési utasítást.
  4. Ugrás az aktivitási tömb következő indexére
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

A kód magyarázata:

  1. Feltételesen ellenőrzi, hogy minden tevékenység lefedett-e.
  2. Ha nem, akkor indítsa újra a kapzsiságot az aktuális indexnek tekintett Index segítségével. Ez egy rekurzív lépés, amely mohón osztja meg a problémamegállapítást.
  3. Ha igen, akkor visszatér a hívóhoz, nincs lehetőség 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ára használt fő funkció.
  2. Egy új ütemező példányos.
  3. A tevékenységválasztó funkció, amely egy típusú tevékenység mutatóját adja vissza, a kapzsi küldetés befejezése után visszatér a hívóhoz.

Kimenet:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

A kapzsi algoritmusok hátrányai

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

Ilyen kapzsi algoritmusgyakorlati problémák esetén a kapzsi módszer téves lehet; a legrosszabb esetben akár nem optimális megoldáshoz is vezethet.

Ezért a kapzsi algoritmusok hátránya, hogy nem tudják, mi áll a jelenlegi kapzsi állapot előtt.

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

Az itt faként bemutatott kapzsi beolvasásnál (magasabb érték magasabb kapzsiság) az algoritmus 40-es állapotánál valószínűleg 29 lesz a következő érték. Ezenkívül küldetése 12-kor ér véget. Ez 41-es értéket jelent.

Ha azonban az algoritmus nem optimális utat választott, vagy elfogadott egy hódító stratégiát. akkor a 25-et 40 követi, az általános költségnövekedés pedig 65, ami 24 ponttal magasabbra értékelhető, mint nem optimális döntés.

Példák a kapzsi algoritmusokra

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

  • Prim minimális átívelő fa algoritmusa
  • Utazó eladó probléma
  • Grafikon - Térkép színezése
  • Kruskal minimális átívelő fa algoritmusa
  • Dijkstra minimális átívelő fa algoritmusa
  • Grafikon - Vertex borító
  • Hátizsák probléma
  • Munkaütemezési probléma

Összegzés:

Összefoglalva, a cikk meghatározta a kapzsi paradigmát, megmutatta, hogy a kapzsi optimalizálás és rekurzió hogyan segíthet a legjobb megoldás elérésében egy pontig. A Greedy algoritmust széles körben alkalmazzák problémamegoldáshoz sok nyelven, például Greedy algoritmus Python, C, C #, PHP, Java stb. megközelítés. Végül megmagyarázták a kapzsi szemlélet használatának hátrányait.