Unele probleme tipice abordate prin tehnica backtracking

Prezentăm aici unele probleme tipice, ale căror soluții se obțin prin backtracking.
 

Generarea tuturor numerelor de n cifre într-o bază dată

Considerăm că se dă tabloul tuturor caracterelor folosite ca cifre ale unui sistem de numerație pozițional și se cere să se genereze toate numerele de n cifre ale sistemului respectiv. De exemplu, dacă cifrele sunt 0 și 1, numerele de 4 cifre vor fi 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. Dacă se generează toate numerele de n cifre în baza m, se obțin mn numere.

Fie tabCifre tabloul cifrelor sistemului de numerație utilizat. Baza sistemului este egală cu lungimea acestui tablou. Numărul generat se formează în stiva folosită pentru backtracking. Pe orice poziție a numărului generat se poate găsi oricare din elementele tabloului tabCifre. În consecința, orice element al acestui tablou este succesor valid al elementului precedent al stivei (deci orice cifră din tabCifre poate sa succeadă cifrei precedente a numărului). Soluția se obține când stiva conține toate cele n cifre ale numărului generat.
 
În fișierul Numarare.java este definită clasa Numarare, care extinde clasa Backtracking și servește pentru generarea de numere într-o bază dată. Remarcăm că cifrele pot fi și diferite de cele ale sistemului zecimal. Testarea se face în aplicația din fișierul TestNumarare.java, care primeste ca argumente în linia de comandă lungimea numerelor generate (numărul de cifre) și cifrele sistemului de numerație folosit (sub forma de caractere separate prin spații).
Remarcăm că, pentru a se putea modifica și prima cifră a numărului generat, la inițializarea stivei se introduce în ea un "element de gardă", care nu conține nici o cifră, dar poate avea orice cifră drept succesor. Cifrele numărului generat se găsesc în stivă începând cu poziția de indice 1. Când s-a format un numar de n cifre, stiva are înălțimea n+1.

Generarea tuturor permutărilor a n obiecte

Considerăm că se dă un tablou de n obiecte și se cer toate permutările acestora. Există, deci, n! soluții.

Problema permutărilor se rezolvă prin bactracking în mod asemănător cu cea a generării de numere într-o bază dată discutată mai sus, cu deosebirea că, la validarea succesorilor, se pune condiția suplimentară ca succesorul respectiv să nu existe deja în stivă. Această condiție este necesară, deoarece într-o permutare nu poate să apară de mai multe ori același obiect. Se consideră că stiva conține o soluție (o permutare), atunci când ea conține toate cele n obiecte ale permutării.
 
În fișierul Permutari.java este definită clasa Permutari, care extinde clasa Backtracking și serveste pentru generarea tuturor permutărilor obiectelor din tabloul tabObj. Deosebirea fața de programul de generare a tuturor numerelor de lungime dată este că, în metoda esteValid, se pune condiția ca, la adăugarea unui nou succesor, acesta să nu existe deja în stivă.

Testarea se face în programul din fișierul TestPermutari.java, care primește ca argumente în linia de comandă obiectele care vor fi permutate (sub forma de șiruri de caractere). 

Generarea tuturor aranjamentelor a m obiecte luate câte n

Considerăm că se dă un tablou tabObj care conține m obiecte și se cere să se genereze aranjamentele acestor obiecte luate câte n (unde n <= m). Problema se rezolvă prin backtracking la fel ca cea a permutărilor, dar se consideră ca soluția este obținută atunci când stiva conține cele n obiecte ale unui aranjament.
 
În fișierul Aranjamente.java este definită clasa Aranjamente, care extinde clasa Backtracking pentru generarea aranjamentelor de m obiecte luate câte n, cu n<=m. Ca și în cazul permutărilor, se dă un tablou de obiecte. În plus, se dă numărul de obiecte dintr-un aranjament. Deosebirea față de clasa permutări este că soluția se obține atunci când în stivă există toate cele n obiecte ale unui aranjament.

În fișierul TestAranjamente.java este dată o aplicație de testare a clasei Aranjamente. La punerea în execuție se dau ca argumente în linia de comandă numărul de obiecte dintr-un aranjament n și cele m obiecte din care se extrag aranjamemtele (fiecare obiect este un String).

Generarea tuturor combinărilor a m obiecte luate câte n

Combinările se generează similar cu aranjamentele, cu deosebirea că nu se permite să avem două combinări care conțin aceleași obiecte, indiferent de ordinea obiectelor respective. Aceasta se poate face punând condiția suplimentară ca obiectele dintr-o combinare să fie situate într-o ordine prestabilită, de exemplu în ordine crescătoare. În acest caz, se consideră că este valid numai acel succesor, care este mai mare decât elementul din vârful stivei.
 
În fișierul Combinari.java este definită clasa Combinari, care extinde clasa Backtracking pentru generarea tuturor combinărilor de m obiecte luate câte n, cu n<=m. Ca și în cazul aranjamentelor, se dau un tablou de obiecte și numărul de obiecte dintr-o combinare. Deosebirea față de clasa Aranjamemte este că la validare se verifică dacă succesorul este mai mare decât elementele existente deja în stivă.

În fișierul TestCombinari.java este dată o aplicație de testare a clasei Combinari. La punerea în execuție se dau ca argumente în linia de comandă numărul de obiecte dintr-o combinare (n) și cele m obiecte din care se extrag combinările (fiecare obiect este un String).

Generarea produsului cartezian între n mulțimi

