Clasa a 7-a Lecția 26: Programare dinamică (3)
Înregistrare video rezolvarea temei
În continuare vom studia exemple de probleme de programare dinamică și probleme suprapuse date la olimpiadă.
Problema Faleza
Problema Faleza a fost dată la ONI 2017 clasa a 6-a. Ea este o problemă de un anumit gen, care se întâlnește din când în când la olimpiadă: probleme mascate, care au o soluție medie sau chiar grea, fără programare dinamică, dar care admit o soluție banală cu programare dinamică.
Atâta vreme cât programarea dinamică nu este în programa de olimpiadă de clasa a șasea, după părerea mea genul acesta de probleme nu sunt bune de concurs, deoarece încurajează dopajul, nu gândirea algoritmică și aprofundarea cunoștințelor. În cazul problemei Faleza cine știe programare dinamică o poate termina în 15 minute. Cine nu, va trebui să găsească un algoritm care nu e deloc evident (mai ales la casa a 6-a), petrecând, probabil, peste o oră.
Soluția comisiei
Construim două tablouri pe care le notăm A și B, cu numerele din fișier, în A cele de pe o parte a falezei și în B cele de pe cealaltă. Pentru simplificarea implementării, dacă avem poziții i în care A[i] = 1 și B[i] = 1 putem să analizăm doar ce se întâmplă între două astfel de poziții consecutive.
Parcurgem element cu element și păstrăm mereu ultima poziție pe care se află o dală bună pentru șirul A respectiv pentru șirul B, alegând, în funcție de acestea, modul de a completa dalele deteriorate.
Timpul de executare este liniar.
După părerea mea este puțin vagă. În mod cert e nevoie de o analiză care nu pare simplă.
Soluție cu programare dinamică
Să simplificăm puțin enunțul: se cere să reparăm cât mai puține dale pentru a se putea ajunge de la un capăt la celălalt. Cu alte cuvinte se cere un drum care să treacă prin cât mai puține dale rupte. Dacă vom schimba codarea dalelor, cele rupte cu 1 și cele întregi cu 0, rezultă că trebuie să găsim un drum de sumă minimă.
O observație simplă, dar esențială, este că drumul minim nu se va întoarce de la dreapta la stânga. Într-adevăr, este clar că nu are de ce. Putem, deci, calcula drumurile de la stânga la dreapta.
Drept care o definiție evidentă a problemei de programare dinamică este:
S[l][c] = suma unui drum de sumă minimă pentru a ajunge în punctul (l, c).
Demonstrație de optimalitate a subprobemelor o las în seama voastră, fiind simplă.
Formula de recurență este iarăși simplă:
- Într-o dală de sus putem ajunge fie dinspre stânga, fie din jos în sus.
- Într-o dală de jos putem ajunge fie dinspre stânga, fie din sus în jos.
Vom lua în considerare minimul dintre cele două variante.
Formula de recurență este:
![{\displaystyle S[l][c]={\begin{cases}D[l][c],&{\mbox{dacă }}c=0\\D[l][c]+min(S[l][c-1],S[1-l][c-1]+D[1-l][c])&{\mbox{în caz contrar}}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/996c907463fbc4ef1ab265cfe9518d49cd90853f)
Am considerat că D[l][c] este codificarea dalei din linia l și coloana c. Liniile și coloanele sunt numerotate de la 0.
Răspunsul cerut este minimul dintre S[0][n-1] și S[1][n-1].
Ce complexitate are această soluție?
Timpul este evident O(n).
Memoria ar putea fi O(1) dacă dalele ar fi date pe linii, nu pe coloane. Așa cum este enunțul suntem obligați să le stocăm, ceea ce duce la memorie O(n). Putem însă refolosi matricea de dale pentru a calcula sumele minime. Drept care memoria va fi de 2n întregi, adică 800KB.
Exemplu
Iată exemplul din enunț calculat conform formulei de mai sus.
Dalele originale (0 = întreagă, 1 = ruptă):
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
Calculul drumurilor minime pe coloane, de la stânga la dreapta:
| 1 | 2 | 2 | 2 | 2 | 3 | 4 | 5 |
| 1 | 2 | 3 | 3 | 3 | 4 | 5 | 5 |
Problema Poteci
Problema poteci a fost dată la ONI 2011 baraj gimnaziu.
Soluția comisiei
Fiind vorba de baraj, soluția este una bazată pe programare dinamică:
Pentru fiecare element din matrice vom calcula drumurile optime până la cele patru colțuri ale matricei.
Parcurgem matricea și determinăm acel element pentru care suma celor patru drumuri este maximă.
Pentru primul pas vom folosi programarea dinamică, o procedură apelată de patru ori. În fapt, vom calcula drumurile optime de la fiecare colț către toate elementele matricei. De exemplu, pentru distanța de la colțul (1, 1) la elementul (i, j) vom avea formula de recurență:
\(D_{1,1}[l][c] = \begin{cases} 0, & \mbox{dacă } l = 0 \mbox{ sau } c = 0\\M[l][c] + \max{(D_{1,1}[l][c-1], D_{1,1}[l-1][c])} & \mbox{în caz contrar}. \end{cases}\)
În final vom alege punctul din matrice (l, c) cu proprietatea:
\(MAX = \max\limits_{1 \leq l \leq L, 1 \leq c \leq C}{(D_{1,1}[l][c] + D_{1,C}[l][c] + D_{L,1}[l][c] + D_{L,C}[l][c])}\)
Ce complexitate are această soluție?
Ea calculează patru matrice, deci atât timpul cât și memoria vor fi O(L·C). Mai exact, vom avea nevoie de patru matrice de elemente întregi de 1000 x 1000 elemente, circa 16MB, plus matricea originală de frumuseți, elemente short int, deci încă 2MB, total 18MB.
Soluție alternativă
O soluție care face mai puține calcule și folosește mai puțină memorie este următoarea.
Observație: perechea optimă de poteci va fi alcătuită din două poteci optime.
Într-adevăr, dacă una din poteci nu ar fi optimă, am putea alege o potecă mai bună care ar duce la o pereche mai bună.
De aici vine și ideea soluției: să calculăm potecile optime pentru cei doi și să alegem punctul de intersecție a lor. Pentru aceasta va trebui să calculăm nu doar frumusețile potecilor, ci și potecile în sine. La final vom calcula intersecția potecilor.
Ce complexitate are această soluție? Ea este, desigur, tot O(L·C) atât ca timp cât și ca memorie. Însă vom calcula doar două matrice, deci timpul se reduce aproximativ la jumate. Iar memoria necesară este de o matrice pentru frumusețile originale (2MB) și o matrice de drumuri (1MB). Pentru a calcula intersecția putem refolosi matricea de drumuri. Necesarul de memorie este, deci, de numai 3MB, comparat cu cei 18MB ai soluției anterioare. Putem reduce și mai mult memoria dacă folosim pentru stocarea drumurilor matrice de biți, caz în care în loc de 1MB vom folosi 125KB, iar memoria totală folosită va fi 2.12MB. Iar folosind algoritmul lui Hirschberg putem elimina complet matricea de drumuri, ceea ce duce la 2MB memorie necesară.
Concluzii:
Timpul se reduce la jumate.
Memoria se reduce la o șesime
Problema Optim
Problema optim a fost dată la ONI 2012 clasa a 8a. Ea are o rezolvare fără programare dinamică, ineficientă și nu chiar banal de implementat și o rezolvare cu programare dinamică, eficientă și relativ ușor de implementat.
Soluția combinatorică, fără programare dinamică
Soluția comisiei, cea combinatorică, se bazează pe generarea tuturor modurilor de a plasa K înmulțiri între N operații și calculul expresiilor respective, din care vom reține minimul și maximul. Implementarea este cea de combinări modificată să calculeze incremental expresiile.
Complexitatea este O(Comb(N, K)). Pentru valori maxime obținem Comb(30, 10), aproximativ 10 milioane operații.
Soluție cu programare dinamică
Problema are două părți echivalente, minimul și maximul. Să ne concetrăm pe maxim, minimul rezolvându-se similar.
O definire directă a subproblemei ar putea fi:
MAX[i][j] = maximul care se poate obține cu numerele nr[0], nr[1], ..., nr[i] folosind i operații, din care j înmulțiri.
Are ea proprietatea de optimalitate?
Să vedem: dacă luăm o soluție optimă și eliminăm ultimul număr și ultima operație, ceea ce rămâne este optim?
Nu neapărat. Dacă ultima operație este o adunare, vom avea o subproblemă optimă, dar dacă este o înmulțire, nu.
Ce facem? Observăm că optimalitatea se păstrează la adunări, nu și la înmulțiri. Deci putem spune că, dacă MAX[i][j] este optim și are m înmulțiri în coadă, atunci și MAX[i-m-1][j-m] este optim, el fiind format din suma produselor anterioare, care dacă nu ar fi optimă am putea construi o sumă mai mare în MAX[i][j].
Astfel, formula de recurență este:
\(MAX[i][j] = \begin{cases} nr[0]\cdot nr[1]\cdot\mbox{…}\cdot nr[i], & \mbox{dacă } i = j\\ \max\limits_{0 \leq m \leq j}{(MAX[i-m-1][j-m] + nr[i-m]\cdot nr[i-m+1]\cdot\mbox{…}\cdot nr[i])} & \mbox{în caz contrar}. \end{cases}\)
Răspunsul la cerință va fi: MAX[N][K].
Ce complexitate are această soluție?
Ea este O(N·K2). Înlocuind vom obține circa 2430 operații, un număr incredibil de mic. Probabil că mai mult va dura citirea celor 30 de numere.
Memoria folosită este cea a matricei de dimensiune N x K, deci O(N·K), din nou neglijabilă.
Exemplu
Iată exemplul din enunț calculat conform formulei de mai sus.
Fie numerele de la intrare:
Indice012345Valoare203-17-4
Calculul expresiilor maxime, pe linii, de la stânga la dreapta:
Înmulțiri0123N u m e r e021202530342204119975753386
Problema Joc6
Problema joc6 a fost dată la ONI 2011 baraj gimnaziu. Este o problemă tipică de programare dinamică.
Soluția comisiei
"Pentru fiecare jucător se determină secvenţele de bile cu valori consecutive. Acest lucru se poate realiza prin utilizarea unui vector caracteristic.
După determinarea secvenţelor, se selectează secvenţa de sumă maximă ce poate fi obţinută prin utilizarea bilelor speciale, în funcţie de numărul de bile speciale pe care le are jucătorul curent. Se determină maximul sumelor maxime şi jucătorul care are acest maxim."
Din păcate explicațiile sunt destul de vagi. Ce bănuiesc eu:
Vom face o listă de secvențe, păstrând pentru fiecare secvență: (indice start, indice final, suma)
Vom încerca să cuplăm secvențe astfel:
Fie două secvențe consecutive dacă ele sunt despărțite de cel mult numărul de bile zero disponibile.
Fie trei secvențe consecutive dacă avem măcar două bile zero, iar secvențele sunt despărțite de fix un zero.
Desigur vom lua maximul sumelor.
Ce complexitate are această soluție?
Pentru detecția secvențelor avem nevoie de un vector de frecvență, deci O(n + p). Pentru parcurgerea secvențelor avem nevoie de O(p) pași. Deoarece avem k jucători complexitatea totală este O(k·(n + p).
Dar memoria? Din cauza vectorului de frecvență vom avea nevoie de O(n + p) memorie.
Este o soluție rezonabilă, poate nu foarte grea, dar care necesită creativitate și gândire algoritmică.
Soluție cu programare dinamică
Această soluție este destul de evidentă. Din păcate ea nu necesită prea multă gândire, ceea ce, după părerea mea, face această problemă să nu fie așa de bună pentru concurs. Totuși, fiind vorba despre baraj gimnaziu, nu este grav.
Putem defini problema de programare dinamică astfel:
S[b][i] = suma maximă ce începe cu bila i, ce se poate obține folosind b bile zero
Unde b poate fi 0, 1, sau 2 în problema noastră, dar nimic nu ne împiedică să îl mărim.
Demonstrația proprietății de optimalitate a subproblemelor este destul de ușoară, v-o las ca temă de gândire.
Recurența este, iarăși, destul de clară:
Dacă bila i există la intrare, atunci o adăugăm la secvența anterioară ce începe cu bila i+1.
Dacă bila i nu există la intrare, atunci folosim o bilă zero. Vom avea deci aceeași valoare cu o secvență ce folosește mai puțin cu unu bile zero și care începe cu bila i+1.
Formula de recurență este:
\(S[b][i] = \begin{cases} 0, & \mbox{dacă } i > n \mbox{ sau } b S[][] pe coloane vom avea nevoie de O(b) memorie, deoarece vom stoca doar o linie, dar O(b) este practic constant. Memorie totală necesară: O(n + b).
Observații:
Obținem un algoritm de complexitate similară ca timp și memorie.
Programul iese foarte scurt, circa 40 de linii efective, mulțumită programării dinamice.
Posibil să fie și ceva mai eficient, dar acest lucru nu contează prea mult deoarece timpul va fi dominat de citire.
Exemplu
Să presupunem că avem următoarele bile la intrare:
Bile20640
Atunci vom calcula tabelul următor:
Bile123456010101Z e r o u r i0020406126410662612101066
Maximul în acest tabel este 12, care este și răspunsul cerut.
Problema Zmax
Problema zmax a fost dată la ONI 2013 baraj gimnaziu.
Soluție cu programare dinamică
Singura soluție de 100p a comisiei este cu programare dinamică.
Vom defini următoarele subprobleme:
S[l][c] = cea mai mare sumă de elemente contigue aflate pe linia l, care se termină la coloana c
D[l][c] = cea mai mare sumă de elemente contigue aflate pe linia l, care încep la coloana c
N7[l][c] = cea mai mare sumă de elemente aflate în matrice în formă de cifra '7' care se termină la (l, c).
Z[l][c] = cea mai mare sumă de elemente aflate în matrice în formă de 'Z' a cărei linie de sus se termină la (l, c).
Primele două subprobleme se pot calcula folosind algoritmul clasic al lui Kadane.
Subproblema N7 se calculează pe baza subproblemelor S și N7, similar cu Kadane: putem continua 7-lea existent, sau să începem unul nou.
Subproblema Z se calculează pe baza subproblemelor D și N7, similar cu Kadane: putem continua Z-ul existent, sau să începem unul nou.
Maximul din subproblema Z este răspunsul la cerință.
Alte probleme
Problema flori2 a fost dată la ONI 2010 baraj gimnaziu. Nu este o problemă foarte grea, dar are multe detalii.
Puteți găsi alte probleme căutând pe Nerdarena după tagul "programare dinamică".
Tema 26
Tema 27 presupune să se rezolve următoarele probleme (program C trimis la NerdArena):
optim
joc6
faleza
Tema 26 opțională
poteci
zmax
flori2
