Algoritm lacom cu exemplu: ce este, metodă și abordare

Pentru a înțelege abordarea lacomă, va trebui să aveți cunoștințe practice despre recursivitate și schimbarea contextului. Acest lucru vă ajută să înțelegeți cum să urmăriți codul. Puteți defini paradigma lacomă în termenii propriilor afirmații necesare și suficiente.

Două condiții definesc paradigma lacomă.

• Fiecare soluție în trepte trebuie să structureze o problemă către cea mai bună soluție acceptată.
• Este suficient dacă structurarea problemei se poate opri într-un număr finit de pași lacomi.

Cu teoretizarea continuată, să descriem istoria asociată cu abordarea căutării Greedy.

Istoria lui Greedy Algorithms

Iată un reper important al algoritmilor lacomi:

• Algoritmii greedy au fost conceptualizați pentru mulți algoritmi de mers pe graf în anii 1950.
• Esdger Djikstra a conceptualizat algoritmul pentru a genera arbori de întindere minim. El și-a propus să scurteze durata rutelor din capitala olandeză, Amsterdam.
• În același deceniu, Prim și Kruskal au realizat strategii de optimizare care s-au bazat pe minimizarea costurilor de traseu de-a lungul rutelor cântărite.
• În anii '70, cercetătorii americani, Cormen, Rivest și Stein au propus o substructurăre recursivă a soluțiilor lacome în cartea lor clasică de introducere a algoritmilor.
• Paradigma de căutare Greedy a fost înregistrată ca un tip diferit de strategie de optimizare în înregistrările NIST în 2005.
• Până în prezent, protocoalele care rulează web, cum ar fi open-shortest-path-first (OSPF) și multe alte protocoale de comutare de pachete de rețea, folosesc strategia lacomă pentru a minimiza timpul petrecut într-o rețea.

Strategii și decizii lacome

Logica în forma sa cea mai simplă a fost rezumată la „lacom” sau „nu lacom”. Aceste afirmații au fost definite de abordarea adoptată pentru a avansa în fiecare etapă a algoritmului.

De exemplu, algoritmul lui Djikstra a folosit o strategie lacomă în pas de identificare a gazdelor pe Internet prin calcularea unei funcții de cost. Valoarea returnată de funcția de cost a determinat dacă următoarea cale este „lacomă” sau „non-lacomă”.

Pe scurt, un algoritm încetează să mai fie lacom dacă în orice stadiu face un pas care nu este lacom la nivel local. Problemele Greedy se opresc fără un alt domeniu al lăcomiei.

Caracteristicile algoritmului Greedy

Caracteristicile importante ale unui algoritm Greedy sunt:

• Există o listă ordonată de resurse, cu costuri sau atribuții valorice. Acestea cuantifică constrângerile asupra unui sistem.
• Veți lua cantitatea maximă de resurse în momentul în care se aplică o constrângere.
• De exemplu, într-o problemă de programare a activității, costurile cu resursele sunt exprimate în ore, iar activitățile trebuie efectuate în ordine de serie.

De ce să folosiți abordarea lacomă?

Iată motivele pentru care folosiți abordarea lacomă:

• Abordarea lacomă are câteva compromisuri, care o pot face potrivită pentru optimizare.
• Un motiv important este obținerea imediată a celei mai fezabile soluții. În problema de selecție a activității (Explicată mai jos), dacă se pot face mai multe activități înainte de finalizarea activității curente, aceste activități pot fi efectuate în același timp.
• Un alt motiv este împărțirea recursiv a unei probleme pe baza unei condiții, fără a fi nevoie să combinați toate soluțiile.
• În problema de selecție a activității, pasul „diviziunii recursive” se realizează prin scanarea unei liste de articole o singură dată și luând în considerare anumite activități.

Cum se rezolvă problema de selecție a activității

În exemplul de programare a activității, există o oră de „început” și „terminare” pentru fiecare activitate. Fiecare activitate este indexată printr-un număr pentru referință. Există două categorii de activități.

1. activitate considerată: este Activitatea, care este referința de la care este analizată capacitatea de a face mai mult de o Activitate rămasă.
2. activitati ramase: activități la unul sau mai mulți indici înaintea activității luate în considerare.

Durata totală oferă costul efectuării activității. Adică (terminare – începere) ne oferă durata ca cost al unei activități.

Veți învăța că măsura lacomă este numărul de activități rămase pe care le puteți efectua în timpul unei activități luate în considerare.

Architectura abordării Greedy

PASUL 1) Scanați lista costurilor de activitate, începând cu indicele 0 ca indice considerat.

PASUL 2) Când mai multe activități pot fi terminate până la momentul respectiv, activitatea considerată se termină, începeți să căutați una sau mai multe activități rămase.

PASUL 3) Dacă nu mai sunt activități rămase, activitatea rămasă curentă devine următoarea activitate considerată. Repetați pasul 1 și pasul 2, cu noua activitate luată în considerare. Dacă nu mai sunt activități rămase, treceți la pasul 4.

PASUL 4) Returnează uniunea indicilor considerați. Aceștia sunt indicii de activitate care vor fi utilizați pentru a maximiza debitul.

Explicarea codului

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

#define MAX_ACTIVITIES 12

Explicația codului:

