Clasa a IX-a lecția 25 - 16 mai 2020

From Algopedia
Revision as of 09:30, 24 May 2020 by Teodor (talk | contribs) (→‎Backtracking)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Clasament teme lecțiile 1 - 24

Pe categorii

Divizori / Primalitate / Ciur
Sortări
Matrici
Căutare binară
Stivă
Recursivitate
Parcurgeri matrice
Divide et Impera
Programare dinamică
Generale

Concursuri

Probleme OȘI
Probleme OJI

Lecție

Backtracking

Așa zisa metodă backtracking reprezintă generarea tuturor soluțiilor unei probleme, urmând ca mai apoi să se aleagă soluția optimă dintre acestea. Am folosit această metodă la diverse probleme în lecțiile anterioare (Numere8, Rețetă, în care am fost nevoiți să generăm toate submulțimile unei mulțimi. Am făcut acest lucru cu ajutorul descompunerii într-o bază de numerație (în baza 2 pentru problema Numere8, în baza 3 pentru problema Rețetă). Am specificat și atunci de existența unei alte tehnici numită backtracking, dar generarea submulțimilor folosind baze de numerație este o tehnică superioară, fiind mult mai rapidă și mai simplu de scris în practică.

La ce este atunci bună această tehnică de backtracking? Cum procedăm atunci când vrem să generăm nu toate submulțimile unei mulțimi, ci toate combinările, sau toate permutările?

Combinări

Enunț

Să se genereze toate combinările de N luate câte K în ordine lexicografică.

Exemplu

Pentru N = 4, K = 3, avem: 1 2 3
1 2 4
1 3 4
2 3 4

Soluție

Vom declara un vector de lungime K. Vom genera toate combinările pe rând cu ajutorul vectorului și le vom afișa. Vom parcurge pozițiile de la stânga la dreapta, și pe fiecare poziție în parte vom încerca să punem toate valorile posibile. După ce setăm o valoare pe o anumită poziție, trecem la următoarea poziție și tot așa, până completăm combinarea, pe care o vom afișa. Apoi ne vom întoarce și vom continua să punem celelalte valori rămase valori în fiecare poziție din vector.

Poate sună complicat, dar având în vedere proprietățile recursivității, algoritmul este chiar foarte simplu de scris:

// avem completate toate pozitiile de la 1 la pos - 1
// vrem sa completam pozitia pos
void bkt(int pos) { 
  if (pos == k + 1) {
    // am completat toate pozitiile
    // afisam vectorul
    for (int i = 1; i <= k; ++i)
      printf("%d ", v[i]);
    printf("\n");
  } else { 
    // completam pozitia pos
    // incepem de la valoarea trecuta in pozitia anterioara + 1
    for (int val = v[pos - 1] + 1; val <= n; ++val) {
      v[pos] = val; // scriem valoarea in vector la pozitia pos
      bkt(pos + 1); // apelam functia pentru pos + 1
    }
  }
}

Permutări

Enunț

Avem mulțimea {1, 2, ..., N}. Să se afișeze toate permutările mulțimii.

Exemplu

Pentru N = 3, avem: 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Soluție

Soluția este similară cu cea folosită pentru generarea combinărilor. De această dată, fiind vorba de permutări, nu vrem să avem elemente duplicate și nu ne putem baza pe faptul că elementele sunt în ordine crescătoare. Deci, trebuie să verificăm soluția în momentul obținerii acesteia.

// functie care returneaza daca in vector avem o permutare
bool perm() {
  ...
}

// avem completate toate pozitiile de la 1 la pos - 1
// vrem sa completam pozitia pos
void bkt(int pos) {
  if (pos == n + 1) {
    // am completat toate pozitiile
    // verificam daca este o permutare
    if (perm()) {
      // afisam
      for (int i = 1; i <= n; ++i)
        printf("%d ", v[i]);
      printf("\n");
    }
  } else {
    // completam pozitia pos
    // trecem prin toate valorile posibile
    for (int val = 1; val <= n; ++val) {
      v[pos] = val; // scriem valoarea in vector la pozitia pos
      bkt(pos + 1); // apelam functia pentru pos + 1
    }
  }
}

Putem mai bine decât să verificăm de fiecare dată când generăm o soluție dacă aceasta este optimă? Da! Putem verifica de fiecare dată când introducem o valoare în vector, dacă aceasta a mai fost deja introdusă. Vom folosi un vector caracteristic pentru asta.

// avem completate toate pozitiile de la 1 la pos - 1
// vrem sa completam pozitia pos
void bkt(int pos) {
  if (pos == n + 1) {
    // am completat toate pozitiile
    // stim deja ca este o permutare, ne-am asigurat cand am construit solutia
    // afisam
    for (int i = 1; i <= n; ++i)
      printf("%d ", v[i]);
    printf("\n");
  } else {
    // completam pozitia pos
    // trecem prin toate valorile posibile
    for (int val = 1; val <= n; ++val)
      if (!marked[val]) {    // daca valoarea nu este marcata
        v[pos] = val;        // scriem valoarea in vector la pozitia pos
        marked[val] = true;  // marcam valoarea ca fiind folosita
        bkt(pos + 1);        // apelam functia pentru pos + 1
        marked[val] = false; // la intoarcere, valoarea nu mai este folosita, o demarcam
      }
  }
}

Problema rucsacului fracționar

Enunț

Se dau N obiecte pentru care se cunosc greutatea g si pretul p si un rucsac de capacitate G. Se cere sa se calculeze si sa se afiseze profitul maxim ce se poate obtine adaugand o submultime din cele N obiecte in rucsac. Se pot selecta si fractiuni ale obiectelor. Profitul este suma preturilor integrale la care se adauga fractiuni ale preturilor pentru obiectele selectate partial.

Exemplu

Avem G = 4 și următoarele obiecte:

Nr. 1 2 3
Greutate 2 2 1
Valoare 4 5 3

Pentru a obține profitul maxim, vom lua 1 unitate din al treilea obiect, 2 unități din cel de-al doilea și 1 unitate din primul. Vom avea deci suma egală cu 10.

Soluție

Având în vedere că putem lua fracțiuni din fiecare obiect, merită să luăm mai întâi cât se poate din obiectele rămase ale călor valoare per unitate este cea mai mare, repetând procedeul până când fie epuizăm toate obiectele, fie umplem rucsacul.

Vom sorta descrescător obiectele după valoarea lor per unitate (raportul preț / greutate) și vom aplica algoritmul descris mai sus.

Tipul acesta de rezolvare, în care la fiecare pas luăm soluția optimă locală pentru ca la final să obținem soluția optimă globală mai poartă și numele de Greedy. Atenție totuși, alegând la fiecare pas soluția locală optimă nu ne garantează întotdeauna că obținem soluția globală optimă.

Complexitate

Din punct de vedere al timpului, avem o complexitate egală cu O(N logN), datorită sortării.

Atenție Pentru a sorta vectorul, trebuie să comparăm fracții (exemplu: p[i]/g[i] ? p[j]/g[j]). Făcut direct, acest lucru este ineficient pentru că ne obligă să folosim tipul de date float. Algoritmul se va mișca mai lent și putem întâlni probleme de precizie. Putem să transformăm această comparație într-o comparație de produse (exemplu: p[i]*g[j] ? g[i]*p[j]). Păstrăm astfel tipul de date int, algoritmul este eficient și nu avem probleme de precizie.

Din punct de vedere al spațiului consumat, algoritmul nu ocupă memorie în plus, ocupând astfel O(1) spațiu suplimentar.

Problema rucsacului

Enunț

Este aceeași problemă ca cea anterioară, doar că de această dată nu putem lua fracțiuni de obiecte, ci suntem obligați să luăm obiectele întregi.

Exemplu

Avem G = 4 și următoarele obiecte:

Nr. 1 2 3
Greutate 2 2 1
Valoare 4 5 3

Vom lua primele două obiecte, obținând suma 9.

Soluție

Soluția prezentată la varianta fracționară a problemei nu funcționează în acest caz (după cum se poate observa și din exemplu). Soluția corectă implică programare dinamică. Un mit popular este că problemele care "par" că se rezolvă folosind metoda Greedy, dar produc răspunsuri incorecte, se pot rezolva folosind programarea dinamică. Este totuși doar un mit și trebuie tratat ca atare. Nu este întotdeauna adevărat!

O soluție corectă ar fi o metodă de tip backtracking, generând toate submulțimile posibile. Evident, această soluție nu este tocmai eficientă, având o complexitate egală cu O(2N), unde N este numărul de obiecte.

Cum construim dinamica pentru această problemă? Variantele "simple", de 1 singură dimensiune, folosite în lecția anterioară nu vor funcționa pentru că în această problemă ne confruntăm cu două dimensiuni: atât greutatea rucsacului și valoarea obiectelor.

Exemplu:

  • D[i] = suma maximă care se poate obține dintr-o submulțime a primelor i obiecte. Nu avem deloc informații despre cât loc mai avem disponibil în rucsac la fiecare pas.
  • D[g] = suma maximă care se poate obține într-un rucsac de greutate g. Nu avem deloc informații despre ce obiecte am selectat deja, pentru a ne asigura că nu luăm un obiect de două ori.

Vom construi deci o dinamică pe două dimensiuni:

  • D[i][g] = suma maximă care se poate obține dintr-o submulțime a primelor i obiecte, într-un rucsac de mărime g.

Răspunsul problemei se află chiar în D[N][G].

Cum calculăm D[N][G]? Vom porni cu un indice i de la stânga la dreapta șirului de obiecte, și pentru fiecare i vom parcurge toate greutățile cu o variabilă g de la 0 la G. La fiecare pas, avem de ales între a introduce sau nu în rucsac cel de-al i-lea obiect. Avem astfel:

  • D[i][g] = D[i - 1][g]; dacă alegem să nu introducem în rucsac obiectul
  • D[i][g] = D[i - 1][g - g[i]] + p[i], unde g[i] și p[i] reprezintă greutatea și prețul celui de-al i-lea obiect; dacă alegem să introducem obiectul

Vom alege evident, varianta optimă dintre acestea, deci D[i][g] = max(D[i - 1][g], D[i - 1][g - g[i]] + p[i]).

for (int i = 0 i < N; ++i)
  for (int s = 0; s <= G; ++s) {
    d[i][s] = d[i - 1][s];
    if (g[i] <= s) // ne asiguram ca avem suficient spatiu in rucsac
      d[i][s] = max(d[i][s], d[i - 1][s - g[i]] + p[i]);
  }

Complexitate

Complexitatea de timp a algoritmului este O(N*G).

Din punct de vedere al spațiului consumat, acesta este egal tot cu O(N*G). Poate fi optimizat către O(G) observând că la fiecare pas, ne folosim doar de rezultatele din linia anterioară.

for (int i = 0; i < N; ++i)
  for (int s = 0; s <= G; ++s) {
    d[i & 1][s] = d[(i - 1) & 1][s];
    if (g[i] <= s)
      d[i & 1][s] = max(d[i & 1][s], d[(i - 1) & 1][s - g[i]] + p[i]);
}

Temă

Da, știu că pare o temă foarte stufoasă. Dar problemele sunt similare, deci nu vă fie frică! :P

infoarena - Combinări
infoarena - Permutări
infoarena - Submulțimi
varena - Submulțimi
varena - Permfix
varena - Trei cifre consecutive
varena - Partițiile unui număr
infoarena - Flip
varena - Regine

varena - Rucsac fracționar
varena - Rucsac1
infoarena - Problema rucsacului
infoarena - Jocul
varena - Camelot