Greedy Algorithm s příkladem: Co je, metoda a přístup

Abyste pochopili chamtivý přístup, budete potřebovat pracovní znalosti rekurze a přepínání kontextu. To vám pomůže pochopit, jak sledovat kód. Chamtivé paradigma můžete definovat pomocí vlastních nezbytných a dostatečných prohlášení.

Chamtivé paradigma definují dvě podmínky.

• Každé postupné řešení musí strukturovat problém směrem k jeho nejlépe přijatelnému řešení.
• Stačí, když se strukturování problému může zastavit v konečném počtu zištných kroků.

S pokračováním teoretizování popišme historii spojenou s přístupem Greedy search.

Historie Greedy Algorithms

Zde je důležitý orientační bod chamtivých algoritmů:

• Chamtivé algoritmy byly konceptualizovány pro mnoho algoritmů procházení grafů v 1950. letech XNUMX. století.
• Esdger Djikstra konceptualizoval algoritmus tak, aby generoval minimální kostry. Jeho cílem bylo zkrátit rozpětí tras v nizozemském hlavním městě Amsterdamu.
• Ve stejném desetiletí Prim a Kruskal dosáhli optimalizačních strategií, které byly založeny na minimalizaci nákladů na cestu podél vážených tras.
• V 70. letech američtí výzkumníci Cormen, Rivest a Stein ve své klasické knize o algoritmech navrhli rekurzivní substrukturování chamtivých řešení.
• Paradigma Greedy search bylo zaregistrováno jako jiný typ optimalizační strategie v záznamech NIST v roce 2005.
• Protokoly, které provozují web, jako je OSPF (open-shortest-path-first) a mnoho dalších síťových protokolů pro přepínání paketů, dosud používají chamtivou strategii k minimalizaci času stráveného v síti.

Chamtivé strategie a rozhodnutí

Logika ve své nejjednodušší podobě byla zredukována na „chamtivý“ nebo „nechamtivý“. Tato tvrzení byla definována přístupem, který byl zvolen pro postup v každé fázi algoritmu.

Například Djikstrův algoritmus využíval postupnou chamtivou strategii identifikující hostitele na internetu pomocí výpočtu nákladové funkce. Hodnota vrácená funkcí cost určovala, zda je další cesta „chamtivá“ nebo „nežravá“.

Stručně řečeno, algoritmus přestane být chamtivý, pokud v jakékoli fázi udělá krok, který není lokálně chamtivý. Greedy problémy se zastaví bez dalšího rozsahu chamtivosti.

Charakteristika Greedy Algorithm

Důležité vlastnosti Greedyho algoritmu jsou:

• Existuje uspořádaný seznam zdrojů s náklady nebo přiřazením hodnoty. Ty kvantifikují omezení v systému.
• Vezmete maximální množství zdrojů v době, kdy platí omezení.
• Například v případě problému s plánováním činnosti jsou náklady na zdroje v hodinách a činnosti je třeba provádět v sériovém pořadí.

Proč používat Greedy Approach?

Zde jsou důvody pro použití chamtivého přístupu:

• Chamtivý přístup má několik kompromisů, díky kterým je vhodný pro optimalizaci.
• Jedním z hlavních důvodů je okamžitě dosáhnout nejschůdnějšího řešení. V problému výběru činností (vysvětleno níže), pokud lze před dokončením aktuální činnosti provést více činností, lze tyto činnosti provést ve stejnou dobu.
• Dalším důvodem je rozdělení problému rekurzivně na základě podmínky, bez nutnosti kombinovat všechna řešení.
• V problému výběru aktivit je krok „rekurzivního dělení“ dosažen tak, že se seznam položek naskenuje pouze jednou a zváží se určité aktivity.

Jak vyřešit problém s výběrem aktivity

V příkladu plánování aktivity je pro každou aktivitu čas „začátek“ a „konec“. Každá aktivita je pro referenci indexována číslem. Existují dvě kategorie aktivit.

1. uvažovaná činnost: je Aktivita, což je reference, ze které se analyzuje schopnost udělat více než jednu zbývající aktivitu.
2. zbývající aktivity: aktivity na jednom nebo více indexech před uvažovanou aktivitou.

Celková doba trvání udává náklady na provedení činnosti. To znamená (dokončit – začít) nám dává trvání jako náklady na aktivitu.

Dozvíte se, že chamtivý rozsah je počet zbývajících činností, které můžete vykonávat v době uvažované činnosti.

Architecture of the Greedy přístupu

KROK 1) Naskenujte seznam nákladů na činnost, počínaje indexem 0 jako uvažovaným indexem.

KROK 2) Jakmile bude možné dokončit více činností, uvažovaná činnost skončí, začněte hledat jednu nebo více zbývajících činností.

KROK 3) Pokud již nejsou žádné zbývající aktivity, aktuální zbývající aktivita se stane další uvažovanou aktivitou. Opakujte krok 1 a krok 2 s novou uvažovanou aktivitou. Pokud nezbývají žádné zbývající aktivity, přejděte ke kroku 4.

KROK 4 ) Vraťte spojení uvažovaných indexů. Toto jsou indexy aktivity, které budou použity k maximalizaci propustnosti.

Vysvětlení kódu

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

#define MAX_ACTIVITIES 12

