Metoda backtracking
Ideile de bază pe scurt și, unde există, exercițiile din subiectele de BAC care le verifică. Lecția completă, animată, cu grile și exerciții corectate, e în aplicația Tomomi.
Pe scurt
Șablon: generează toate permutările
Permutări = toate ordinele celor n elemente. Le generezi crescător; pentru următoarea soluție schimbi cât mai în dreapta. Sunt n! permutări.
// pe hârtie, nu de scris la BAC:
123, 132, 213, 231, 312, 321 // ordinea pentru {1, 2, 3}
Idee: la BAC găsești următoarea soluție
La examen, backtracking nu înseamnă să scrii cod. Ți se dă ordinea generării și generezi soluțiile sau scrii soluția de după una dată. Codul îl citești doar ca să înțelegi ordinea.
Șablon: următorul tuplu (contor)
Produs cartezian peste {1, ..., m} pe n poziții: mⁿ tupluri. Următorul tuplu: crește poziția din dreapta; la depășire adu-o la 1 și du transportul la stânga. Submulțimile sunt cazul {da, nu}ⁿ, deci 2ⁿ.
Șablon: următoarea combinare
Combinări = k valori strict crescătoare din n; ordinea nu contează (12 = 21). Următoarea: crește poziția cea mai din dreapta care mai poate crește, apoi completează restul consecutiv. Sunt C(n, k).
Cum recunoști generatorul
used[] și toate pozițiile pline: permutări. Bucla 1..m pe fiecare poziție, fără used[]: produs cartezian (valori repetabile; submulțimi dacă m = 2). Parametrul start cu i + 1: combinări (strict crescător).
Șablon: următorul aranjament
Aranjamente = k elemente din n, cu ordine (12 ≠ 21) și fără repetiție. Următorul: crește poziția cea mai din dreapta care mai poate crește (cu o valoare încă nefolosită), apoi completează restul cu cele mai mici valori disponibile. Sunt A(n, k) = n · (n-1) · ... · (n-k+1).
// pe hârtie, nu de scris la BAC:
12, 13, 21, 23, 31, 32 // A(3, 2) = 3 · 2 = 6
Capcana: aranjamente, permutări sau combinări
Toate trei folosesc valori distincte, dar se deosebesc prin DOUĂ întrebări. Contează ordinea? Dacă nu, sunt combinări (12 = 21). Dacă da: te oprești la k sau la n? La k sunt aranjamente (rămân elemente nefolosite), la n sunt permutări. Pe scurt: permutările sunt aranjamente cu k = n.
Idee: când merită backtracking
Folosești metoda când ai nevoie de configurațiile în sine, construite pe poziții și date în ordine. Nu o folosești când răspunsul este un singur număr cu formulă: permutări, submulțimi, C(n, k) combinări. Costul crește exploziv, deci metoda are sens doar pentru n mic - exact cât se cere la examen.
Din subiectele de BAC
Exerciții reale din subiectele anilor trecuți. Încearcă-le singur înainte să deschizi rezolvarea.
Utilizând metoda backtracking, s-au generat toate codurile posibile pentru deblocarea unor telefoane, coduri de câte 6 cifre distincte, din mulțimea cifrelor, ordonată crescător. Fiecare cod are primele trei cifre impare și ultimele trei cifre pare. Primele patru coduri sunt 135024, 135026, 135028, 135042. Indicați penultimul cod generat.
a. 957862
b. 957846
c. 975862
d. 975846
Vezi rezolvarea
Codurile se generează în ordine lexicografică (crescătoare), pentru că la fiecare poziție cifrele se încearcă în ordinea crescătoare a mulțimii. Ultimul cod generat este deci cel mai mare cod posibil:
- primele trei cifre, impare distincte, cât mai mari:
9,7,5; - ultimele trei cifre, pare distincte, cât mai mari:
8,6,4.
Ultimul cod este 975864. Penultimul se obține modificând ultima poziție, singura care se schimbă cel mai des: cu prefixul 97586 fixat, cifrele pare rămase sunt 0, 2 și 4, deci codurile cu acest prefix sunt, în ordine, 975860, 975862, 975864. Penultimul cod generat este așadar 975862, litera c.
Atenție la capcană: penultimul NU se obține micșorând prima cifră - variantele a și b schimbă a doua cifră, ceea ce ar da coduri mult mai mici, generate cu mult înainte.
Utilizând metoda backtracking se generează toate permutările elementelor mulțimii ordonate {1, 2, 3, 4, 5, 6}; pentru fiecare permutare, pe primele trei poziții sunt doar valori pare, iar pe ultimele trei poziții sunt doar valori impare. Primele șase permutări generate sunt, în această ordine: (2,4,6,1,3,5), (2,4,6,1,5,3), (2,4,6,3,1,5), (2,4,6,3,5,1), (2,4,6,5,1,3), (2,4,6,5,3,1). Indicați a șaptea permutare generată.
a. (4,2,6,1,5,3) b. (4,2,6,1,3,5) c. (2,6,4,1,3,5) d. (2,4,6,5,3,2)
Vezi rezolvarea
Primele șase permutări păstrează prefixul par (2,4,6) și parcurg în ordine lexicografică toate cele 3! = 6 aranjamente ale valorilor impare (1,3,5).
După epuizarea lor, backtracking trece la următorul prefix par în ordine lexicografică: după (2,4,6) urmează (2,6,4). Prima permutare cu acest prefix folosește cea mai mică ordine a valorilor impare, adică (1,3,5).
A șaptea permutare generată este (2,6,4,1,3,5), litera c.
Utilizând metoda backtracking, se generează toate amestecurile de apă provenită din surse distincte din mulțimea {lac, mare, ocean, ploaie, râu}, astfel încât o sursă să fie de apă sărată și una sau două surse să fie de apă dulce. Marea și oceanul sunt surse de apă sărată, iar lacul, ploaia și râul sunt surse de apă dulce. Două amestecuri sunt distincte dacă diferă prin cel puțin o sursă a apei. Primele patru soluții obținute sunt, în această ordine: (lac, mare), (lac, mare, ploaie), (lac, mare, râu) și (lac, ocean). Scrieți soluția generată imediat înainte și soluția generată imediat după (ocean, ploaie).
Vezi rezolvarea
Soluțiile sunt generate în ordinea lexicografică a submulțimilor cu elemente în ordinea lac, mare, ocean, ploaie, râu, păstrând doar amestecurile valide (o sursă sărată + una sau două surse dulci):
(lac,mare), (lac,mare,ploaie), (lac,mare,râu), (lac,ocean), (lac,ocean,ploaie), (lac,ocean,râu), (mare,ploaie), (mare,ploaie,râu), (mare,râu), (ocean,ploaie), (ocean,ploaie,râu), (ocean,râu)
Imediat înainte de (ocean,ploaie) se generează (`mare`,`râu`), iar imediat după se generează (`ocean`,`ploaie`,`râu`).