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