Am prezentat problema labirintului în cadrul secțiunii despre backtracking. Similar, se dă o matrice pătratică de dimensiune N, cu valori de 0 sau de 1, codificând un labirint. Valoarea 0 reprezintă o cameră deschisă, iar valoarea unu o cameră închisă. Se cere de data aceasta cel mai scurt drum de la poziția (1, 1) la poziția (N, N), mergând doar prin camere deschise și doar la stânga, dreapta, în jos sau în sus. Nu se poate trece de două ori prin același loc. Lungimea unui drum este dată de numărul de pași necesari parcurgerii drumului.
Vom citi datele de intrare din fișierul lee.in, iar în fișierul de ieșire lee.out vom afișa pe prima linie lungimea drumului minim, iar pe următoarele linii coordonatele care descriu un drum de lungime minimă.
Exemplu:
lee.in
|
lee.out
|
|---|---|
| 4 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
6 1 1 2 1 3 1 3 2 3 3 3 4 4 4 |
Rezolvarea prin metoda backtracking de la problema în care se cereau toate ieșirile din labirint se poate aplica și la această variantă a problemei. Trebuie doar să generăm toate drumurile, iar apoi să-l alegem pe cel de lungime minimă. Această rezolvare nu este însă eficientă, deoarece are la bază o căutare exhaustivă.
Problema se poate rezolva eficient în timp O(N2) folosind algoritmul lui Lee (care este de fapt o parcurgere în lățime pentru cei familiarizați cu noțiuni de teoria grafurilor). Algoritmul poate fi privit ca un algoritm de programare dinamică. Pentru a evidenția acest lucru, să presupunem că vrem să aflăm lungimea drumului minim de la poziția (1, 1) a matricei până la poziția (p, q). Deoarece dintr-o poziție (x, y) ne putem deplasa în pozițiile învecinate cu (x, y) la nord, sud, est sau vest, putem scrie următoarea formulă:
D[p][q] = 1 + min(D[p - 1][q], D[p + 1][q], D[p][q - 1], D[p][q + 1]), unde D[x][y] reprezintă distanța minimă de la (1, 1) la (x, y). Pentru indici invalizi sau care reprezintă un zid, distanța minimă va fi infinit.
Există mai multe metode de implementare a acestui algoritm. Fie A matricea dată. Prima metodă reprezintă implementarea relației de recurență exact așa cum este dată, cu ajutorul unei funcții recursive. Vom folosi pentru această metodă o matrice D cu semnificația anterioară și o funcție recursivă Lee(A, N, x, y, D) care va construi această matrice. Vom iniția D[1][1] cu 0, iar în restul matricei cu infinit, semnificând faptul că acele valori nu au fost calculate încă.
Funcția Lee poate fi implementată astfel:
- Pentru fiecare vecin (newx, newy) al lui (x, y) execută:
- Dacă (newx, newy) este o poziție validă, nu reprezintă un zid și D[newx][newy] > D[x][y] + 1 execută
- D[newx][newy] = D[x][y] + 1
- Apel recursiv Lee(A, N, newx, newy, D)
După apelul inițial lee(A, N, 1, 1, D), matricea D va fi calculată conform definiției sale, deci D[N][N] va conține distanța minimă.
Deși această metodă este cel mai ușor de implementat, nu este cea mai eficientă, deoarece funcția lee poate fi apelată de mai multe ori pentru aceeași poziție. Pentru a evidenția acest lucru vom prezenta modul de execuție al funcției de mai sus pe exemplul dat. Vom considera că vectorii de direcție (acest concept a fost definit la secțiunea dedicată metodei backtracking) sunt:
dx[] = {1, 0, -1, 0};
dy[] = {0, 1, 0, -1};
Inițial avem:
| A | D |
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ |
Primul vecin al poziției (1, 1), conform vectorilor de direcție folosiți este (2, 1). Această poziție este validă, nu conține un zid și ∞ > 0 + 1. Se observă că și al doilea pas va conduce la poziția validă (3, 1). Așadar, după primii doi pași avem:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ |
Primul vecin al poziției (3, 1), este (4, 1), poziția invalidă deoarece conține un zid. Al doilea vecin este poziția (3, 2), poziție validă. Funcția se autoapelează pentru această poziție și obținem:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 3 ∞ ∞ ∞ ∞ ∞ ∞ |
Din poziția (3, 2) prima dată se încearcă vecinul (4, 2), care este însă un zid. Se va merge în continuare la stânga încă doi pași, până obținem:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 3 4 5 ∞ ∞ ∞ ∞ |
Din poziția (3, 4) funcția se va apela prima dată pentru poziția (4, 4), obținându-se următoarea configurație:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 3 4 5 ∞ ∞ ∞ 6 |
Deoarece niciun vecin al poziției (4, 4) nu este valid pentru a se efectua apeluri recursive, se revine din recursivitate la poziția (3, 4), din care se efectuează apoi un autoapel pentru vecinul de sus, (2, 4):
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ 6 2 3 4 5 ∞ ∞ ∞ 6 |
Singurul apel recursiv valid din poziția (2, 4) este pentru poziția (2, 3), obținându-se:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ 7 6 2 3 4 5 ∞ ∞ ∞ 6 |
Se revine din recursivitate până la poziția (3, 3), de unde, când se verifică vecinul (2, 3) se vor îndeplini toate condițiile necesare efectuării unui apel recursiv deoarece 7 > 4 + 1 = 5 și poziția (2, 3) este validă și conține o cameră deschisă. Forma finală a matricei D va fi:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ 5 6 2 3 4 5 ∞ ∞ ∞ 6 |
Așadar, am actualizat de două ori valoarea D[2][3]. Vom încerca să găsim un algoritm care actualizează fiecare valoare o singură dată, dar vom prezenta mai întâi implementarea acestei metode:
Precizăm că am omis intenționat funcția care determină coordonatele ce descriu un drum de lungime minimă. Această funcție va fi prezentată la sfârșit.
Am afirmat la începutul acestei secțiuni că algoritmul lui Lee este de fapt o parcurgere in lățime. Acei cititori care cunosc parcurgerea în lățime și cea în adâncime probabil au observat că prima metodă este de fapt o parcurgere în adâncime, deoarece se merge în aceeași direcție până când se întâlnește un obstacol și abia apoi se revine la un pas anterior sau se schimbă direcția. Parcurgerile grafurilor vor fi prezentate într-un alt capitol, așa că nu vom detalia aici parcurgerea în lățime. Ideea de bază este să verificăm la fiecare pas toți vecinii poziției curente, iar apoi toți vecinii acestora și așa mai departe, până când se parcurge întreaga matrice. Datorită faptului că vom parcurge matricea uniform, fiecare element va fi analizat o singură dată.
Ideea de bază rămâne aceeași, diferind doar implementarea. Pentru a putea implementa parcurgerea descrisă anterior vom folosi o structură de date numită coadă F.I.F.O. Această structură de date a fost descrisă în capitolul Introducere în S.T.L.
Vom prezenta în continuare noul algoritm în pseudocod. Notațiile rămân aceleași, iar Q reprezintă coada F.I.F.O. folosită, p reprezintă poziția primului element din coadă, iar u poziția ultimului element din coada:
- p = u = 1
- Q[p] = (1, 1)
- Cât timp p ≤ u execută
- (x, y) = Q[p++]
- Pentru fiecare vecin (newx, newy) al lui (x, y) execută
- Dacă (newx, newy) este o poziție validă, nu reprezintă un zid și D[newx][newy] > D[x][y] + 1 execută
- D[newx][newy] = D[x][y] + 1
- Q[++u] = (newx, newy)
Datorită modului în care parcurgem matricea, toate drumurile posibile vor fi parcurse în același timp, deci nu va exista posibilitatea completării unei părți a matricei D cu valori care vor trebui ulterior corectate, așa cum a fost cazul în implementarea inițială. Pentru a evidenția acest lucru vom prezenta modul de execuție al algoritmului pe exemplul dat.
Inițial avem:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ |
Se extrage primul element din coada Q și anume (1, 1). Se actualizează toți vecinii acestuia care se supun condițiilor de mai sus. Singurul vecin valid este (2, 1), care se actualizează, iar poziția (2, 1) se introduce în coadă. Avem configurația:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ |
La următorul pas e extrage Q[p], adică (2, 1). Singurul vecin valid este (3, 1), care se actualizează și se introduce în coadă:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ |
Similar, singurul vecin valid al poziției Q[p] = (3, 1) este (3, 2), care se va introduce în coadă si se va actualiza. La următorul pas se va extrage (3, 2) din coadă și se va introduce singurul vecin valid al acestei poziții (3, 3):
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ ∞ ∞ 2 3 4 ∞ ∞ ∞ ∞ ∞ |
Se extrage (3, 3) din Q. Poziția (3, 3) are doi vecini valizi: (3, 4) și (2, 3), care se actualizează și se introduc amândoi în coadă:
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ 5 ∞ 2 3 4 5 ∞ ∞ ∞ ∞ |
Se extrage elementul (3, 4), care va actualiza pozițiile (4, 4) și (2, 4) și le va introduce în coadă. Se observă că după acest pas matricea este deja completată corect.
A
|
D
|
|---|---|
| 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 |
0 ∞ ∞ ∞ 1 ∞ 5 6 2 3 4 5 ∞ ∞ ∞ 6 |
Dacă ne interesează doar poziția (N, N), putem returna D[N][N] imediat ce această valoare a fost calculată. Dacă ne interesează întreaga matrice D, algoritmul trebuie continuat până când p devine mai mare decât u.
Datorită faptului că am introdus fiecare poziție a matricei (care nu reprezintă un zid) în coadă exact o singură dată și pentru că am evitat recursivitatea, timpul de execuție al acestei implementări este cu mult mai bun decât cel al implementării recursive.
Pentru a determina coordonatele care alcătuiesc traseul vom folosi o funcție recursivă drum(x, y). Observăm că dacă D[x][y] == k (k > 0, k != ∞) atunci poziția imediat anterioară lui (x, y) în cadrul drumului minim este acel vecin (p, q) al lui (x, y) pentru care D[p][q] == k - 1. Dacă D[x][y] este 0, atunci (x, y) == (1, 1); această condiție este chiar condiția de ieșire din recursivitate. Așadar funcția drum(x, y) poate fi scrisă astfel:
- Dacă D[x][y] == 0 afișează (1, 1) și oprește execuția
- Caută un singur vecin (p, q) al lui (x, y) pentru care D[p][q] == D[x][y] - 1
- Apel recursiv drum(p, q)
- Afișează (x, y)
In C++ această funcție poate fi implementată în felul următor. Funcția funcționează atât pentru implementarea deja prezentată, cât și pentru implementările ce vor urma.
Funcția determină un singur traseu, iar apelul inițial este drum(D, N, N, N, out) pentru cerința problemei prezentate.
Vom prezenta în continuare două variante de funcții Lee care implementează ultimul algoritm descris. Avem mai multe posibilități de a implementa o coadă. Prima și cea mai evidentă posibilitate este să folosim un vector cu N2 perechi de numere întregi (deoarece fiecare poziție poate fi introdusă cel mult o singură dată în coadă) și să reținem poziția primului element al cozii în variabila p și poziția ultimului element în variabila u, exact așa cum se poate vedea în evidențierea exemplului dat. Pentru această implementare avem nevoie de o structură care grupează două variabile întregi:
Noua funcție lee poate fi implementată în felul următor:
Iar apelul inițial devine Lee(A, N, D).
Putem scrie un cod mai compact și mai natural limbajului C++ folosind utilitățile puse la dispoziție de către biblioteca S.T.L. și anume containerele pair și queue, care pun la dispoziție programatorului ceea ce noi ar trebui să implementăm singuri în codul anterior: posibilitatea de a reține perechi de numere, respectiv o coadă F.I.F.O. Avantajul containerului queue este că acesta nu va folosi niciodată memorie pentru N2 elemente, deoarece este implementat în așa fel încât elementele scoase din coadă să fie șterse și din memorie. In implementarea precedentă memoria folosită pentru coadă este întotdeauna maximă și nici nu ștergem efectiv elementele, ci doar incrementăm o limită inferioară pentru poziția primului element.
Nu vom prezenta pe larg aici aceste două containere întrucât au fost prezentate în cadrul capitolului Introducere în S.T.L. Precizăm doar că pentru folosirea lor trebuie incluse fișierele antet <utility> și <queue>. Noua implementare este:
Recomandăm cititorilor să se familiarizeze cât mai bine cu biblioteca S.T.L., mai ales pentru capitolele ce vor urma, deoarece facilitățile oferite de aceasta sunt de multe ori foarte folositoare și conduc la implementări mai ușoare sau mai eficiente. De aceea, de fiecare dată când acest lucru este posibil și preferabil, următoarele implementări vor fi prezentate exclusiv folosind facilitățile S.T.L.
Exerciții:
a) Considerăm că o persoană pornește din (1, 1) și alta din (N, N). Cele două persoane se mișcă exact în același timp. Scrieți un program care determină coordonatele spre care acestea ar trebui să se îndrepte pentru a se întâlni cât mai rapid.
b) Dați un exemplu pe care soluția recursivă efectuează cu mult mai mulți pași decât e necesar.
c) Modificați funcția de afișare a drumului astfel încât să afișeze toate drumurile minime existente.
Niciun comentariu:
Trimiteți un comentariu