1. Fișierele/clasele de antet incluse
2. Un număr maxim de activități oferite de utilizator.

using namespace std;

class TIME
{
    public:
    int hours;

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

Explicația codului:

1. Spațiul de nume pentru operațiunile de streaming.
2. O definiție de clasă pentru TIME
3. Timp de o oră.
4. Un constructor implicit TIME
5. Variabila orelor.

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

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

Explicația codului:

1. O definiție de clasă din activitate
2. Marcaje temporale care definesc o durată
3. Toate marcajele de timp sunt inițializate la 0 în constructorul implicit

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

Explicația codului:

1. Partea 1 a definiției clasei de planificator.
2. Considered Index este punctul de plecare pentru scanarea mulțime.
3. Indicele de inițializare este utilizat pentru a atribui marcaje temporale aleatorii.
4. O serie de obiecte de activitate este alocată dinamic folosind noul operator.
5. Indicatorul programat definește locația de bază curentă pentru lăcomie.

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

Explicația codului:

1. Constructorul de planificator – partea 2 a definiției clasei de planificator.
2. Indicele considerat definește începutul curent al scanării curente.
3. Extinderea actuală lacomă este nedefinită la început.

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

Explicația codului:

1. O buclă for pentru a inițializa orele de început și orele de sfârșit ale fiecărei activități programate în prezent.
2. Inițializarea orei de începere.
3. Inițializarea orei de încheiere întotdeauna după sau exact la ora de începere.
4. O instrucțiune de depanare pentru a tipări duratele alocate.

	public:
   		 Activity * activity_select(int);
};

Explicația codului:

1. Partea 4 – ultima parte a definiției clasei de planificator.
2. Funcția de selectare a activității ia ca bază un index al punctului de pornire și împarte misiunea lacomă în subprobleme lacome.

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

1. Folosind operatorul de rezoluție a domeniului (::), este furnizată definiția funcției.
2. Indicele considerat este Indexul numit după valoare. Greedy_extent este inițializat doar un index după Indexul considerat.

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

Explicația codului:

1. Logica de bază - Măsura lacomă este limitată la numărul de activități.
2. Orele de început ale activității curente sunt verificate ca programabile înainte ca Activitatea considerată (dată de indexul luat în considerare) să se termine.
3. Atâta timp cât este posibil, este tipărită o instrucțiune opțională de depanare.
4. Avansați la următorul index din matricea de activități

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Explicația codului:

1. Condiționalul verifică dacă toate activitățile au fost acoperite.
2. Dacă nu, puteți reporni greedy-ul cu Indexul considerat ca punct curent. Acesta este un pas recursiv care împarte cu lăcomie enunțul problemei.
3. Dacă da, se întoarce la apelant fără posibilitatea de a extinde lăcomia.

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

Explicația codului:

1. Funcția principală folosită pentru a invoca planificatorul.
2. Este instanțiat un nou Scheduler.
3. Funcția de selectare a activității, care returnează un indicator de tipul de activitate, revine apelantului după terminarea misiunii lacome.

ieșire:

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

Limitările tehnicii Greedy

Nu este potrivit pentru probleme Greedy unde este necesară o soluție pentru fiecare subproblemă, cum ar fi sortarea.

În astfel de probleme de practică ale algoritmului Greedy, metoda Greedy poate fi greșită; în cel mai rău caz chiar duce la o soluție neoptimală.

Prin urmare, dezavantajul algoritmilor lacomi este folosirea de a nu ști ce se află înaintea stării lacome actuale.

Mai jos este o descriere a dezavantajului metodei Greedy:

În scanarea greedy prezentată aici ca un arbore (valoare mai mare mai mare lăcomie), o stare de algoritm la valoarea: 40, este probabil să ia 29 ca următoarea valoare. În plus, căutarea sa se termină la 12. Aceasta înseamnă o valoare de 41.

Cu toate acestea, dacă algoritmul a luat o cale suboptimă sau a adoptat o strategie de cucerire. apoi 25 ar fi urmați de 40, iar îmbunătățirea generală a costurilor ar fi 65, care este evaluat cu 24 de puncte mai mult ca o decizie suboptimă.

Exemple de Greedy Algorithms

Majoritatea algoritmilor de rețea folosesc abordarea lacomă. Iată o listă cu câteva exemple de algoritmi Greedy:

• Algoritmul arborelui de întindere minim al lui Prim
• Problema vânzătorului călător
• Grafic – Colorarea hărții
• Algoritmul arborelui de întindere minimă al lui Kruskal
• Algoritmul arborelui de întindere minimă al lui Dijkstra
• Grafic – Acoperire Vertex
• Problemă la rucsac
• Problemă de programare a locurilor de muncă

Rezumat

Pentru a rezuma, articolul a definit paradigma lacomă, a arătat cum optimizarea și recursiunea lacomă vă pot ajuta să obțineți cea mai bună soluție până la un punct. Algoritmul Greedy este aplicat pe scară largă pentru rezolvarea problemelor în multe limbi ca algoritmul Greedy Python, C, C#, PHP, Java, etc. Selecția activității exemplului algoritmului Greedy a fost descrisă ca o problemă strategică care ar putea atinge un randament maxim folosind abordarea greedy. În final, au fost explicate dezavantajele utilizării abordării lacome.