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
edytujBibliografia
edytuj- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.