11. laboratórium: Adatszerkezetek és algoritmusok dinamikus programozása (1AB sorozat)
Felhasználói eszközök
Webhely eszközök
Oldalsáv
tartalom
1 Laboratóriumi célok
2 Dinamikus programozás
2.1 Áttekintés
A dinamikus programozás magában foglalja a probléma megoldását részproblémákra bontásával és megoldásával. A divide et impera-val ellentétben az alprogramok nem szétválnak, hanem átfedik egymást.
Az átfedő részek újraszámolásának elkerülése érdekében a megoldás a legkisebb alprogramokból indul ki, és eredményünk felhasználásával kiszámoljuk az azonnal nagyobb részproblémát. A legkisebb részproblémákat egységproblémáknak nevezzük, amelyek állandó bonyolultságban megoldhatók, pl. Egyetlen elem halmazának legnagyobb szekvenciája.
2.2 Végrehajtás
2.3 Az algoritmussal megoldott tipikus problémák
2.3.1 A hátizsák problémája
A megoldást dinamikus programozással állítják össze, D [i] [j] = az első i objektumra elért legjobb költség, amelynek maximális súlya j.
A megismétlődés relációja a következő: D [i] [j] = maximum (D [i-1] [j], D [i-1] [jG [i]] + C [i]), ahol G [i] = az i objektum súlya, és C [i] = az objektum költsége.
Az ötlet a következő: A jelenlegi megoldáshoz vagy egyáltalán nem adjuk hozzá az i objektumot, és az i-1 objektumok költségén maradunk, vagy hozzáadjuk az i objektumot, amely esetben hozzáadjuk annak költségét az első i-1 objektumhoz kapott költséghez és a j-G súlyhoz [i].
2.3.2 A leghosszabb emelkedő sor meghatározása
Példa: a 24,12,15,8,19 karakterláncra a válasz a 12,15,19 karakterlánc.
Kezdjük azzal, hogy minden elemhez meghatározzuk a leghosszabb szigorúan növekvő karakterlánc hosszát, amely az első elemmel kezdődik és abban az elemben végződik. Ezt az értéket nevezzük a legjobban, és a legjobb rekurzív képletet alkalmazzuk i = 1 + max (legjobb j), jn-vel, akkor újraírhatjuk P (n) = ∏ (Cn, k X k), ahol k = 0,1,2,… n.
Legyen koef (P, k) = X k együtthatója a P polinomban. Ezután felírhatjuk a következő 2 tulajdonságot:
Összefüggésre következtethetünk a P (n) típusú polinomok együtthatói között, ha P (n + 1) = (X + 1) P (n) = X P (n) + P (n).
De a koef (P (n), k) = C (n, k), tehát olyan ismétlődést kaptunk, amely csak egy összeadást használ.
Feladatok
3. Laboratóriumi gyakorlatok (Linux)
A laboratórium kódvázát itt töltheti le. Töltse le az archívumot, és csomagolja ki.
Linux
A wget segédprogramot letöltheti, a kicsomagolást pedig a kicsomagoláshoz.