D&C DP (optimizarea divide et impera)

Introducere

Să considerăm o dinamică cu următoarea formulă:

$dp(i,j) = \min_{0\leq k \leq j} ( dp(i-1, k-1) + C(k,j))$

unde $C(i,j)$ este o funcție de cost care poate fi calculată în $O(1)$ . De asemenea, $dp(i,j) =0$ pentru $j<0$ .

O implementare simplă ne-ar da o complexitate de $O(M \cdot N^2)$ dacă $0 \leq i < M$ și $0\leq j < N$ , deci se impune găsirea unei optimizări care să îmbunătățească soluția.

În cele ce urmează, vom prezenta tehnica Divide & Conquer DP, care ne va permite să optimizăm această dinamică la $O(M \cdot N \log N)$ .

Mai întâi, vom defini pentru un $(i, j)$ oarecare $\text{opt}(i,j)$ ca fiind valoarea care minimizează expresia din ecuație. Astfel, D&C DP se aplică doar dacă $\text{opt}(i,j) \leq \text{opt}(i,j+1).$

De multe ori, demonstrația poate fi dificil de găsit, dar dacă funcția de cost respectă quadrangle inequality, condiția se aplică.

Sfat

De multe ori, dacă credeți că problema pe care o rezolvați are o asemenea optimizare în spate, puteți începe prin a scrie o soluție brută, iar dacă $\text{opt}(i,j) \leq \text{opt}(i,j+1).$ se aplică, sunt șanse mari să puteți folosi această optimizare cu destul de mult succes.

Astfel, vom putea aplica ideea din spatele divide et impera. Pentru un interval $(L, R)$ , știm punctele posibile care pot fi optime $(opt_L, opt_R)$ . Astfel, vom încerca să calculăm dinamica pentru valoarea din mijloc, iar în funcție de valoarea optimă găsită (o notăm $opt$ ), vom împărți intervalele recursiv în două, după cum urmează:

$(L, mid-1)$ , respectiv $(opt_L, opt)$
$(mid+1, R)$ , respectiv $(opt, opt_R)$ .

Vom continua acest lucru până când ajungem la intervale unitare, caz în care ne vom opri.

Deoarece fiecare valoare a $\text{opt}(i, j)$ apare de $O(\log n)$ ori, vom avea o complexitate finală de $O(mn \log n)$ .

Problema exemplu - Subarray Squares

View Problem

CSES

Deschide

Notă

Această problemă are și o soluție video postată de Algorithms Conquered aici.

Pentru a rezolva această problemă, ne putem gândi mai întâi la o dinamică simplă dar care este prea înceată, în stilul celei descrise mai devreme în articol.

Totuși, se poate observa că proprietatea legată de valorile optime pentru fiecare stare se respectă, ceea ce ne duce cu gândul la aplicarea tehnicii D&C pentru implementarea acestei probleme.

Recomandăm citirea implementării de mai jos, deoarece este una educațională și instructivă și pentru celelalte probleme pe care le veți rezolva folosind această tehnică.

--8 < --"avansat/dc-dp/subarraysquares.cpp"

Problema suxumetre

View Problem

Kilonova

Could not fetch problem details

Deschide

Dinamicele de genul sunt foarte clasice, chiar au o optimizare foarte faină. Pentru un dp cum ar fi $dp_{i, j} = min(dp_{i - 1, k} + C(k + 1, j)$ , notăm $opt(i, j)$ ca fiind "the optimum splitting point" și egal cu $k$ -ul care minimizează $dp_{i, j}$ .

Atunci putem spune că $opt(i, j - 1) \leq opt(i, j)$ pentru oricare $(i, j)$ doar dacă oricum am alege patru indici $(a, b, c, d), C(a, b) + C(b, d) \leq C(a, d) + C(b, c)$ ;

$C(x, y) = \sum_{x \leq i \leq j \leq y}{}sp(i, j) \text{, unde } sp(i, j) = \sum_{k = i}^{j}v_k\mod{m}$

Conform definiției avem $sp(x, y) \geq 0$ și $C(x, y) \geq 0$ .

abcd_ok

În primul rând, vom analiza ce intervale contribuie la costurile din inegalitatea de mai sus. Distingem trei tipuri de intervale:

interval roșu: inclus în $[a, c]$ sau $[b, d]$ , dar nu în $[b, c]$ .
interval albastru: inclus în $[b, c]$ .
interval verde: inclus în $[a, d]$ , dar nu în $[a, c]$ sau $[b, d]$ .

Vom scrie membrul stâng și membrul drept al inegalității în funcție de cele trei tipuri de intervale:

$C(a, c) + C(b, d) = \sum sp(interval_{roșu}) + 2 \sum sp(interval_{albastru})$
$C(a, d) + C(b, c) = \sum sp(interval_{roșu}) + 2 \sum sp(interval_{albastru}) + \sum sp(interval_{verde})$
$C(a, c) + C(b, d) \leq C(a, d) + C(b, c) \Leftrightarrow 0 \leq \sum sp(interval_{verde})$

ceea ce este adevărat din definiția funcției $sp(x, y)$ .

Putem deci să dezvoltăm un algoritm tip "divide and conquer", unde vom împărți succesiv vectorul în două intervale $[st, mij], [mij + 1, dr]$ și să calculăm dinamica pentru $mij$ în intervalul $[opt(i, st), opt(i, dr)]$ .

Complexitatea finală va fi astfel $O(k \cdot n \ log \ n)$ .

--8 < --"avansat/dc-dp/suxumetre.cpp"

D&C DP (optimizarea divide et impera)

Introducere

Problema exemplu - Subarray Squares

View Problem

Problema suxumetre

View Problem

Concluzii

Probleme suplimentare

Resurse suplimentare

On this page