[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 4x4 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 4x4 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 4x4 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.