|
|
|
Generarea permutarilor. Se citeste un numar natural n. Sa se genereze toate permutarile multimii .
Generarea permutarilor se va face tinand cont ca orice permutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.
Prezentam algoritmul corespunzator cazului n=3:
1
2
3
1
2
2
2
2
1
1
1
1
1
1
1
2
3
3
3
3
3
1
1
1
1
1
2
2
1
2
3
1
1
1
1
2
3
3
2
2
2
2
2
2
se incarca in stiva pe nivelul 1 valoarea 1;
incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stivei;
incarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnita;
valoarea 1 din nivelul al 3-lea se regaseste pe nivelul 1;
valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-lea;
valoarea 3 pe nivelul al 3-lea nu e intalnita pe nivelurile anterioare; intrucat nivelul 3 este completat corect. Tiparim: 1 2 3
Algoritmul continua pana cand stiva devine vida.
Problema celor n dame. Fiind data o tabla de sah n n se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (damele sa nu se atace reciproc).
Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4 4, o solutie ar fi urmatoarea:
D
D
D
D
Cum procedam? Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1 coloana 1.
D
A doua dama nu poate fi asezata decat pe coloana a 3-a.
D
D
Observam ca a treia dama nu poate fi plasata in linia a 3-a. Incercam atunci plasarea celei de-a doua dame in coloana a 4-a.
D
D
A treia dama nu poate fi plasata decat pe coloana a 2-a.
D
D
D
In aceasta situatie dama a patra nu mai poate fi asezata. Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana a treia, nici in coloana a patra, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana a doua.
D
A doua dama nu poate fi asezata decat in coloana a patra.
D
D
Dama a treia se aseaza in prima coloana.
D
D
D
Acum este posibil sa plasam a patra dama in coloana a treia si astfel am obtinut o solutie a problemei.
D
D
D
D
Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.
Pentru prezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama). Exemplu: pentru solutia gasita avem vectorul st ce poate fi asimilat unei stive.
Doua dame se gasesc pe aceeasi diagonala daca si numai daca este indeplinita conditia. |st (i) - st (j)| = |i-j| : (diferenta, in modul, intre linii si coloane este aceeasi).
3
ST (4)
1
ST (3)
In general ST(i) = k semnifica faptul ca pe linia i dama ocupa pozitia k.
4
ST (2)
2
ST (1)
Exemplu: In tabla 4 4 avem situatia:
D
St (1) = 1 i = 1;
St (3) = 1 j = 3;
| St (1) - st (3) | = |1 - 3| = 2
|i - j| = |1 - 3| = 2
D
Sau situatia:
D
St (1) = 3 i = 1;
St (3) = 1 j = 3;
| St (i) - st (j) | = |3 - 1| = 2
|i - j| = |3 - 1| = 2
D
Intrucat doua dame nu se pot gasi pe aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema (ca doua dame sa nu fie plasate in aceeasi diagonala). A proceda astfel, inseamna sa lucra conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea. Fata de programul de generare a tuturor solutiilor problemei celor n dame, are o singura conditie suplimentara, in procedura valid.
Produsul cartezian a n multimi. Se dau multimile de mai jos si se cere produsul cartezian al lor.
A1 =
A2 =
.........
An =
Exemplu: A1 =
A2 =
A3 =
A1 A2 A3 = .
Pentru rezolvare, se folosesc stiva ST si un vector A ce retine numerele k1, k2, .kn. Utilizam metoda backtracking, usor modificata din urmatoarele motive:
a) Orice element aflat la nivelul k al stivei este valid, motiv pentru care procedura valid nu face altceva decat sa atribuie variabilei ev valoarea TRUE.
b) Limita superioara pe nivelul k al stivei este data de A(k).
Modul de concepere a algoritmului rezulta din cele ce urmeaza:
1
2
3
1
1
1
1
2
2
1
1
1
1
1
1
2
3
1
2
3
2
2
3
3
3
3
1
1
1
1
1
1
Observatii:
Algoritmul prezentat aici este de tip backtracking? Intrebarea are sens pentru ca este absent mecanismul de intoarcere. Vom admite ca si aceasta este backtracking, dar "degenerat".
Generarea aranjamentelor. Se citesc n si p. Sa se genereze toate aranjamentele de n luate cate p.
Din analiza problemei rezulta urmatoarele:
stiva are inaltimea p;
fiecare nivel ia valori intre 1 si n;
elementele plasate pe diverse niveluri trebuie sa fie distincte.
Algoritmul este asemanator cu cel de la permutari, cu deosebirea ca aici stipa are inaltimea p.
Generarea combinarilor. Se citesc n si p numere naturale, n p. Se cere sa se genereze toate submultimile cu p elemente ale multimii .
Pentru rezolvarea problemei trebuie tinut cont de urmatoarele:
stiva are inaltimea p;
elementele aflate pe niveluri diferite ale stivei trebuie sa fie distincte;
pentru a evita repetitia elementele se aseaza in ordine crescatoare: pe nivelul k se va afla o valoare mai mare decat pe nivelul k-1 si mai mica sau egala cu n-p+k.
Problema comis-voiajorului. Un comis voiajor trebuie sa viziteze un numar n de orase. Initial, el se afla intr-unul dintre ele, notat 1. Comis - voiajorul doreste sa nu treaca de doua ori prin acelasi oras, iar la intoarcere sa revina in orasul 1. Cunoscand legaturile existente intre orase, se cere sa se tipareasca toate drumurile posibile pe care le poate efectua comis - voiajorul.
Exemplu: In figura alaturata sunt simbolizate cele 6 orase, precum si drumurile existente intre ele.
2
3
1
4
6
5
Comis - voiajorul are urmatoarele posibilitati de parcurgere:
1, 2, 3, 4, 5, 6, 1;
1, 2, 5, 4, 3, 6, 1;
1, 6, 3, 4, 5, 2, 1;
1, 6, 5, 4, 3, 2, 1;
Legaturile existente intre orase sunt date in matricea An,n. Elementele matricei A pot fi 0 sau 1 (matricea este binara).
1, daca exista drum intre orasele i
si j;
A(i,j) =
0 , altfel
Se observa ca A(i,j) = A(j,i), oricare ar fi i,j I - matricea este simetrica.
Pentru rezolvarea problemei folosim stiva st. la baza stivei (nivelul 1) se incarca numarul 1. Prezentam in continuare modul de rezolvare a problemei.
2
De la orasul 1 la orasul 2 exista drum, deci se va urca in stiva;
1
2
Orasul 2 se mai gaseste in stiva, deci nu este acceptat;
2
1
3
De la orasul 2 la orasul 3 se gaseste drum; prin orasul 3 nu s-a mai trecut, deci orasul 3 este acceptat.
2
1
Algoritmul continua in acest mod pana se ajunge din nou la nivelul 1, caz in care algoritmul se incheie.
Un succesor, intre 2 si n, aflat pe nivelul k al stivei, este considerat valid daca sunt indeplinite urmatoarele conditii:
nu s-a mai trecut prin orasul simbolizat de succesor, deci acesta nu se regaseste in stiva;
exista drum intre orasul aflat la nivelul k-1 si cel aflat la nivelul k;
daca succesorul se gaseste la nivelul n, sa existe drum de la el la orasul 1.
Observatii:
1. Problemele rezolvate prin aceasta metoda necesita un timp indelungat de executie. Din acest motiv este bine sa utilizam metoda atunci numai atunci cand nu mai avem la dispozitie un alt algoritm mai eficient
2. Mentionam ca nu exista probleme pentru care nu se cunosc algoritmi eficienti de rezolvare, deci backtracking este indicata.
3. Rezolvarea iterativa incalca principiul stivei atunci cand verificam conditiile de continuare, sau atunci cand tiparim solutia gasita, pentru ca accesam orice nivel al stivei. Consider ca o structura trebuie folosita ca atare atunci cand este strict necesar. De exemplu, chiar si segmentul de stiva al calculatorului poate fi accesat oriunde. Asta nu inseamna ca acolo nu se utilizeaza din plin "mecanismul" stivei.
