logo

TechCodeview

Algoritmi lacomi

Algoritmi lacomi sunt o clasă de algoritmi care fac optim local alegeri la fiecare pas cu speranța de a găsi a optim global soluţie. În acești algoritmi, deciziile sunt luate pe baza informațiilor disponibile în momentul actual, fără a lua în considerare consecințele acestor decizii în viitor. Ideea cheie este de a selecta cea mai bună alegere posibilă la fiecare pas, ceea ce duce la o soluție care poate nu este întotdeauna cea mai optimă, dar este adesea suficient de bună pentru multe probleme.

În acest articol, vom înțelege algoritmii lacomi cu exemple. De asemenea, vom analiza problemele și soluțiile lor folosind abordarea lacomă.



Algoritmi lacomi

interfata in java

Cuprins

Ce este algoritmul Greedy?

A algoritm lacom este un tip de algoritm de optimizare care face alegeri optime la nivel local la fiecare pas pentru a găsi o soluție optimă la nivel global. Funcționează pe principiul alegerii celei mai bune opțiuni acum, fără a lua în considerare consecințele pe termen lung.



Pentru a afla ce este metoda greedy și cum să utilizați abordarea greedy, citiți tutorialul oferit despre algoritmul Greedy:

Pași pentru crearea unui algoritm lacom

Pașii pentru definirea unui algoritm lacom sunt:



  1. Defineste problema: Indicați clar problema de rezolvat și obiectivul de optimizat.
  2. Identificați alegerea lacomă: Determinați alegerea optimă local la fiecare pas pe baza stării curente.
  3. Fă alegerea lacomă: Selectați alegerea lacomă și actualizați starea curentă.
  4. Repeta: Continuați să faceți alegeri lacome până când se ajunge la o soluție.

Urmând pașii dați, se poate învăța cum să folosească algoritmi lacomi pentru a găsi soluții optime.

contor java

Exemple de algoritm lacom

Exemplele de algoritmi lacomi sunt cel mai bun mod de a înțelege algoritmul. Câteva exemple din viața reală de algoritm lacom sunt:

  • Rucsac fracționat : Optimizează valoarea articolelor care pot fi incluse fracționat într-un rucsac cu capacitate limitată.
  • algoritmul lui Dijkstra : Găsește calea cea mai scurtă de la un vârf sursă la toate celelalte vârfuri dintr-un grafic ponderat.
  • algoritmul lui Kruskal : Găsește arborele de acoperire minim al unui grafic ponderat.
  • Codare Huffman : Comprimă datele atribuind coduri mai scurte simbolurilor mai frecvente.

Aplicații ale algoritmului Greedy

Există multe aplicații ale metodei greedy în DAA . Câteva aplicații importante ale algoritmului lacom sunt:

  • Atribuirea sarcinilor resurselor pentru a minimiza timpul de așteptare sau pentru a maximiza eficiența.
  • Selectarea celor mai valoroase articole pentru a le încăpea într-un rucsac cu capacitate limitată.
  • Împărțirea unei imagini în regiuni cu caracteristici similare.
  • Reducerea dimensiunii datelor prin eliminarea informațiilor redundante.

Dezavantaje/Limitări ale utilizării unui algoritm lacom

Mai jos sunt câteva dezavantaje ale algoritmului Greedy:

  • Este posibil ca algoritmii greedy să nu găsească întotdeauna cea mai bună soluție posibilă.
  • Ordinea în care sunt luate în considerare elementele poate avea un impact semnificativ asupra rezultatului.
  • Algoritmii greedy se concentrează pe optimizările locale și pot pierde soluții mai bune care necesită luarea în considerare a unui context mai larg.
  • Algoritmii greedy nu sunt aplicabili problemelor în care alegerea greedy nu duce la o soluție optimă.

Bazele algoritmului Greedy:

  • Algoritmi greedy (structură generală și aplicații)
  • Diferența dintre algoritmul Greedy și algoritmul Divide and Conquer
  • Abordare lacomă vs programare dinamică
  • Comparație între Greedy, Divide and Conquer și algoritmul de programare dinamică

Algoritmi standard greedy:

  • Problemă de selecție a activității
  • Problemă de secvențiere a locurilor de muncă
  • Codarea Huffman
  • Decodare Huffman
  • Problemă de conectare la apă
  • Schimburi minime pentru echilibrarea bracket-ului
  • Fracția egipteană
  • Polițiștii prind hoți
  • Problemă cu montarea raftului
  • Atribuiți șoareci la găuri

