Arvutiteaduses öeldakse, et probleemil on kattuvad alamprobleemid, kui probleemi saab jaotada alamprobleemideks, mida kasutatakse mitu korda või kui ülesande rekursiivne algoritm lahendab sama alamprobleemi ikka ja jälle, mitte ei genereeri alati uusi alamprobleemid.
Mis on dünaamilise programmeerimise optimaalne alamstruktuur ja kattuvad alamprobleemid?
Ülesandel on optimaalne alamstruktuuri omadus, kui selle alamülesannete optimaalset lahendust kasutades on võimalik saada antud ülesandele optimaalne lahendus. Dünaamiline programmeerimine kasutab seda omadust lahenduse leidmiseks ära.
Mis on dünaamilise programmeerimise kattuv alamprobleem?
1) Kattuvad alamprobleemid:
Dünaamilist programmeerimist kasutatakse peamiselt siis, kui on vaja ikka ja jälle samade alamülesannete lahendusi. Dünaamilises programmeerimises salvestatakse alamprobleemide arvutatud lahendused tabelisse, nii et neid ei pea uuesti arvutama.
Mis vahe on optimaalsel alamstruktuuril ja kattuvatel alamprobleemidel?
Mõistan mõlema meetodi sihtlähenemist, kus optimaalne alamstruktuur arvutab optimaalse lahenduse sisendi n põhjal, samas kui kattuvad alamprobleemid sihib kõiki lahendusi sisendivahemikus, näiteks vahemikus 1 kuni n. Sellise probleemi jaoks nagu varda lõikamise probleem.
Milline neist tehnikatest kasutab alamprobleemide kattumist?
Dünaamiline programmeerimine on tehnika kattuvate alamprobleemidega probleemide lahendamiseks. Sellesse salvestame ühekordselt lahendatud alamprobleemi tulemuse edaspidiseks taaskasutamiseks. Alamprobleemide lahenduste salvestamise tehnikat nimetatakse memoiseerimiseks.