Fie n mulțimi M0, M1, M2, ..., Mn-1. Produsul cartezian al acestor mulțimi, M0 x M1 x M2 x ... x Mn-1 este
o mulțime, ale cărei elemente sunt n-upluri care conțin câte un element din fiecare din mulțimile date. De exemplu, dacă se dau mulțimile {a0, a1} și {b0, b1}, produsul lor cartezian este multimea {(a0,b0), (a0,b1), (a1,b0), (a1,b1)}. Mulțimile pot avea cardinale diferite.

Generarea elementelor produsului cartezian se poate face prin backtracking, în mod asemănător cu generarea numerelor dintr-un sistem de numerație (vezi clasa Numarare). Deosebirea este că, de data aceasta, fiecărei poziții din stivă îi corespunde altă listă (sau alt tablou) de succesori posibili. Aceasta este lista elementelor mulțimii de pe poziția corespunzătoare a produsului cartezian.
 
În fișierul ProdusCartezian.java este definită clasa ProdusCartezian, care extinde clasa Bactracking. Elementele mulțimilor al cărui produs cartezian trebuie generat se dau sub forma tabloului bidimensional multimi, în care fiecare linie conține elementele unei mulțimi. Liniile pot avea lungimi diferite.
La stabilirea succesorului elementului din vârful stivei se stabilește mai întâi indicele acestuia, după care se ia succesorul de pe linia următoare a matricei multimi, care sa fie situat după ultimul succesor j care a fost deja parcurs.

În fișierul TestProdCart.java se dă o aplicație 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 consideră o tablă de șah cu n carouri pe fiecare latură. Se cere să se așeze pe această tablă n dame, astfel încât ele să nu se atace reciproc. Conform regulilor jocului de șah, aceasta înseamnă că nu trebuie să se așeze două dame pe aceeași coloană, pe aceeași linie, sau pe aceeași diagonală.

Pentru rezolvarea acestei probleme prin bactracking, vom considera că elementul de indice i al stivei conține indicele j al damei puse pe linia i a tablei de șah. Având în vedere că nu pot exista doua dame pe aceeași linie, indicarea coloanei în care se află unica damă de pe fiecare linie a tablei este suficientă pentru a caracteriza întreaga situație.

La selectarea succesorului, se are în vedere că, în principiu, dama poate fi pusă în oricare coloana a oricărei linii. În consecință, 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 în vedere că:
  a/ dama succesoare nu trebuie să se gasească în aceeași coloană cu nici una din damele de pe liniile precedente; în consecință, valoarea j a coloanei în care se pune dama succesoare nu trebuie să se gasească pe nici una din pozițiile anterioare ale stivei;
  b/ dama succesoare nu trebuie să se găsească pe aceeași diagonală cu niciuna din damele din liniile precedente, deci pentru nici o pozitie j din stivă  nu trebuie fie satisfacută egalitatea |j[i]-j[k]|==|i-k|, în care j[i] este valoarea indicelui j (de coloană) memorată pe poziția i a stivei, iar j[k] este valoarea indicelui j (de coloană) pentru linia de indice k, în care se va plasa dama succesoare.
Soluția problemei trebuie să conțină câte o damă pe fiecare linie a tablei de șah, respectând aceste restricții.
 
În fișierul NDame.java este definită clasa NDame, care extinde clasa Backtracking și aplică la stabilirea succesorului valid restricțiile menționate mai sus. 
În fișierul TestNDame.java este dată o aplicație de testare. La punerea în execuție a aplicației, în linia de comandă se dă numărul de carouri de pe o latură a tablei de șah.

Backtracking recursiv

Așa cum s-a arătat și în cazul parcurgerii arborilor, întrucât la realizarea backtrackingului se folosește stiva, acesta poate fi realizat și folosind funcții recursive.

Rezolvarea problemelor prin tehnica "forței brute"

În multe situații practice, în care trebuie să se aleagă dintre mai multe variante posibile soluția care satisface anumite condiții (de exemplu soluția de cost minim, sau de profit maxim și care îndeplinește eventual și anumite restricții) se poate face aplicând principiul "forței brute" în modul următor: se generează toate variantele posibile, dintre care se selectează numai acele variante care indeplinesc restricțiile impuse și, în final, dintre variantele astfel selectate se alege cea optimă. Avantajul acestei tehnici este simplitatea, cel puțin la nivel conceptual. Marele desavantaj este că, cu cresterea dimensiunii n (a numărului de elemente din mulțimile de date asupra cărora se aplică algoritmul), numărul de variante posibile crește foarte rapid. În consecință, în general tehnica "forței brute" nu este convenabilă pentru cazul când numărul de elemente este mare. Întotdeauna când există pentru o anumită problemă un algoritm mai eficient, trebuie folosit acesta. Totuși, cand astfel de algoritmi nu exista sau nu se cunosc, la nevoie se poate recurge și la "forța brută"

În secțiunea precedentă s-au prezentat algoritmi prin care se pot genera toate soluțiile posibile pentru diferite probleme tipice. Dacă dorim să aplicăm "forța brută" pentru rezolvarea unei probleme particulare, stabilim mai întâi în care din cazurile menționate se încadrează variantele de soluții, generăm soluțiile respective și apoi o selectăm pe cea corespunzătoare condițiilor problemei.
 
Iată un exemplu: să considerăm că la o conferință, în jurul unei mese rotunde, trebuie asezate n persoane, astfel încât să nu fie așezate alături două persoane rivale, fiind dată pentru fiecare persoană lista rivalilor acesteia. Remarcăm imediat că soluția, dacă există, se găsește printre permutările celor n persoane. În consecință, generăm toate permutările de n obiecte și le selectăm pe acelea în care, pentru fiecare persoană în parte, cei doi vecini nu se găsesc în lista de rivali.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați