Unele probleme tipice abordate prin tehnica backtracking

Prezentam aici unele probleme tipice, ale caror solutii se obtin prin backtracking.
 

Generarea tuturor numerelor de n cifre intr-o baza data

Consideram ca se da tabloul tuturor caracterelor folosite ca cifre ale unui sistem de numeratie pozitional si se cere sa se genereze toate numerele de n cifre ale sistemului respectiv. De exemplu, daca cifrele sunt 0 si 1, numerele de 4 cifre vor fi 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. Daca se genereaza toate numerele de n cifre in baza m, se obtin mn solutii.

Fie tabCifre tabloul cifrelor sistemului de numeratie utilizat. Baza sistemului este egala cu lungimea acestui tablou. Numarul generat se formeaza in stiva folosita pentru backtracking. Pe orice pozitie a numarului generat se poate gasi oricare din elementele tabloului tabCifre. In consecinta, orice element al acestui tablou este succesor valid al elementului precedent al stivei (deci orice cifra din tabCifre poate sa succeada cifrei precedente a numarului). Solutia se obtine cand stiva contine toate cele n cifre ale numarului generat.
 
In fisierul Numarare.java este definita clasa Numarare, care extinde clasa Backtracking si serveste pentru generarea de numere intr-o baza data. Remarcam ca cifrele pot fi si diferite de cele ale sistemului zecimal. Testarea se face in aplicatia din fisierul TestNumarare.java, care primeste ca argumente in linia de comanda lungimea numerelor generate (numarul de cifre) si cifrele sistemului de numeratie folosit (sub forma de caractere separate prin spatii).
Remarcam ca, pentru a se putea modifica si prima cifra a numarului generat, la initializarea stivei se introduce in ea un "element de garda", care nu contine nici o cifra, dar poate avea orice cifra drept succesor. Cifrele numarului generat se gasesc in stiva incepand cu pozitia de indice 1. Cand s-a format un numar de n cifre, stiva are inaltimea n+1.

Generarea tuturor permutarilor a n obiecte

Consideram ca se da un tablou de n obiecte si se cer toate permutarile acestora. Exista, deci, n! solutii.

Problema permutarilor se rezolva prin bactracking in mod asemanator cu cea a generarii de numere intr-o baza data discutata mai sus, cu deosebirea ca, la validarea succesorilor, se pune conditia suplimentara ca succesorul respectiv sa nu existe deja in stiva. Aceasta conditie este necesara, deoarece intr-o permutare nu poate sa apara de mai multe ori acelasi obiect. Se considera ca stiva contine o solutie (o permutare), atunci cand ea contine toate cele n obiecte ale permutarii.
 
In fisierul Permutari.java este definita clasa Permutari, care extinde clasa Backtracking si serveste pentru generarea tuturor permutarilor obiectelor din tabloul tabObj. Deosebirea fata de programul de generare a tuturor numerelor de lungime data este ca, in metoda esteValid, se pune conditia ca la adaugarea unui nou succesor, acesta sa nu existe deja in stiva.

Testarea se face in programul din fisierul TestPermutari.java, care primeste ca argumente in linia de comanda obiectele care vor fi permutate (sub forma de siruri de caractere). 

Generarea tuturor aranjamentelor a m obiecte luate cate n

Consideram ca se da un tablou tabObj care contine m obiecte si se cere sa se genereze aranjamentele acestor obiecte luata cate n (unde n <= m). Problema se rezolva prin backtracking la fel ca cea a permutarilor, dar se considera ca solutia este obtinuta atunci cand stiva contine cele n obiecte ale unui aranjament.
 
In fisierul Aranjamente.java este definita clasa Aranjamente, care extinde clasa Backtracking pentru generarea aranjamentelor de m obiecte luate cate n, cu n<=m. Ca si in cazul permutarilor, se da un tablou de obiecte. In plus, se da numarul de obiecte dintr-un aranjament. Deosebirea fata de clasa permutari este ca solutia se obtine atunci cand in stiva exista toate cele n obiecte ale unui aranjament.

