Własność optymalnej podstruktury

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

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.

Bibliografia

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