OJI - Text

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 f₂₀ , 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, f₂₀ = f₁₈ + f₁₉ . 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 f_n = f_n-2 + f_n-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 f_n-1 = f_n-3 + f_n-2 și f_n-2 = f_n-4 + f_n-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 f₁ = f₂ = 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.

Cod:

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ă f_n = f_n-2 + f_n-1 a unui număr Fibonacci, figură realizată cu yEd)

În arborele de recurență de mai sus se observă că f_n-4 este calculat deja de 4 ori. Dacă am extinde arborele, am observa că f_n-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 f₂₀.

termen	count
f₁	2584
f₂	4181
f₃	2584
f₄	1597
f₅	987

Clar nu vrem să calculăm f₂ 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.

Cod:

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
f₁	1
f₂	1
f₃	1
f₄	1
f₅	1

și, mai mult, continuă cu 1 până la f₂₀.

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.

Cod:

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 iepuri

Putem 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 g_n.

Spre exemplu, cum am putea găsi g₆? 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ă, g₆ = 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 g₆, g₆ = 1 + max(g₃, g₄) . 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 g_n = 1 + max(g_a₁, g_a₂, ... , g_{a_m}) unde cuvintele de indici a₁, a₂, ... , a_n 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 g_n = 1 + max(g_a₁, g_a₂, ... , g_{a_m}) ce indice a_k a ales funcția max. În exemplul de mai sus, pentru iepuri am fi ținut minte andrei, pentru că la andrei aveam g₄ = 2 iar la câini g₃ = 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(g_a₁, g_a₂, ... , g_{a_m}) pentru indicii de forma a_k dacă aveam o muchie care pleca de la cuvântul (nodul) de indice a_k ș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ă.

	Ajutor	Subiect: OJI - Text (Citit de 9601 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.

infoarena informatica de performanta