Probleme lacome pe matrice:

  • Subset de produs minim al unei matrice
  • Maximizați suma matricei după K negații folosind Sortarea
  • Suma minimă a produsului a două matrice
  • Suma minimă a diferenței absolute a perechilor de două tablouri
  • Creștere/decrementare minimă pentru ca matricea să nu fie în creștere
  • Matrice de sortare cu reversul în jurul mijlocului
  • Suma ariilor dreptunghiurilor posibilă pentru o matrice
  • Cea mai mare matrice lexicografică cu cel mult K schimburi consecutive
  • Împărțiți în două subgrupuri de lungimi k și (N – k) astfel încât diferența de sume să fie maximă

Probleme lacome pe sistemul de operare:

  • Algoritmul First Fit în gestionarea memoriei
  • Algoritmul Best Fit în gestionarea memoriei
  • Algoritmul cel mai prost potrivit în gestionarea memoriei
  • Cel mai scurt loc de muncă Prima programare
  • Programarea locurilor de muncă cu două locuri de muncă permise simultan
  • Program pentru algoritmul optim de înlocuire a paginii

Probleme lacome pe grafic:

  • Arborele de întindere minim al lui Kruskal
  • Arborele de întindere minim al lui Prim
  • Arborele de întindere minim al lui Boruvka
  • Algoritmul cu cea mai scurtă cale al lui Dijkastra
  • Algoritmul Dialului
  • Cost minim pentru conectarea tuturor orașelor
  • Introducere problemei fluxului maxim
  • Numărul de componente cu un singur ciclu într-un grafic nedirecționat

Algoritmul Greedy aproximativ pentru NP Complete:

  • Setați problema capacului
  • Problemă de ambalare a coșului
  • Colorarea graficului
  • Problema cu centrele K
  • Cea mai scurtă problemă de superstring
  • Soluție aproximativă pentru problema vânzătorului călător folosind MST

Lacom pentru cazuri speciale de DP:

  • Problema rucsacului fracționat
  • Numărul minim de monede necesar

Probleme ușoare pe Greedy Algoritm :

  • Împărțiți n în numere compuse maxime
  • Cumpărați acțiuni maxime dacă stocurile i pot fi cumpărate în a-a zi
  • Găsiți suma minimă și maximă pentru a cumpăra toate N bomboane
  • Suma maximă posibilă este egală cu suma a trei stive
  • Împărțiți cuboidul în cuburi astfel încât suma volumelor să fie maximă
  • Numărul maxim de clienți care pot fi mulțumiți de cantitatea dată
  • Rotații minime pentru a debloca o încuietoare circulară
  • Săli minime pentru m evenimente din n loturi cu program dat
  • Costul minim pentru a face dimensiunea matricei 1 prin eliminarea perechilor mai mari
  • Costul minim pentru achiziționarea tuturor monedelor cu k monede suplimentare permis cu fiecare monedă
  • Incrementare minimă cu k operații pentru a face toate elementele egale
  • Găsiți numărul minim de bancnote și valori care însumează suma dată
  • Cea mai mică submulțime cu o sumă mai mare decât toate celelalte elemente

Probleme medii pe Greedy Algoritm :

  • Numărul maxim de trenuri pentru care se poate asigura oprire
  • Termenii minimi Fibonacci cu suma egală cu K
  • Împărțiți de la 1 la n în două grupuri cu o diferență de sumă minimă
  • Hârtia tăiată în număr minim de pătrate
  • Diferența minimă între grupurile de mărime doi
  • Conectați n frânghii cu costuri minime
  • Numărul minim de peroane necesare pentru o stație de cale ferată/autobuz
  • Vârfurile inițiale minime pentru a parcurge întreaga matrice cu condiții date
  • Cel mai mare număr palindromic prin permutarea cifrelor
  • Găsiți cel mai mic număr cu un număr dat de cifre și suma cifrelor
  • Subsecvență cea mai mare din punct de vedere lexicografic, astfel încât fiecare caracter să apară de cel puțin k ori

Probleme grele pe Greedy Algoritm :

  • Elemente maxime care pot fi egalate cu k actualizări
  • Minimizați fluxul de numerar între prieteni
  • Costul minim pentru a tăia o placă în pătrate
  • Costul minim de procesare a m sarcini unde costurile de comutare
  • Timp minim pentru a finaliza toate lucrările cu constrângeri date
  • Minimizați diferența maximă dintre înălțimile turnurilor
  • Margini minime de inversat pentru a face calea de la o sursă la o destinație
  • Găsiți cel mai mare cub format prin ștergerea cifrelor minime dintr-un număr
  • Rearanjați caracterele într-un șir astfel încât să nu fie două adiacente la fel
  • Rearanjați un șir astfel încât toate aceleași caractere să devină la distanță d
  • Aflați structura datelor și algoritmi | Tutorial DSA
  • Top 20 de întrebări de interviu Greedy Algorithms
  • „Probleme de practică” pe algoritmi lacomi
  • „Quiz” despre algoritmi lacomi