Da, recunosc și eu că soluțiile oficiale de la problemele de la olimpiade și implementarea lor lasă de dorit uneori.
Luând în calcul că problema s-a mai dat la olimpiadă, și o soluție este deja existentă pe internet, o să-mi iau libertatea să dau și eu o descriere a aceleiași soluție. Cu toate astea, ca să nu se supere lumea pe mine, o să dau și ceva lucruri mai generale, poate învățăm cu toții din asta.
Trecând peste partea cu determinarea numărului de cuvinte din datele de intrare, avem în față o problemă clasică de programare dinamică, dar puțin deghizată, ce-i drept.
Acum probabil întrebarea este
ce este programarea dinamică și de unde vine ea?Un lucru este sigur, nu are legătură cu alocarea dinamică sau alte chestii legate de limbajul de programare. Zic asta pentru că am văzut că mai există confuzii pe alocuri când se aude prima dată de acest termen. Termenul de
programare dinamică a fost folosit prima dată de către
Richard Bellman în 1953. Pe atunci nu se prea scria cod, iar termenul de
programare era mai degrabă folosit cu sensul de
plănuire. Programarea dinamică este doar o metodă de rezolvare a unor probleme.
Ideea e cam așa – dându-ni-se o problemă, am putea da soluția corectă dacă am ști de dinainte soluția pentru una sau mai multe probleme mai
mici?
De exemplu, problema ar putea fi:
să se determine f20 , al 20-lea termen al șirului lui Fibonacci. Am putea da pe loc soluția problemei dacă am ști al 18-lea și al 19-lea termen,
f20 = f18 + f19 . Pentru că suntem programatori, să facem deja și un program pentru determinarea unui asemenea termen Evident, nu o să facem un program care doar ne afișează al 20-lea termen, sau doar al
x-lea termen, ci o să facem un program care ne dă al
n-lea termen, pentru un
n luat cumva din niște date de intrare. Știm că, în general, pentru determinarea unui termen al șirului lui Fibonacci ne este de ajuns să cunoaștem cei doi termeni precedenți ai șirului. Dacă îi cunoaștem, putem folosi imediat formula
fn = fn-2 + fn-1 și să obținem rezultatul. Dacă nu îi cunoaștem, atunci vrem să îi calculăm. Observăm că am obținut acum alte două probleme, dar care sunt mai
mici decât cea inițială. Putem folosi iar formula de recurență a șirului lui Fibonacci ca să obținem câte alte două probleme pentru fiecare din cele două obținute precedent, mai exact
fn-1 = fn-3 + fn-2 și
fn-2 = fn-4 + fn-3. Putem continua în aceasă manieră până când ajungem la o problemă pe care o putem rezolva trivial, aceea se va numi
cazul de bază (pot fi și mai multe). În situația noastră, cazurile de bază sunt
f1 = f2 = 1. Am obținut deci un algoritm recursiv care ne rezolvă problema determinării unui termen de indice
n al șirului lui Fibonacci pentru un
n arbitrar. Să vedem și codul în C++ pentru un astfel de algoritm.
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
}
return fibonacci(n - 2) + fibonacci(n - 1);
}
Cu toate că folosind acest algoritm recursiv obținem soluția corectă, algoritmul este ineficient. Dezvoltând după formula de recurență, putem observa că recalculăm inutil unii termeni ai șirului.
(arbore de recurență de adâncime 3 pentru formula generală
fn = fn-2 + fn-1 a unui număr Fibonacci, figură realizată cu
yEd)
În arborele de recurență de mai sus se observă că
fn-4 este calculat deja de 4 ori. Dacă am extinde arborele, am observa că
fn-4 este calculat chiar de mai multe ori. Ca exemplu, următorul tabel ne arată de câte ori calculăm fiecare din primii 5 termeni ai șirului, dacă folosim algoritmul de mai sus pentru a calcula
f20.
| termen | count |
| f1 | 2584 |
| f2 | 4181 |
| f3 | 2584 |
| f4 | 1597 |
| f5 | 987 |
Clar nu vrem să calculăm
f2 de 4181 ori, până și pe hârtie putem face mult mai bine de atât.
Acest fapt ne conduce la o optimizare naturală, care este și o tehnică foarte folositoare la olimpiade și alte concursuri. Aceasta se numește memoizare (engleză -
memoization). Termenul a fost folosit prima dată în 1968 de către
Donald Michie, care, ca și
Alan Turing, a lucrat la Bletchley Park în timpul celui de-Al Doilea Război Mondial. Memoizarea nu este decât faptul de a memora anumite rezultate pentru a nu le recalcula.
În exemplul de față, este ușor să facem acest lucru. Concret, vom menține un vector de
n elemente în care vom memora dacă am mai calculat sau nu înainte un termen și, dacă da, care a fost rezultatul. Pentru a vedea dacă am mai calculat sau nu termenul în cauză, vom inițializa vectorul cu
-1, folosindu-ne de faptul că un termen al șirului lui Fibonacci este mereu pozitiv, deci dacă vectorul la indicele termenului pe care vrem să îl calculăm este mai mare decât
-1 atunci înseamnă că am mai calculat termenul înainte. Codul în C++ este mai jos.
int mem[100];
int fibonacci(int n) {
if (mem[n] == -1) {
if (n == 1 || n == 2) {
mem[n] = 1;
} else {
mem[n] = fibonacci(n - 2) + fibonacci(n - 1);
}
}
return mem[n];
}
Folosind memoizare, tabelul de mai sus devine
| termen | count |
| f1 | 1 |
| f2 | 1 |
| f3 | 1 |
| f4 | 1 |
| f5 | 1 |
și, mai mult, continuă cu 1 până la
f20.
Acestă tehnică este foarte utilă, dar putem mai bine de atât! Putem chiar să scăpăm de recursivitate și să creăm un algoritm iterativ. Ce am făcut mai sus se numește o abordare
top-down. Ce urmează să facem se numește, intuitiv,
bottom-up.
În cazul șirului lui Fibonacci ne este ușor să trecem la abordarea dorită. Ne este ușor din două puncte de vedere. Primul este că un termen al șirului lui Fibonacci depinde doar de indicile său, este
o funcție de o singură variabilă. Al doilea este că formula de recurență este simplă, nu depinde decât de două rezultate precedente.
Întrebarea mai clară aici este
am putea calcula valorile vectorului mem în timp liniar, fără a folosi un algoritm recursiv? (partea cu
liniar este specifică probleme pe care o rezolvăm acum)
Primul pas ar fi să punem cazurile de bază,
mem[1]=1 și
mem[2]=1. Următorul pas ar fi să observăm că putem calcula acum
mem[3], care este
mem[1]+mem[2]. Continuând tot așa pentru
mem[4],
mem[5],
mem[6], etc, obținem un simplu algoritm iterativ pentru a calcula valorile vectorului.
mem[1] = 1;
mem[2] = 2;
for (int i = 3; i < n; ++i) {
mem[i] = mem[i - 2] + mem[i - 1];
}
Acum putem spune oficial că am folosit
programare dinamică. Codul de mai sus mai poate fi optimizat, dar optimizarea nu aduce nimic în plus ideii în discuție.
___________________________________________________________
Să încercăm acum să ne îndreptăm acum spre problema
Text, de la care a pornit cam toată discuția. Problema ne cere mai exact, cum am zis în postările anterioare,
secvența maximală de cuvinte (nu neapărat consecutive în datele de intrare) care are proprietatea că oricare două cuvinte consecutive din secvență îndeplinesc proprietatea cerută. O pereche de cuvinte îndeplinește proprietatea dacă și numai dacă ultima literă a primului cuvânt este aceeași cu prima literă a celui de-al doilea. Să ne luăm un exemplu mai ușor:
ana are caini andrei are iepuriPutem reprezenta grafic exemplul cu diagrama de mai jos.
(reprezentarea grafică a exemplului de mai sus, figură realizată cu
yEd)
Am pus o săgeată de la un cuvânt la altul dacă ce de-al doilea vine după primul în datele de intrare și ultima literă a primului este prima literă de celui de-al doilea.
Acum problema este mai ușor de văzut, ni se cere să găsim un
drum de lungime maximă. Prin drum înțelegem o secvență de cuvinte legate prin săgeți ca în diagrama de mai sus. Evident, săgețile trebuie să fie orientate înspre dreapta, nu puteam schimba ordinea cuvintelor. Pentru asta, vom rezolva probleme similare cu cele în care găseam un termen al șirului lui Fibonacci, dar de data aceasta vom folosi o altă formulă de recurență. Mai exact, problemele pe care vrem să le rezolvăm sunt de tipul
care este lungimea maximă a unei secvențe care se termină la al n-lea cuvânt din datele de intrare și corespunde cu cerința problemei? Nu prea sună la fel, dar în realitate este. O să notăm răspunsul la întrebări de genul acesteia cu
gn.
Spre exemplu, cum am putea găsi
g6? Ei bine, lungimea secvenței care se terină la cuvântul
iepuri este cel puțin 1 pentru că, evident, secvența include cel puțin cuvântul
iepuri. Desigur, răspunsul nu este chiar 1, dar deja începem să construim o formulă,
g6 = 1 + (ceva) . Observăm acum ușor pe diagramă că singura modalitate de a ajunge la cuvântul
iepuri, în caz că nu am plecasem chiar de acolo, este ori prin cuvântul
andrei (indice 4), ori prin cuvântul
câini (indice 3). Dar nu le putem adăuga pe ambele. Trebuie să alegem una dintre cele două modalități. Ținând cont că vrem să aflăm lungimea maximă, ar trebui să o adăugăm pe cea cu valoarea
g mai mare. Deci, obținem formula pentru
g6,
g6 = 1 + max(g3, g4) . Este indicat să vedem
prin această formulă. Practic ea zice că dintre cele două modalități de a ajunge la cuvântul 6, noi o vrem pe cea mai bună, mai bună în acest caz înseamnă mai
lungă.
Putem generaliza acum ușor această formulă recurentă. De la un cuvânt de indice
n vrem să alegem cel mai lung drum care ajunge la cuvântul
n. Deci, mai concis
gn = 1 + max(ga1, ga2, ... , gam) unde cuvintele de indici
a1, a2, ... , an au ca ultimă literă prima literă a cuvântului de indice
n.
Acum că știm formula, povestea este aceeași ca la șirul lui Fibonacci, putem rezolva problema recursiv
top-down, unde putem optimiza folosind memoizare, sau o putem rezolva iterativ
bottom-up. Ar fi câteva lucruri de menționat. Primul este că răspunsul nu va mai găsit chiar în același loc ca la Fibonacci, ci vor mai fi de făcut câteva mici calcule. Al doilea este că nu suntem mulțumiți doar cu găsirea lungimii secvenței care trebuie eliminată, ci vrem și secvența în sine, lucru care se face ușor dacă ținem minte cumva la fiecare utilizare a formulei
gn = 1 + max(ga1, ga2, ... , gam) ce indice
ak a ales funcția
max. ÃŽn exemplul de mai sus, pentru
iepuri am fi ținut minte
andrei, pentru că la
andrei aveam
g4 = 2 iar la
câini g3 = 1, deci era de preferat să fi
venit de la cuvântul
andrei pentru că drumul era mai lung. Mai exact, ținem minte
de unde am venit. Acest lucru (găsirea subsecvenței în sine) nu ține direct de programare dinamică, așa că nu o să îl descriu în detaliu.
Astea fiind zise, avem acum o direcție destul de bună ca să începem să implementăm problema. Din diferite motive, am ales să nu pun aici codul, dar problema se rezolvă, cum am zis mai sus, aproximativ la fel ca cea a șirului lui Fibonacci.
___________________________________________________________
Mai jos sunt câteva chestii puțin mai avansate și care deviază de la subiect.
Este interesant de văzut, pentru cei care sunt la început și deja au învățat despre grafuri, că sub orice problemă de dinamică (i.e. care poate fi rezolvată folosind metoda programării dinamice) stă de fapt un graf aciclic orientat, sau
DAG (directed acyclic graph). Chiar dacă problema pare că nu are absolut nicio legătură cu grafurile, ea se poate modela ca o problemă pe un DAG în mod natural. Nodurile DAG-ului sunt subproblemele pe care vrem să le rezolvăm, iar muchiile sunt dependențele între probleme. Dacă alegem această reprezentare, este evident de ce vrem ca graful să fie aciclic – nu vrem dependențe circulare. În problema de mai sus se vede clar acest lucru. Diagrama aceea era de fapt un DAG, iar în formulă foloseam acel
max(ga1, ga2, ... , gam) pentru indicii de forma
ak dacă aveam o muchie care pleca de la cuvântul (nodul) de indice
ak și ajungea în nodul pentru care făceam calculul. Găsirea celui mai lung subșir crescător, este exact aceeași problemă ca cea de mai sus, deci acesta este încă un exemplu. Alt exemplu – găsirea celui mai lung subșir comun, graful arată frumos dacă îl aranjăm ca o
pânză, adică nodurile puse ca într-un tablou dibimensional, soluția ar fi atunci pe o
plimbare dintr-un colț al grafului în colțul opus, fără să schimbăm
sensul, soluția în sine ar fi ce obținem dacă selectăm din acea
plimbare doar acele mișcări pe diagonală. Aceste grafuri ne oferă, printre altele, o posibilitate de a vizualiza mai clar problemele, scăpând de cea a tablourilor 1-, 2-, 3- sau mai știu cu cât-dimensionale unde mai toate problemele arată la fel – un tablou și-o formulă.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena