Introducere în Algoritmul Greedy
O strategie folosită pentru rezolvarea problemelor. Algoritmul lacom este considerat ca una dintre abordările utilizate pentru rezolvarea problemelor. Acest eretic de rezolvare a problemelor merge cu alegerea care pare cea mai bună în acel moment. Această abordare este cea mai bună pentru a rezolva problemele de optimizare. Problemele de optimizare pot fi definite ca probleme care necesită rezultate minime sau maxime. Un algoritm lacom este o abordare cea mai simplă și mai simplă care poate fi folosită pentru a obține o soluție optimă.
Ce este algoritmul lacom?
Greedy Algorithm este o strategie algoritmică folosită pentru a face cea mai bună alegere opțională la o etapă foarte mică, în timp ce produce o soluție optimă la nivel global. Acest algoritm alege cea mai bună soluție posibilă în acel moment, fără a ține cont de consecințe. Metoda lacom spune că problema trebuie rezolvată în etape în care fiecare intrare este considerată, având în vedere că această intrare este posibilă. Întrucât această abordare se concentrează doar pe un rezultat imediat, fără a ține cont de imaginea mai mare, este considerată lacomă.
Definirea conceptului de bază
Până acum, știm ce este un algoritm lacom și de ce este numit așa. Indicatorii de mai jos te vor face să înțelegi algoritmul lacom într-un mod mai bun. Până acum, a fost foarte clar că algoritmul lacom funcționează numai atunci când există o problemă; cu toate acestea, această abordare este aplicabilă numai dacă avem o condiție sau o restricție la această problemă.
Tipuri de probleme
- Problema de minimizare: Obținerea unei soluții la o problemă este ușor, având în vedere că sunt îndeplinite toate condițiile. Cu toate acestea, atunci când această problemă necesită un rezultat minim, atunci este numită Problemă de minimizare.
- Problema de maximizare: o problemă care necesită rezultatul maxim este cunoscută sub numele de problemă de maximizare.
- Problema de optimizare: o problemă se numește problemă de optimizare atunci când necesită rezultate minime sau maxime.
Tipuri de soluții
- Soluție fezabilă: Acum, când apare o problemă, avem multe soluții plauzibile pentru această problemă. Cu toate acestea, luând în considerare condiția stabilită pentru această problemă, alegem soluții care satisfac condiția dată. Astfel de soluții care ne ajută să obținem rezultate care îndeplinesc condiția dată se numește o soluție fezabilă .
- Soluție optimă: o soluție este numită optimă atunci când este deja posibil și atinge obiectivul problemei; cel mai bun rezultat. Acest obiectiv poate fi rezultatul minim sau maxim. Ideea de remarcat este că orice problemă va avea o singură soluție optimă.
Următorul exemplu vă va face să înțelegeți cu ușurință metoda lacomă. Spune, cineva vrea să cumpere cea mai bună mașină disponibilă pe piață. Una dintre metodele de a alege această mașină este prin analizarea tuturor mașinilor de pe piață. Acum, aceasta necesită mult timp, pentru a face mai ușor să selectezi o mașină din acele mărci specifice în care sunt interesați să investească. Prin urmare, abordarea folosită aici este lacomă, deoarece această soluție a fost soluția optimă pentru tine, considerând că toți factorii erau favorabili pentru tine.
Componentele de bază ale unui algoritm lacom
Acum, când vom înțelege mai bine acest mecanism, să explorăm componentele de bază ale unui algoritm lacom care îl diferențiază de alte procese:
- Set de candidați: Un răspuns este creat din acest set.
- Funcția de selecție: selectează cel mai bun candidat care trebuie inclus în soluție.
- Funcția de fezabilitate: Această secțiune calculează dacă un candidat poate fi utilizat pentru a contribui la soluție.
- O funcție obiectivă: atribuie o valoare unei soluții complete sau parțiale.
- O funcție de soluție: aceasta este folosită pentru a indica dacă a fost respectată o soluție adecvată.
Unde funcționează cel mai bine Greedy Algorithm?
Algoritmul lacom poate fi aplicat la problemele menționate mai jos.
- Abordarea Greedy poate fi folosită pentru a găsi graficul arborelor de întindere minimă folosind algoritmul lui Prim sau Kruskal
- Găsirea celui mai scurt traseu între două vârfuri este încă o problemă care poate fi rezolvată folosind un algoritm lacom. Aplicarea algoritmului lui Dijkstra împreună cu algoritmul lacom vă va oferi o soluție optimă.
- Huffman Coding
avantaje
Cel mai mare avantaj pe care algoritmul Greedy îl are față de alții este că este ușor de implementat și foarte eficient în majoritatea cazurilor.
Dezavantaje
Algoritmul lacom construiește practic o soluție parte câte una și alege următoarea parte astfel încât să ofere imediat cea mai bună soluție la problema actuală. Drept urmare, nu există nicio atenție sau îngrijorare cu privire la consecințele deciziei actuale luate. Nu reconsidera niciodată alegerile luate anterior, Greedy Algorithm nu reușește să producă o soluție optimă, deși oferă o soluție aproape optimă . Problema Rucsacului și Problema Vânzătorului Călător sunt exemple de probleme în care Algoritmul Greedy nu reușește să producă o soluție optimă.
- Problema rucsacului: cea mai frecvent cunoscută de numele rucsack problem, este o problemă de zi cu zi cu care se confruntă mulți oameni. Spune, am setat de articole și fiecare are o greutate și o valoare diferite (profit) pentru a fi completate într-un container sau ar trebui colectate astfel încât greutatea totală să fie mai mică sau egală cu cea a containerului, în timp ce profitul total este maximizat .
Concluzie
Algoritmul lacom este cel mai bine aplicabil atunci când este nevoie de o soluție în timp real și răspunsuri aproximative este „suficient de bun”. În mod clar, un algoritm lacom minimizează timpul, asigurându-se, în același timp, că se produce o soluție optimă, prin urmare, este mai aplicabil să se utilizeze într-o situație în care este nevoie de mai puțin timp. După citirea acestui articol, s-ar putea avea o idee corectă despre algoritmi lacomi. În plus, acest post explică de ce este considerat cel mai bun cadru care răspunde aproape tuturor provocărilor de programare, alături de faptul că te ajută să decizi cea mai optimă soluție la un moment dat.
Totuși, pe partea aspră, pentru aplicarea teoriei algoritmului lacom, trebuie să muncim mai mult pentru a cunoaște problemele corecte. Deși este un concept științific care are logică, are și o esență a creativității.
Articole recomandate
Acesta a fost un ghid pentru Ce este un algoritm lacom. Aici am discutat Conceptul de bază, componentele, Avantajul și dezavantajul algoritmului lacom. Puteți parcurge și alte articole sugerate pentru a afla mai multe -
- Algoritmul în programare
- Ce este Perl?
- Introducere în Algoritm
- Ce este Agile Sprint?