In fisierul TestAranjamente.java este data o aplicatie de testare a clasei Aranjamente. La punerea in executie se dau ca argumente in linia de comanda numarul de obiecte dintr-un aranjament n si cele m obiecte din care se extrag aranjamemtele (fiecare obiect este un String).

Generarea tuturor combinarilor a m obiecte luate cate n

Combinarile se genereaza similar cu aranjamentele, cu deosebirea ca nu se permite sa avem doua combinari care contin aceleasi obiecte. Aceasta se poate face punand conditia suplimentara ca obiectele dintr-o combinare sa fie situate intr-o ordine prestabilita, de exemplu in ordine crescatoare. In acest caz, se considera ca este valid numai acel succesor, care este mai mare decat elementul din varful stivei.
 
In fisierul Combinari.java este definita clasa Combinari, care extinde clasa Backtracking pentru generarea tuturor combinarilor de m obiecte luate cate n, cu n<=m. Ca si in cazul aranjamentelor, se dau un tablou de obiecte si numarul de obiecte dintr-un aranjament. Deosebirea fata de clasa Aranjamemte este ca la validare se verifica daca succesorul este mai mare decat elementele existente deja in stiva.

In fisierul TestCombinari.java este data o aplicatie de testare a clasei Combinari. La punerea in executie se dau ca argumente in linia de comanda numarul de obiecte dintr-o combinare (n) si cele m obiecte din care se extrag combinarile (fiecare obiect este un String).

Generarea produsului cartezian intre n multimi

Fie n multimi M0, M1, M2, ..., Mn-1. Produsul cartezian al acestor multimi, M0 x M1 x M2 x ... x Mn-1 este
o multime, ale carei elemente sunt n-upluri care contin cate un element din fiecare din multimile date. De exemplu, daca se dau multimile {a0, a1} si {b0, b1}, produsul lor cartezian este multimea {(a0,b0), (a0,b1), (a1,b0), (a1,b1)}. Multimile pot avea cardinale diferite.

Generarea elementelor produsului cartezian se poate face prin backtracking, in mod asemenator cu generarea numerelor dintr-un sistem de numeratie (vezi clasa Numarare). Deosebirea este ca, de data aceasta, pentru fiecarei pozitii din stiva ii corespunde alta lista (sau alt tablou) de succesori posibili. Aceasta este lista elementelor de pe pozitia corespunzatoare a produsului cartezian.
 
In fisierul ProdusCartezian.java este definita clasa ProdusCartezian, care extinde clasa Bactracking. Elementele multimilor al carui produs cartezian trebuie generat se dau sub forma tabloului bidimensional multimi, in care fiecare linie contine elementele unei multimi. Liniile pot avea lungimi diferite.
La stabilirea succesorului elementului din varful stivei se stabileste mai intai indicele acestuia, dupa care se ia succesorul de pe linia urmatoare a matricei multimi, care sa fie situat dupa ultimul succesor j care a fost deja parcurs.

In fisierul TestProdCart.java se da o eplicatie de testare a clasei ProdusCartezian.

Problema celor n dame

Una din problemele clasice care pot fi rezolvate prin backtracking este "problema celor n dame". Se considera o tabla de sah cu n carouri pe fiecare latura. Se cere sa se aseze pe aceasta tabla n dame, astfel incat ele sa nu se atace reciproc. Conform regulilor jocului de sah, aceasta inseamna ca nu trebuie sa se aseze doua dame pe aceeasi coloana, pe aceeasi linie, sau pe aceeasi diagonala.

Pentru rezolvarea acestei probleme prin bactracking, vom considera ca elementul de indice i al stivei contine indicele j al damei puse pe linia i a tablei de sah. Avand in vedere ca nu pot exista doua dame pe aceeasi linie, indicarea coloanei in care se afla unica dama de pe fiecare linie a tablei este suficienta pentru a caracteriza intreaga situatie.

