V računalništvu naj bi imel problem prekrivajoče se podprobleme, če je težavo mogoče razčleniti na podprobleme, ki se večkrat ponovno uporabijo, ali rekurzivni algoritem za problem vedno znova rešuje isti podproblem, namesto da bi vedno ustvaril nove. podproblemi.
Kaj so optimalna podstruktura in prekrivajoči se podproblemi v dinamičnem programiranju?
Problem ima optimalno lastnost podstrukture, če je mogoče optimalno rešitev danega problema dobiti z uporabo optimalne rešitve njegovih podproblemov. Dinamično programiranje izkorišča to lastnost za iskanje rešitve.
Kaj je prekrivajoči se podproblem v dinamičnem programiranju?
1) Prekrivajoči se podproblemi:
Dinamično programiranje se večinoma uporablja, ko so vedno znova potrebne rešitve istih podproblemov. Pri dinamičnem programiranju so izračunane rešitve podproblemov shranjene v tabeli, tako da jih ni treba ponovno izračunati.
Kakšna je razlika med optimalno podstrukturo in prekrivajočimi se podproblemi?
Razumem ciljni pristop za obe metodi, kjer Optimalna podstruktura izračuna optimalno rešitev na podlagi vnosa n, medtem ko Prekrivajoči se podproblemi ciljajo na vse rešitve za obseg vnosa, recimo od 1 do n. Za težavo, kot je problem rezanja palice.
Katera od teh tehnik uporablja prekrivanje podproblemov?
Dinamično programiranje je tehnika za reševanje problemov s prekrivajočimi se podproblemi. V to shranimo rezultat podproblema, ki je enkrat rešen, za prihodnjo ponovno uporabo. Tehnika shranjevanja rešitev podproblemov se imenuje pomnjenje.
