admin
Administrator
Data inscrierii: 30/Ian/2007
Mesaje: 76
|
 Trimis: 24/10/2007 19:08 Titlul subiectului: Probleme clasice |
 |
|
Backtraking
1) Problema generarii permutarilor multimii A={1,2, ... , n}
2) Generarea aranjamentelor de n elemente luate câte p.
Elementele sunt din multimea A={1,2,....,n}, si 1<p<n.
3) Generarea permutarilor unei multimi A={a1,a2, ... , an}
Indicatie: Se foloseste algoritmul de generare a
? permutarilor de la prob. 1) si adresarea indirecta.
4) Generarea combinarilor de n elemente luate câte p.
Observatie: Obtinerea combinarilor se face mai modest cu
o conditie de continuare <adevarata> pentru orice solutie
partiala, folosind o initializare convenabila a unei
componente din vector cu valoarea componentei anterioare.
5) Generarea submultimilor unei multimi cu n elemente A={1,2,...,n}.
6) Generarea produsului cartezian A la p, unde A={1,2,...,n}.
7) Generarea produsului cartezian a n multimi An cu numar
diferit de elemente.
8) Generarea partitiilor unei multimi.
Fie A o multime finita, A={1,2,...,n}. Sa se genereze
toate partitiile multimii A.
Observatie: Numarul de partitii cu k submultimi este notat cu S(n,k).
S(n,k)=S(n-1,k-1)+k*S(n-1,k)
Numerele S(n,k) sunt vestite în matematica sub numele
de "numerele lui Stirling de speta a doua".
9) Sa se genereze permutarile multimii A={1,2, ... , n} de forma
P=(p1,p2, ..., pn) în care pk ? k, 1<= k <n>=n.
16. Problema comis-voiajorului
Un comis-voiajor trebuie sa viziteze un numar de n orase. Initial, asta
se afla într-unul dintre ele, notat 1. Comis-voiajorul doreste sa nu treaca
de doua ori prin acelasi oras, iar la întoarcere sa revina în orasul 1.
Cunoscând legaturile existente între orase, se cere sa se tipareasca
toate drumurile posibile pe care le poate efectua comis-voiajorul.
17. Problema colorarii hartilor
Fiind data o harta cu n tari, se cer toate solutiile de colorare a hartii,
utilizând maxim 4 culori, astfel încât doua tari cu frontiera comuna
sa fie colorate diferit.
Observatie: Este demonstrat faptul ca sunt suficiente numai 4 culori
astfel încât indiferent ce harta plana sa poata fi colorata in conditiile din enunt.
18. Problema bilei
Un teren este reprezentat sub forma unei matrice A cu m linii si
n coloane. Elementele a[i,j] ce apartin multimii numerelor reale
reprezinta cotele diferitelor portiuni din acest teren. Se presupune
ca o bila se gaseste pe o portiune deținând o anumita cota. Se cere
sa se precizeze toate traseele posibile de a fi urmate de bila spre
a iesi din teren, stiind ca bila se poate deplasa în orice portiune
de teren învecinata cu o cota strict inferioara cotei terenului
pe care se gaseste bila.
Bactracking generalizat (în plan)
19. Problema labirintului
Fiind dat un labirint sub forma unei matrici patratice cu m linii
si n coloane, în care anumite pozitii sunt ocupate, se cere sa
se determine toate pozitiile în care poate ajunge un mobil ce
pleaca din punctul initial (i,j) stiind ca el se poate deplasa
doar astfel:
- cu o pozitie la dreapta pe aceeasi linie;
- cu o pozitie la stânga pe aceeasi linie;
- cu o pozitie în jos pe aceeasi coloana;
- cu o pozitie în sus pe aceeasi coloana.
20. Problema sariturii calului (enuntata de Leonhard Euler)
Se considera o „tabla de sah” patratica cu n linii si n coloane.
Un cal pleaca din pozitia (1,1), adica din coltul din stânga sus.
Nici o pozitie nefiind interzisa, se cere sa se efectueze cu calul,
conform regulilor din sah, o succesiune de mutari astfel încât
calul sa treaca o singura data prin fiecare pozitie a tablei.
21. Se considera o „tabla de sah” ca în problema anterioara.
Se cere sa se obtina toate mutarile astfel încât calul sa revina
în pozitia initiala.
Bactracking cu optimizari |
|
