Clasa a IX-a lecția 21 - 28 mar 2020

From Algopedia
Revision as of 18:58, 2 April 2020 by Teodor (talk | contribs) (→‎Implementare)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Clasament teme lecțiile 1 - 20

Pe categorii

Divizori / Primalitate / Ciur
Sortari
Matrici
Cautare binara
Stivă
Recursivitate
Parcurgeri matrice
Generale

Concursuri

Probleme OȘI
Probleme OJI

Lecție

De acasă

Având în vedere că ne aflăm în situația de a nu putea ține cercul fizic, vă invit totuși pe fiecare dintre voi să treceți prin lecțiile pe care vi le pregătesc și să participați la concursuri și să lucrați temele pe care vi le propun.

Coadă

Definiție

Coada este o structură de date de tip FIFO (first in, first out). Asta înseamnă că elementele sunt adăugate în ordine (ca într-un vector obișnuit) și trebuiesc scoase în ordinea în care au fost adăugate. Un exemplu bun de coadă din viața reală este chiar o coadă de la un magazin: primul venit (primul element adăugat în coadă) este primul servit (primul element care iese din coadă). Prin contrast, stiva era o structură de date de tip LIFO (last in, first out).

Implementare #1

Sunt necesare următoarele operații:

  • push/enqueue(value) - inserează o valoare în coadă
  • pop/dequeue - șterge prima valoare din coadă
  • front - returnează prima valoare din coadă
  • size - returnează numărul de elemente din coadă

Exemplu implementare:

#define MAXN 1000

int queue[MAXN];     // stocarea valorilor propriu-zise
int queue_left = 0;  // indice la prima pozitie din coada
int queue_right = 0; // indice la dreapta ultimului element din coada

// adauga valoarea 'val' la coada, daca aceasta nu este plina
// returneaza 1 in caz de succes, 0 in caz de coada plina
int push( int val ) {
  if ( queue_right >= MAXN )    // coada este plina?
    return 0;                   // returnam eroare

  queue[queue_right++] = val;   // adaugam valoarea in coada
  return 1;                     // returnam succes
}

// returnează valoarea care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top() {
  return queue_left < queue_right ? queue[queue_left] : -1;
}

// elimina elementul care este la rand in coada
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
  if ( queue_left >= queue_right ) // testam cazul de eroare
    return 0;
  
  ++queue_left; // daca avem elemente in coada, il eliminam pe primul, mutand cursorul mai in dreapta
  return 1;
}

// returneaza numarul de elemente din coada
int size() {
  return queue_right - queue_left;
}

Problemă implementare #1

Coada implementată are o dimensiune maximă egală cu 1000 de adăugiri. Ce se întâmplă dacă vrem să adăugăm 1000 elemente în coadă, să scoatem 500 dintre acestea, și să mai adăugăm încă 500 după? Ar fi ideal să putem face asta, dar implementarea de mai sus nu ne permite.

Implementare #2: folosind vectori circulari

Vom folosi o metodă de implementare care să ne permită să avem un total de maxim 1000 elemente în coadă, nu doar 1000 adăugiri. Vom face acest lucru refolosind golurile care se creează prin eliminarea elementelor din coadă. Vom ține ca și înainte, poziția primului element din coadă și al ultimului. Când depășim limita vectorului adăugând elemente, vom considera că vectorul este circular și vom încerca să adăugăm elementul în "dreapta" limitei. Iar dreapta limitei este chiar poziția 0.

Exemplu implementare:

#define MAXN 1000

int queue[MAXN];     // stocarea valorilor propriu-zise
int queue_left = 0;  // indice la prima pozitie din coada
int queue_size = 0;  // numarul de elemente din coada

// adauga valoarea 'val' la coada, daca aceasta nu este plina
// returneaza 1 in caz de succes, 0 in caz de coada plina
int push( int val ) {
  if (queue_size == MAX_N)      // coada este plina?
    return 0;                   // returnam eroare
  
  queue[(queue_left + queue_size) % MAX_N] = val; // adaugam valoarea in coada
  ++size;                                         // incrementam numarul de elemente
  return 1;                                       // returnam succes
}

// returnează valoarea care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top() {
  return queue_size > 0 ? queue[queue_left] : -1;
}

// elimina elementul care este la rand in coada
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
  if (queue_size == 0) // testam cazul de eroare
    return 0;
  
  queue_left = (queue_left + 1) % MAX_N; // daca avem elemente in coada, il eliminam pe primul, mutand cursorul mai in dreapta
  --queue_size;
  return 1;
}

Optimizare

Am spus într-una din lecțiile anterioare că operațiile modulo sunt lente. Pentru a scăpa de ele în cazul de față, putem declara dimensiunea cozii ca fiind putere a lui 2 și ne vom folosi de operații pe biți, optimizând astfel timpul real de execuție al programului.

Algoritmul lui Lee

Algoritmul lui Lee este similar cu algoritmul Flood Fill, în sensul că face parte din aceeași "familie" a parcurgerilor în matrice. Diferența principală constă în ordinea parcurgerii. Flood Fill parcurge elementele "în adâncime", pornind de la o poziție și extinzându-se într-o direcție cât timp se poate. Când nu se mai poate, schimbă direcția și continuă. Algoritmul lui Lee în schimb, pornește de la o poziție și se extinde în același timp în toate direcțiile posibile, pas cu pas.

Aplicații ale algoritmului

  • Găsirea drumului minim de la un punct la celălalt
  • Calcularea distanței minime dintre un punct și toate celelalte

