[C++, programare dinamică] Problemă cu algoritmul lui Lee (b)

Introducere în problema labirintului aici.

Enunț

b) Dați un exemplu pe care soluția recursivă efectuează cu mult mai mulți pași decât e necesar.

Explicație

Soluția recursivă efectuează mai mulți pași decât soluția nerecursivă cu cât se fac mai multe apeluri recursive pentru poziții deja calculate, ceea ce echivalează cu cât există mai multe poziții în care se poate ajunge prin multiple căi.

In exemplul dat în pagina de la link-ul de la începutul acestui articol, poziția (2, 3) are la primul apel recursiv asupra ei valoarea 7, apoi la al doilea apel primește valoarea 5. Ordinea apelurilor recursive este determinată de ordinea valorilor din vectorii de direcție, fiind o parcurgere în adâncime.

Aici este codul care a generat fișierele de ieșire de mai jos (am modificat ordinea elementelor din vectorii de direcție pentru ca să se parcurgă în ordinea aceasta: dreapta, jos, stânga, sus). Codul afișează în fereastra linie de comandă, dar se poate selecta tot conținutul ei cu: clic stânga pe un caracter sau spațiu din fereastră, Ctrl-A și apoi clic dreapta pe oricare caracter sau spațiu din fereastră. Apoi se poate da Ctrl-V sau Paste în oricare alt program care poate primi text, inclusiv într-un editor text.

  • Aici este fișierul de ieșire cu fiecare pas dezvoltat al problemei de la link-ul de la începutul acestui articol (prima variantă a algoritmului) cu datele de intrare din exemplul din carte.
  • In același format, dar pentru o matrice 4×4 cu camere doar deschise, aici este fișierul de ieșire.

Puteți deschide aceste fișiere în Visual Studio Code, editor care suportă automat colapsarea secțiunilor intentate diferit. Notă: inițial matricea D este plină de valori pseudo-infinite, adică valori foarte mari care cu greu pot fi depășite.

In aceste două fișiere se poate folosi căutarea textului „Urmeaza parcurgerea vecinilor lui” (fără diacritice) și într-un editor care suportă acest lucru, de exemplu Visual Studio Code, se afișează câte rezultate au fost găsite. In fișierul rezultat din exemplul din carte, acest șir de caractere apare de 10 ori. In fișierul rezultat din exemplul nou, sunt 52 de apariții ale acestui șir. Fiecare astfel de apariție reprezintă un apel recursiv.

Exemplul din carte Exemplul 4×4 doar cu camere deschise
Algoritm recursiv 10 apeluri recursive 52 de apeluri recursive
Algoritm optim nerecursiv 9 pași 16 pași

Cum 16 este mult mai mic decât 52 având în vedere aceeași dimensiune a matricei labirint, deci am găsit un exemplu bun pentru cerința de la începutul acestui articol.

In figură, apare direcția de parcurgere în adâncime a matricei 4×4 cu camere doar deschise, și cu vectorii de poziție din fișierul de la ultimul link de mai sus:

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
După parcurgerea din figură urmează revenirea din apelurile recursive care poate începe alte apeluri recursive.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: