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. |
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). |
Î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). |
Î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 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. |
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. |
Î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. |