Vysvětlení kódu:

1. Zahrnuté hlavičkové soubory/třídy
2. Maximální počet činností poskytovaných uživatelem.

using namespace std;

class TIME
{
    public:
    int hours;

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

Vysvětlení kódu:

1. Jmenný prostor pro operace streamování.
2. Definice třídy pro TIME
3. Hodinové časové razítko.
4. Výchozí konstruktor TIME
5. Proměnná hodin.

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

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

Vysvětlení kódu:

1. Definice třídy z aktivity
2. Časová razítka definující dobu trvání
3. Všechna časová razítka jsou ve výchozím konstruktoru inicializována na 0

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

Vysvětlení kódu:

1. Část 1 definice třídy plánovače.
2. Zvažovaný index je výchozím bodem pro skenování řada.
3. Inicializační index se používá k přiřazení náhodných časových razítek.
4. Pole objektů aktivity je dynamicky alokováno pomocí operátoru new.
5. Naplánovaný ukazatel definuje aktuální základní umístění pro chamtivost.

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

Vysvětlení kódu:

1. Konstruktor plánovače – 2. část definice třídy plánovače.
2. Uvažovaný index definuje aktuální začátek aktuálního skenování.
3. Aktuální rozsah zištnosti není na začátku definová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);
 }
…
…

Vysvětlení kódu:

1. Smyčka for pro inicializaci počáteční a koncové hodiny každé z aktuálně naplánovaných aktivit.
2. Inicializace času zahájení.
3. Inicializace koncového času vždy po nebo přesně v počáteční hodinu.
4. Příkaz ladění pro tisk přidělených trvání.

	public:
   		 Activity * activity_select(int);
};

Vysvětlení kódu:

1. Část 4 – poslední část definice třídy plánovače.
2. Funkce výběru aktivity bere jako základ index výchozího bodu a rozděluje chamtivý úkol na chamtivé dílčí problémy.

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

1. Pomocí operátoru rozlišení rozsahu (::) je poskytnuta definice funkce.
2. Uvažovaný Index je Index nazývaný hodnotou. greedy_extent je inicializovaný pouze index za uvažovaným indexem.

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

Vysvětlení kódu:

1. Základní logika- Nenásytný rozsah je omezen na počet činností.
2. Počáteční hodiny aktuální aktivity jsou kontrolovány jako plánovatelné, než uvažovaná aktivita (daná uvažovaným indexem) skončí.
3. Dokud je to možné, vytiskne se volitelný příkaz ladění.
4. Přejít na další index v poli aktivit

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Vysvětlení kódu:

1. Podmínka kontroluje, zda byly pokryty všechny činnosti.
2. Pokud ne, můžete svou chamtivost restartovat s uvažovaným Indexem jako aktuálním bodem. Toto je rekurzivní krok, který chtivě rozděluje problémové prohlášení.
3. Pokud ano, vrátí se volajícímu bez prostoru pro rozšíření chamtivosti.

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

Vysvětlení kódu:

1. Hlavní funkce použitá k vyvolání plánovače.
2. Vytvoří se nový plánovač.
3. Funkce výběru aktivity, která vrací ukazatel typu aktivity, se volajícímu vrátí po skončení chtivé výpravy.

Výstup:

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

Omezení Greedy techniky

Není vhodný pro Greedy problémy, kde je vyžadováno řešení pro každý dílčí problém, jako je třídění.

V takových problémech procvičování Greedyho algoritmu může být Greedyho metoda chybná; v nejhorším případě dokonce vést k neoptimálnímu řešení.

Proto nevýhodou chamtivých algoritmů je použití neznalosti toho, co je před současným chamtivým stavem.

Níže je znázorněna nevýhoda Greedyho metody:

V chamtivém skenování zde zobrazeném jako strom (vyšší hodnota vyšší chamtivost) stav algoritmu na hodnotě: 40 pravděpodobně vezme 29 jako další hodnotu. Dále jeho úkol končí na 12. To má hodnotu 41.

Pokud by se však algoritmus vydal neoptimální cestou nebo přijal dobývací strategii. pak by po 25 následovalo 40 a celkové zlepšení nákladů by bylo 65, což je ohodnoceno o 24 bodů výše jako neoptimální rozhodnutí.

Příklady Greedy Algorithms

Většina síťových algoritmů používá chamtivý přístup. Zde je seznam několika příkladů Greedy algoritmu:

• Primův minimální algoritmus Spanning Tree
• Cestování prodavač problém
• Graf – Barvení mapy
• Kruskalův minimální algoritmus Spanning Tree
• Dijkstrův algoritmus minimálního Spanning Tree
• Graf – Vertex Cover
• Problém s batohem
• Problém s plánováním práce

Shrnutí

Abychom to shrnuli, článek definoval chamtivé paradigma a ukázal, jak chamtivá optimalizace a rekurze vám mohou pomoci získat nejlepší řešení do určité míry. Greedy algoritmus je široce používán pro řešení problémů v mnoha jazycích jako Greedy algoritmus Python, C, C#, PHP, Java, atd. Výběr aktivity v příkladu Greedyho algoritmu byl popsán jako strategický problém, který by mohl dosáhnout maximální propustnosti pomocí greedy přístupu. Na závěr byly vysvětleny nedostatky používání zištného přístupu.