...rimul element x1 din A1. Se repeta intr-o structura repetitiva pana cand nu mai exista elemente netestate din multimea A1- se presupune ca am ajuns la elementul xk din multimea Ak si se doreste gasirea unui element xk1 din multimea Ak1. Acesta trebuie sa indeplineasca conditiile de existenta a unui astfel de element, impuse de problema, iar daca- indeplineste aceste conditii atunci trebuie sa indeplineasca alte conditii impuse de problema, prin care se determina daca el ar putea face parte din solutie. Daca- da, atunci se testeaza daca sirul de elemente este o solutie a problemei. Daca- da, atunci se tipareste vectorul care contine aceste solutii- nu, atunci se trece pe urmatorul nivel din sir kk1- nu, nu indeplineste conditiile de a face parte din solutie, atunci se trece la urmatorul element netestat din multimea Ak- nu mai poate exista un element pe nivelul k, atunci se trece la nivelul anterior si se incearca aici gasirea unui element- repetitia se termina cand am ajuns pe nivelul 0.Backtraking generalizat in planMetoda Backtracking in plan are cateva modificari- stiva contine mai multe coloane este dubla, tripla, ...- trebuiesc codificate oarecum directiile prin numere, litere, elemente, etc.Problema labirintului se poate rezolva dupa un algoritm de backtracking generalizat in plan. Ea va fi prezentata in continuare.Problema labirintului. Enunt Se da un labirint sub forma de matrice de m linii si n coloane. Fiecare element al matricii reprezinta o camera. Intr-una din camerele labirintului se gaseste un om. Se cere sa se afle toate solutiile ca acel om sa iasa din labirint, fara sa treaca de doua ori prin aceeasi camera.Generalizare. Aceasta varianta a problemei este varianta in care fiecare camera are peretii proprii in partile laterale. Exista o alta varianta in care fiecare element al matricii este fie un culoar, fie un perete, putandu-se trece doar dintr-un culoar in altul. Aici, se poate trece dintr-o camera in alta, doar daca intre cele doua camere nu exista perete camerele sunt imediat apropiate. Prin labirint, putem trece dintr-o camera in alta doar mergand in sus, in jos, la stanga sau la dreapta, nu si in diagonala.Codificare. Principiul backtracking generalizat spune ca trebuies codificate directiile. In aceste caz vor fi codificate si combinatiile de pereti ai fiecarei camere. Asftel, un element al camerei va fi un element al unei matrici cu n linii si n coloane, avand valori de la 0 la 15. In sistemul binar, numerele 0..15 sunt reprezentate ca 0..1111, fiind memorate pe 4 biti consecutivi. Vom lua in cosiderare toti cei 4 biti, astfel numerele vor fi 0000..1111. Fiecare din cei 4 biti reprezinta o directie, iar valoarea lui ne spune daca in acea directie a camerei exista sau nu un perete. Vom reprezenta numarul astfelnr b1 b2 b3 b4 b bitAsftel, b1 indica directia nord sus, b2 indica directia est dreapta, b3 indica directia sud jos iar b4 indica directia vest stanga.Valorile unui bit sunt, fireste, 0 si 1. 0 inseamna ca in directia respectiva nu exista un perete, iar 1 inseamna ca in directia respectiva exista un perete si pe acolo nu se poate trece. De exemplu 0111 - camera aceasta are pereti in dreapta, in jos si in stanga, iar in sus este drum liber spre camera vecina. Acest numar este de fapt 7, asa fiind notat in matricea labirintului.In ceea ce priveste directiile, vom retine doar coordonatele unde se afla omul din labirint, acestea fiind schimbate in functie de drumul pe care-l urmeaza. Vom avea o stiva tripla astfel- coloana 1 va indica directia. Aceasta va fi de la 1 la 4, 1 reprezentand sus, 2 reprezentand dreapta, 3 reprezentand jos, iar 4, stanga.- coloana 2 va retine indicele de linie al camerelor parcurse in labirint- coloane 3 va retine indicele de coloana al camerelor parcurse in labirint- fiecare linie va insemna o camera, cu indicele de linie si de coloanaAstfel, in cazul in care di...
Download