Este de menționat că algoritmul lui Lee poate fi folosit și pentru Fill. Va folosi mai puțină memorie dar va fi mai lent în execuție (din experiență proprie, mult mai lent). Personal, prefer să folosesc Fill când este suficient, pentru că este util, simplu de scris (nu are nevoie de structuri auxiliare, ne putem folosi de stiva recursivității), rapid și își face foarte bine treaba.

Exemplificare grafică

Sursă: IQAcademy

Exemplu de BFS fill cu 4 direcții

A se observa diferența de extindere cu cea din algoritmul Flood Fill

Implementare

Din punct de vedere al implementării, diferența dintre Lee și Flood Fill este structura folosită. La implementarea algoritmului lui Lee, vom folosi o coadă, spre deosebire de stiva folosită în Fill.

Enunț Se dă un labirint codificat ca o matrice cu zero și unu, zero semnificând loc liber și unu fiind element obstacol (zid). Se dau de asemenea un punct de start și unul de final. În matrice ne putem deplasa pe linie sau pe coloană, cu condiția să nu avem un obstacol. Să se calculeze, lungimea drumului minim între cele două puncte, dacă există un astfel de drum.

Vom implementa mai întâi coada pe care o vom folosi în algoritmul lui Lee. O posibilă implementare poate arăta așa:

#define MAXN 1000

int queue_line[MAXN], queue_col[MAX_N];     // stocarea pozitiilor in coada: linie, coloana
int queue_left = 0;                         // indice la prima pozitie din coada
int queue_size = 0;                         // numarul de elemente din coada

// adauga pozitia in coada, daca mai este loc
int push(int line, int col) {
  if (queue_size == MAX_N)      // coada este plina?
    return 0;                   // returnam eroare
  
  int pos = (queue_left + queue_size) % MAX_N;
  queue_line[pos] = line; // adaugam linia in coada
  queue_col[pos] = col;   // adaugam coloana in coada
  ++size;                 // incrementam numarul de elemente
  return 1;               // returnam succes
}

// returnează linia pozitiei care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top_line() {
  return queue_size > 0 ? queue_line[queue_left] : -1;
}

// returnează coloana pozitiei care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top_col() {
  return queue_size > 0 ? queue_col[queue_left] : -1;
}

// elimina pozitia care este la rand in coada
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
  if (queue_size == 0) // testam cazul de eroare
    return 0;
  
  queue_left = (queue_left + 1) % MAX_N; // daca avem elemente in coada, il eliminam pe primul, mutand cursorul mai in dreapta
  --queue_size;
  return 1;
}

Având coada implementată, putem trece la scrierea algoritmului. Vom nota în matricea inițială cu 0 spațiile libere și cu -1 obstacolele. Vom marca punctul de start cu valoarea 1 și la fiecare pas vom marca vecinii poziției curente incrementând valoarea acesteia. La final, distanța până la punctul de final va fi egală cu valoarea din matrice, din care vom scădea 1 (pentru că am început marcarea de la valoarea 1).

push(startLine, startCol);     // adaugam punctul de start in coada
mat[startLine][startCol] = 1;  // marcam "distanta" pana la el ca fiind 1

do {
  // luam pozitia din coada si distanta pana la ea
  line = top_line();
  col = top_col();
  dist = mat[line][col];
  
  pop();   // scoatem pozitia din coada
  
  for (i = 0; i < 4; ++i) {           // parcurgem toti vecinii
    newLine = line + dLine[i];
    newCol = col + dCol[i];

    if (mat[newLine][newCol] == 0) {    // daca nu l-am procesat
      push(newLine, newCol);            // il adaugam in coada
      mat[newLine][newCol] = dist + 1;  // actualizam distanta pana la el
    }
  }
} while (queue_size > 0 && (line != stopLine || col != stopCol)); // ne oprim cand nu mai avem elemente in coada sau cand am ajuns la destinatie

printf("Distanta este %d\n", mat[stopLine][stopCol] - 1);

Detalii implementare

  • Algoritmul se poate extinde ușor de la 4 vecini la 8 vecini
  • Vom folosi aceleași tehnici ca și la Flood Fill:
    • Bordarea matricelor pentru a scăpa de testul de ieșire din matrice
    • Vectorii de direcție pentru a genera ușor vecinii
  • Observați că am oprit bucla în momentul în care punctul pe care îl căutam a fost deja procesat. În cazul de față, bucla poate fi oprită chiar mai devreme (în momentul în care punctul de final este adăugat în coadă). Gândiți-vă cum și de ce!
  • Putem modifica algoritmul pentru a calcula distanța minimă către mai multe puncte de final, marcând în matrice care sunt aceste puncte de final. De exemplu, le putem marca în cazul de față cu -2.
  • Putem modifica algoritmul să permită plecarea din mai multe puncte simultan. Singura modificare necesară este adăugarea tuturor punctelor inițiale la început în coadă.

Complexitate

Complexitate timp: O(M * N), parcurgând cel mult o dată fiecare element

Complexitate spatiu: O(M * N), pentru matricea de distanțe

Atenție Este posibil să avem nevoie să reținem mai multe informații pentru fiecare poziție (distanța calculată până acum, dacă a mai fost sau nu vizitată poziția, dacă este punct de final, etc.). Sunt cazuri în care putem reține toate informațiile acestea într-o singură matrice, jonglând cu biții numerelor acesteia (primul bit ne spune dacă poziția a fost vizitată, al doilea ne spune dacă este punct de final, ... restul biților țin valoarea distanței). Recomand astfel de practici pentru micșorarea memoriei folosite!

Temă

alee - varena
muzeu - infoarena
traseu3 - infoarena
insule - varena
cifre4 - infoarena