Algoritmul Greedy

Care este principiul de bază al algoritmului Greedy și de ce se numește „lacom”?

• Care este principiul de bază al algoritmului Greedy și de ce se numește „lacom”?

• Principiul Greedy presupune explorarea tuturor posibilităților simultan și alegerea soluției finale bazată pe calcule exhaustive.

• Algoritmul Greedy rezolvă probleme folosind recursivitate pentru a găsi toate soluțiile posibile și apoi alege cea optimă.

În algoritmul formal prezentat, ce rol are condiția fezabil(S∪(x)) și de ce este importantă?

• Această condiție oprește algoritmul atunci când toate elementele au fost adăugate în soluție, indiferent de constrângeri.

• Condiția decide dacă elementul x este cel mai mare element din mulțimea inițială C.

• Verifică dacă adăugarea elementului x în soluția parțială S respectă constrângerile problemei.

Cum funcționează algoritmul Greedy pentru rezolvarea problemei spectacolelor și care este raționamentul sortării spectacolelor după timpii de final?

• Sortarea spectacolelor crescător după timpii de final garantează selecția unui număr maxim de spectacole compatibile.

• Sortarea se face după timpii de start, iar selecția depinde doar de primul spectacol din listă.

• Algoritmul selectează spectacolele aleator și le adaugă pe cele cu cel mai mare timp de final în soluție.

În problema cuielor, de ce se observă că punctele din mulțimea M pot fi considerate capete drepte ale intervalelor?

• Capetele drepte sunt cele mai mici puncte din intervale și oferă cea mai rapidă soluție

• Capetele drepte garantează acoperirea întregului interval cu un număr minim de puncte, fără pierderea de soluții.

• Punctele din M trebuie alese întotdeauna la mijlocul fiecărui interval pentru a echilibra distribuția.

De ce eficiența de transport (profit/greutate) este utilizată pentru rezolvarea problemei rucsacului?

• Această metodă permite adăugarea doar a obiectelor cele mai ușoare, maximizând numărul total de obiecte încărcate.

• Eficiența de transport minimizează numărul de obiecte alese, indiferent de greutatea totală.

• Eficiența maximizează profitul obținut per unitate de greutate, ajutând la o încărcare optimă a rucsacului.

Care este limita algoritmului Greedy în rezolvarea problemei comisului voiajor (TSP)?

• Algoritmul Greedy folosește întotdeauna parcurgerea BFS (Breadth-First Search) pentru a găsi cea mai rapidă soluție.

• Algoritmul Greedy găsește întotdeauna soluția optimă în orice problemă TSP fără excepție.

• Algoritmul Greedy nu garantează găsirea soluției optime, dar oferă o soluție aproximativă într-un timp util.

Numiți o aplicație practică a algoritmului Greedy în afara celor prezentate în text.

• Problema restului la bancomat – alegerea unui număr minim de bancnote pentru o sumă dată.

• Problema parcurgerii unui arbore binar folosind o metodă de backtracking.

• Rezolvarea sistemelor liniare de ecuații prin metoda Gauss-Jordan.

Care sunt avantajele și dezavantajele utilizării unui algoritm Greedy în comparație cu alte tehnici de optimizare?

• Avantaj: Greedy oferă întotdeauna soluția optimă. Dezavantaj: necesită mult spațiu de memorie.

• Avantaj: Greedy este rapid și simplu de implementat. Dezavantaj: nu garantează soluția optimă în toate cazurile.

• Avantaj: Greedy explorează toate soluțiile posibile. Dezavantaj: este întotdeauna mai lent decât programarea dinamică.