BACKTRACKING GENERALIZAT IN PLAN PROBLEMA LABIRINTULUI REFERAT SCOALA

Metoda Backtracking în plan are câteva modificări: - stiva conţine mai multe coloane (este dublă, triplă, ...); - trebuiesc codificate oarecum direcţiile prin numere, litere, elemente, etc. Problema labirintului se poate rezolva după un algoritm de backtracking generalizat în plan. Ea va fi prezentată în continuare. Problema labirintului. Enunt: Se dă un labirint sub formă de matrice de m linii şi n coloane. Fiecare element al matricii reprezintă o cameră. Într-una din camerele labirintului se găseşte un om. Se cere să se afle toate soluţiile ca acel om să iasă din labirint, fără să treacă de două ori prin aceeaşi cameră. Generalizare. Această variantă a problemei este varianta în care fiecare cameră are pereţii proprii în părţile laterale. Există o altă variantă în care fiecare element al matricii este fie un culoar, fie un perete, putându-se trece doar dintr-un culoar în altul. Aici, se poate trece dintr-o cameră în alta, doar dacă între cele două camere nu există perete (camerele sunt imediat apropiate). Prin labirint, putem trece dintr-o cameră în alta doar mergând în sus, în jos, la stânga sau la dreapta, nu şi în diagonală. Codificare. Principiul backtracking generalizat spune că trebuies codificate direcţiile. În aceste caz vor fi codificate şi combinaţiile de pereţi ai fiecărei camere. Asftel, un element al camerei va fi un element al unei matrici cu n linii şi n coloane, având valori de la 0 la 15. În sistemul binar, numerele 0..15 sunt reprezentate ca 0..1111, fiind memorate pe 4 biţi consecutivi. Vom lua în cosiderare toţi cei 4 biţi, astfel numerele vor fi 0000..1111. Fiecare din cei 4 biţi reprezintă o direcţie, iar valoarea lui ne spune dacă în acea direcţie a camerei există sau nu un perete. Vom reprezenta numărul astfel: