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[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

edytuj

Bibliografia

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