ČVUT V PRAZE FAKULTA INFORMAČNÍCH TECHNOLOGIÍ JAN SCHMIDT A PETR FIŠER
MI-PAA
DYNAMICKÉ PROGRAMOVÁNÍ A PROBLÉM BATOHU
EVROPSKÝ SOCIÁLNÍ FOND PRAHA A EU: INVESTUJEME DO VAŠÍ BUDOUCNOSTI
Dynamické programování Dynamické programování je vždy spojeno s dekompozicí. Pro 0/1 problém batohu i existují nejméně dvě dekompozice:
podle celkové ceny
podle kapacity batohu
Dekompozice podle celkové ceny
Označme E(i, c) instanci 0/1 inverzního problému batohuii se zadanou cenou c, která vznikne z řešené instance omezením na prvých i věcí. Označme dále W(i, c) sumární hmotnost věcí řešené instance. Pak platí
W(0,0) = 0 W(0,c) = ∞ pro všechna c > 0 W(i+1, c) = min(W(i, c), W(i, c-ci+1)+wi+1) pro všechna i > 0.
Z výsledných řešení W(n, c) vybereme řešení, pro které je W(n, c) < M pro největší c. Je zřejmé, že řešení můžeme omezit na c menší nebo rovné součtu cen všech věcí. Výše uvedená závislost je pro dynamické programování charakteristická. Postup řešení lze formulovat buď rekurzí (řešit problémy E(n, c) pro všechna c a rekurzivně potřebné podproblémy) nebo dopředně - začít s E(0, c) pro všechna c a generovat všechna možná řešení problémů E(i, c) pro i = 1, … , n. Je třeba zabránit tomu, aby byl jeden a týž problém řešen opakovaně, jinak se ztrácejí přednosti metody.
Dekompozice podle kapacity Abychom stanovili optimální řešení pro n věcí, musíme znát 1. optimální řešení problému s vyjmutou n-tou věcí (v případě, že n-tá věc v optimálním řešení není) 2. optimální řešení problému s vyjmutou n-tou věcí a kapacitou batohu sníženou o hmotnost té věci (v případě, že n-tá věc je součástí optimálního řešení). Srovnáme-li obě varianty, zjistíme, zda n-tá věc má být v optimálním řešení. Rekurzivně opakujeme, až dostaneme triviální podúlohy. Řešení podúloh je třeba zaznamenávat k opakovanému použití. Možný algoritmus Nechť (Xn, Cn, m) = KNAP(V, C, M) je algoritmus řešící instanci problému batohu danou (V, C, M) a vracející vektor X, celkovou cenu Cn a celkovou váhu m. Pak můžeme KNAP napsat jako následující pseudokód. Tečka je zde operátor zřetězení: function KNAP (V, C, M) if isTrivial(V, C, M) return trivialKNAP(V, C, M);
// ukončení rekurze, je-li instance triviální (X0, C0, m0) = KNAP(V-{vn}, C-{cn}, M); // vyřeš batoh, ve kterém n-tá věc není (X1, C1, m1) = KNAP(V-{vn}, C-{cn}, M-vn); // vyřeš batoh, ve kterém n-tá věc je if (C1+cn) > C0 return(X1.1, C1+cn, m1+vn); // jaká varianta je lepší? else return(X0.0, C0, m0); function isTrivial(V, C, M) return(isEmpty(V) or M=0 or M<0);
Až dosud uvedený algoritmus je prohledáváním do hloubky. Protože pokaždé voláme funkci dvakrát a hloubka rekurze je n, je složitost 2n. Nicméně, některé instance řešíme vícekrát a můžeme tedy uschovávat řešení. Protože podúlohy pracují vždy s i prvými věcmi a množiny V and C lze považovat za globální, každá podúloha je charakterizována hodnotami n a M. Proto pamět mezivýsledků můžeme uspořádat do dvourozměrného pole indexovaného hodnotami n a M. Pole má n.M prvků a taková je i složitost algoritmu. Je polynomiální ve velikosti instance, nicméně obsahuje parametr, který s velikostí instance nesouvisí. Takové algoritmy se nazývají pseudopolynomiální. Dynamické programování může být buď složeno z dopředné a zpětné fáze nebo může obsahovat jen zpětnou fázi. V dopředné fázi začínáme od původní úlohy v prvku (n, M) pole a rekurzivně označujeme podúlohy, které potřebujeme řešit, až narazíme na triviální podúlohy. Ve zpětné fázi vyřešíme nejprve označené triviální podúlohy (resp. všechny triviální podúlohy, nemáme-li dopřednou fázi). Pak řešíme takové označené (resp. všechny takové) úlohy, které lze řešit pomocí úloh již vyřešených a v tabulce uložených, až dospějeme k celkovému řešení.
Detailní příklad dekompozice podle ceny
Nechť n = 5, V = (2,6,5,3,4), C = (5,9,20,12,18), a M = 10. Začneme ve sloupci n = 0 a postupně plníme tabulku doprava. Výsledné řešení je určeno polem v posledním sloupci, které obsahuje váhu menší než M a má maximální index. Jestliže pole (n-1, c) obsahuje váhu stejnou jako pole (n, c), pak n-tá věc není součástí optimálního řešení Takto se dá rekonstruovat vektor X z tabulky.
W(n, c) 64 63 62 61 60
20
59
18
58 57 56 55
14
54 53 52
17
51 50
12
49 48 47 46
15 16
16
45 44
15
43
11
42 41
14
14
40 39
13
38 37
9 10
10
36 35
9
34
13
13
13
8
8
33 32 31 30
7
29
11
11
11
28 27
10
26 25
7
11
11
7
7
24 23
6
22 21 20
5
9
9
5
5
19 18
4
17
5
5
8
8
16 15 14
8
8
13 12
3
3
11 10 9
6
6
6
6
2
2
2
2
2
0
0
0
0
0
8 7 6 5 4 3 2 1 0
0
n
0
1
2
3
4
5
V
2
6
5
3
4
C
5
9
20
12
18
Optimální řešení je tedy (00101), cena 38, váha 9.
i
MI-PAAknapsack.pdf
ii
tamtéž