La selectarea succesorului, se are in vedere ca, in principiu, dama poate fi pusa in oricare coloana a oricarei linii. In consecinta, succesorul elementului din linia i (de pe pozitia i a stivei) poate fi orice j situat in intervalul [1, n]. La validarea succesorului se are in vedere ca:
  a/ dama succesoare nu trebuie sa se gaseasca in aceeasi coloana cu nici una din damele de pe linia precedenta; in consecinta, valoarea j a coloanei in care se pune dama succesoare nu trebuie sa se gaseasca pe nici una din pozitiile anterioare ale stivei;
  b/ dama succesoare nu trebuie sa se gaseasca pe aceeasi diagonala cu niciuna din damele din liniile precedente, deci pentru nici o pozitie j din stiva  nu trebuie fie satisfacuta egalitatea |j[i]-j[k]|==|i-k|, in care j[i] este valoarea indicelui j de coloana memorata pe pozitia i a stivei, iar j[k] este valoarea indicelui j de coloana pentru linia de indice k, in care se va plasa dama succesoare.
Solutia problemei trebuie sa contina cate o dama pe fiecare linie a tablei de sah, respectand aceste restrictii.
 
In fisierul NDame.java este definita clasa NDame, care extinde clasa Backtracking si aplica la stabilirea succesorului valid restrictiile mentionate mai sus. 
In fisierul TestNDame.java este data o aplicatie de testare. La punerea in executie a aplicatiei, in linia de comanda se da numarul de carouri de pe o latura a tablei de sah.

Backtracking recursiv

Asa cum s-a aratat si in cazul parcurgerii arborilor, intrucat la realizarea backtrackingului se foloseste stiva, acesta poate fi realizat si folosind functii recursive.

Rezolvarea problemelor prin tehnica "fortei brute"

In multe situatii practice, in care trebuie sa se aleaga dintre mai multe variante posibile solutia care satisface anumite conditii (de exemplu solutia de cost minim, sau de profit maxim si care indeplineste eventual si anumite restrictii) se poate face aplicand principiul "fortei brute" in modul urmator: se genereaza toate variantele posibile, dintre care se selecteaza numai acele variante care indeplinesc restrictiile impuse si, in final, dintre variantele astfel selectate se alege cea optima. Avantajul acestei tehnici este simplitatea, cel putin la nivel conceptual. Marele desavantaj este ca cu cresterea dimensiunii n (a numarului de elemente din multimile de date asupra carora se aplica algoritmul) numarul de variante posibile creste foerte rapid. In consecinta, in general tehnica "fortei brute" nu este convenabila pentru cazul cand numarul de elemente este mare. Intotdeauna cand exista pentru o anumita problema un algoritm mai eficient, trebuie folosit acesta. Totusi, cand astfel de algoritmi nu exista, la nevoie se poate recurge si la "forta bruta"

In sectiunea precedenta s-au prezentat algoritmi prin care se pot genera toate solutiile posibile pentru diferite probleme tipice. Daca dorim sa aplicam "forta bruta" pentru rezolvarea unei probleme particulare, stabilim mai intai in care din cazurile mentionate se incadreaza variantele de solutii, generam solutiile respective si apoi o selectam pe cea corespunzatoare conditiilor.
 
Iata un exemplu: sa consideram ca la o conferinta, in jurul unei mese rotunde, trebuie asezate n persoane, astfel incat sa nu fie asezate alaturi doua persoane rivale, fiind data pentru fiecare persoana lista rivalilor acesteia. Remarcam imediat ca solutia se gaseste printre permutarile celor n persoane. In consecinta generam toate permutarile de n obiecte si le selectam pe acelea in care, pentru fiecare persoana in parte, cei doi vecini nu se gasesc in lista de rivali.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati