Substructură optimă
În informatică , o problemă are o substructură optimă dacă este posibilă construirea eficientă a unei soluții optime pornind de la soluțiile optime ale subproblemelor sale. Această proprietate este necesară pentru a utiliza tehnici de programare dinamică sau algoritmi lacomi .
Un exemplu de substructuri optime este căutarea celei mai scurte căi între două vârfuri într-un grafic , așa cum se ilustrează în figura următoare: mai întâi cea mai scurtă cale se găsește de la vârful de sosire la toate vârfurile apropiate de cea inițială (în mod repetat și cu aceeași metodă); atunci se alege calea care minimizează greutatea totală a arcurilor .
De obicei, o problemă cu substructură optimă este rezolvată cu un algoritm lacom . Dacă problema are și subprobleme suprapuse , poate fi utilizat un algoritm dinamic .
