Własność optymalnej podstruktury

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Własność optymalnej podstruktury – jest własnością problemów, które można rozwiązywać za pomocą algorytmów, mówiącą, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów[1].

Jeżeli problem wykazuje własność optymalnej podstruktury, to zazwyczaj można znaleźć rozwiązujący go algorytm dynamiczny, a czasem (także) zachłanny[1].

Przypisy

Bibliografia[edytuj | edytuj kod]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.