metoda backtracking- trebuiesc codificate oarecum direcţiile de deplasare prin numere, litere,...
TRANSCRIPT
CN Onisifor Ghibu Oradea Cerc de informatică
Metoda backtracking
1. Descrierea metodei
Această metodă generală de programare se aplică problemelor în care trebuie determinate toate soluțiile
problemei, soluţia se poate reprezenta sub forma unui vector X = (x1, ..., xn), iar x1 A1, … xn An unde
mulţimile A1, ..., An sun tmulţimi finite având |Ai| = ai elemente. Pentru fiecare problemă concretă sunt date
anumite relaţii între componentel ex1, ...xn ale vectorului X, numite condiţii interne.
Mulţimea finită A = A1 x A2 x... x An se numeşte spaţiul soluţiilo rposibile (este un produs cartezian). Soluţiile
posibile care satisfac condiţiile interne se numesc soluţii rezultat. Ceea ce ne propunem este de a determina
toate soluţiile rezultat, cu scopul de a le afişa sau de a allege dintre ele una care maximizează sau minimizează o
eventual funcţie obiectiv dată.
Metoda backtracking se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii:
- trebuie generate toate soluțiile problemei;
- soluţia poate fi pusă sub forma unui vector X = (x1, x2 ..., xn), cu x1 A1 …. xn An. MulţimileA1, A2, …
An sun tmulţimi finite, iar elementelelor se află într-o ordine bine stabilită;
- nu se dispune de o metodă de rezolvare ma irapidă.
Pentru uşurarea înţelegerii metodei vom prezenta o rutină unică, aplicabilă oricărei probleme, rutină care
utilizează noţiunea de stivă.
- se alege primul element x1, c eaparţine lui A1;
- presupunând generate elementele x1…xk, vom căuta elemental xk+1. Vom avea 2 posibilităţi:
o nu s-a găsit un astfel de element, caz în care se reia căutarea, considerând generate elementele x1
… xk-1, iar aceasta se reia de la următorul element din Ak, rămas netestat.
o a fost găsit, caz în care se testează dacă acesta îndeplineşte anumite condiţii.
dacă le îndeplineşte, se testează dacă s-a ajuns la soluţie
dacă s-a ajuns la soluţie, se tipăreşt eşi se continuă algoritmul pentru găsirea unei
alte soluţii, considerându-se generate x1…xk, iar elemental xk+1 se caută printer
elementele mulţimii Ak+1 rămase netestate
dacă nu s-a ajuns la soluţie se reia algoritmul considerându-se generate elementele
x1, … xk, xk+1 și se caută elementul xk+2.
dacă nu le îndeplineşte se reia algoritmul considerând generate x1…xk, iar elementul xk+1
se caută printre elementele mulţimii Ak+1 rămase netestate.
2. Implementareametodei
2.1. Variantaiterativă
a) Date și structure de date
- vectorul st[] - pentru a memora elementele xk ale soluției se folosește o structură de date de tip stivă,
implementată static printr-un vector.
- k – vârful stivei. Când s-a găsit elemental xk se urcă în stivă prin incrementare avârfului cu 1 (k++), pentru a
căuta elemental xk+1 al soluției, ia rpentru a reveni la elemental xk-1 se decrementează vârful.
CN Onisifor Ghibu Oradea Cerc de informatică
- as - pentru a ști dacapentruelementulxk al solu\ieimaiexista un succesor, adicădacămaiexista un elementînmulțimeaAk
care arputea fi elementulxk al soluției (este o variabilălogicăce are valoarea 1 -true, dacaexistăsuccesor; altfel, are valoarea
0).
- ev – pentru a ști dacă elementul găsit respectă condiția de continuitate și poate fi elementul xk al soluției (este
o variabilă logică ce are valoarea 1 -true, daca elemental este valid; altfel, are valoarea 0).
- n – dimensiunea soluției.
Obs. – în unele probleme (aranjamente, permutări, combinări etc) elementul xk este format dintr-o singură valoare, iar
în problemele în care trebuie găsit un traseu xk este format de regulă din două valori care reprezintă
coordonatele poziției în care se face deplasarea.
b) Subprograme
- subprogramul init() – de tip void. Inițializează elemental xk din vârful stivei. Acest subprogram are rolul
de a începe căutarea elementului xk de la începutul mulțimii Ak. În acest sens lui xk i se atribuie o valoare a
cărui successor va fi primul element din Ak.
- subprogramul successor() – de tip int. Cauta in multimea A daca elementul de pe nivelul k care este
curent are succesor sau nu. În caz afirmativ se generează această valoare și se returnează valoarea 1, în caz
contrar se returnează valoarea 0. Valoarea returnată se atribuie variabilei as.
- subprogramul valid() – de tip int. Verifică dacă valoarea de pe nivelul k îndeplineşte condiţiile interne. În
caz afirmativ se returnează valoarea 1, în caz contrar se returnează valoarea 0. Valoarea returnată se atribuie
variabilei ev.
- subprogramul solutie() – de tip int. Verifică dacă s-a ajuns sau nu la o soluţie finală. În caz afirmativ se
returnează valoarea 1, în caz contrar se returnează valoarea 0.
- subprogramul tipar() – de tip void. Afișează soluția.
- subprogramul bkt() – implementează strategia backtracking.
k=1; //se completează stiva începând cu primul nivel
init(); //se iniţializează primul nivel al stivei
while (k>0)//cat timp stiva nu e vida
{
as = 1; ev = 0;
while (as && !ev) //se caută succesor pe nivelul k atâta
{ //timp cât există succesor care nu este valid
as = successor(); //se cauta succesor
if (as) //daca există successor
ev = valid();//se verifica daca e valid
} //iesim daca nu mai e successor sau daca am gasit un element ok
if(as) //daca avem succesor
if(solutie()) //dacă s-a completat stiva
CN Onisifor Ghibu Oradea Cerc de informatică tipar(); //se tipăreşte soluţia
else //stiva nu s-a completat
{
k++; // se trece pe nivelul următor
init(); // se iniţializează noul nivel
}
else k--; // nu există succesor pentru nivelul k,
//deci se coboară un nivel în stivă
}
2.2. Varianta recursivă
a) Date și structure de date
- vectorul st[] - pentru a memora elementele xk ale soluției se folosește o structură de date de tip stivă,
implementată static printr-un vector.
- k – vârful stivei. Când s-a găsit elemental xk se urcă în stivă prin incrementare avârfului cu 1 (k++), pentru a
căuta elemental xk+1 al soluției, ia rpentru a reveni la elemental xk-1 se decrementează vârful.
b) Subprograme
Se vor folosi aceleași subprograme ca și în cazul variantei iterative, doar tehnica backtracking (subprogramul
bkt()) va fi implementat recursiv. Forma general a acestuia va fi:
init(); //se iniţializează primul nivel al stivei
while (successor(k))//cat timp mai am succesor
{
if(valid(k) { //daca acesta e valid
if(solutie(k)) //dacă s-a completat stiva
tipar(k); //se tipăreşte soluţia
else //stiva nu s-a completat
bkt(k+1); // se trece pe nivelul următor
}
}
Primul apel al suprogramului are loc pentru primul nivel (de regula bkt(1)).
3. Probleme propuse
3.1. Pentru a înțelege modul de funcționare
Un algoritm generează în ordine descrescătoare, toate numerele de n cifre (n<9), cu cifrele în ordine strict
crescătoare, care nu au două cifre pare alăturate. Dacă pentru n=5, primele cinci soluţii generate sunt 56789,
45789, 45679, 45678, 36789, precizaţi care sunt următoarele trei soluţii generate, în ordinea obţinerii lor.
CN Onisifor Ghibu Oradea Cerc de informatică
Generând şirurile de maximum 3 caractere distincte din mulţimea {A,B,C,D,E}, ordonate lexicografic, obţinem
succesiv: A, AB, ABC, ABD, ... . Ce şir va fi generat imediat după BAE?
Un program citeşte o valoare naturală nenulă impară pentru n şi apoi generează şi afişează în ordine crescătoare
lexicografic toate combinaţiile formate din n cifre care îndeplinesc următoarele proprietăţi:
- încep şi se termină cu 0;
- modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este 1.
Astfel, pentru n=5, combinaţiile afişate sunt, în ordine, următoarele: 01010, 01210. Dacă se rulează acest
program şi se citeşte pentru n valoarea 7, imediat după combinaţia 0101210 va fi afişată combinaţia:
Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,2,9} se utilizează un algoritm
backtracking care, pentru n=2, generează, în ordine, numerele 20,22,29,90,92,99. Dacă n=4 şi se utilizează
acelaşi algoritm, care este numărul generat imediat după numărul 2009?
Se utilizează metoda backtracking pentru a genera toate cuvintele formate din două litere distincte din muţimea
{w,x,z,y} astfel încât niciun cuvânt să nu înceapă cu litera x şi niciun cuvânt să nu conţină litera w lângă litera
z. Cuvintele vor fi generate în ordinea wx, wy, zx, zy, yw, yx, yz. Folosind aceeaşi metodă se generează toate
cuvintele de două litere distincte din mulţimea {w,x,z,y,t} astfel încât niciun cuvânt să nu înceapă cu litera x şi
niciun cuvânt să nu conţină litera w lângă litera z. Care sunt a treia şi a patra soluţie generată?
3.2. De încălzire
1. Generarea permutărilor
2. Generarea aranjamentelor
3. Generarea combinărilor
4. Generarea tuturor submulţimilor
5. Generarea tuturor partiților unui număr
6. Generarea tuturor partiţiilor unei mulţimi
7. Generarea produsului cartezian al n mulţimi
8. Problema celor n dame
4. Backtracking în plan
Metoda Backtracking în plan are câteva modificări:
- un element al soluției este format din mai multe valori (de regulă coordonatele în plan);
- trebuiesc codificate oarecum direcţiile de deplasare prin numere, litere, elemente, etc. (N, S, E, V).
Fie următoarea problemă: Într-un labirint, reprezentat ca o matrice L, cu n linii şi m coloane, cu componente 0
sau 1, (1 semnificând perete, 0 culoar) se găseşte o bucată de brânză pe poziţia (xb, yb) şi un şoricel pe poziţia
(xs, ys). Afişaţi toate posibilităţile şoricelului de a ajunge la brânză, ştiind că el se poate deplasa numai pe
culoar, iar direcţiile posibile de mişcare sunt N, E, S, V. De exemplu, pentru un labirint cu 4 linii şi 4 coloane de
forma următoare, în care şoricelul se găseşte pe poziţia 1 1, iar brânza pe poziţia 4 4
0 1 1 1
0 1 1 1
0 0 0 1
0 0 0 0
Se va afișa:
(1,1), (2,1), (3,1), (3,2), (3,3), (4,3), (4,4) //prima solutie
(1,1), (2,1), (3,1), (3,2), (4,2), (4,3), (4,4) //a doua solutie
CN Onisifor Ghibu Oradea Cerc de informatică
(1,1), (2,1), (3,1), (4,1), (4,2), (3,2), (3,3), (4,3), (4,4) //a treia solutie
(1,1), (2,1), (3,1), (4,1), (4,2), (4,3), (4,4) //a patra solutie
Rezolvare:
- pentru codificarea direcțiilor de deplasare vom folosi doi vectori dx și dy, asftel încât dx va indica
deplasarea pe axa x, dy deplasarea pe axa y, inițializați astfel: dx[] = {0,1,-1,0,0},dy[] =
{0,0,0,1,-1};(primul element (0,0) e de decor).
- Vom folosi a nouă variabilă tr care va reține poziția în care ne deplasăm. Poziția de pe nivelul k va fi
poziția de pe nivelul k-1 la care se adugă direcția de deplasare.
- Primul element al traseului va fi poziția în care se găsește șoricelul. Pentru ca aceasta să rămână
permanent în vector o vom trece pe poziția 0. int n,m,a[10][10],ls,cs,lb,cb,nr,sol[10];
struct traseu {
int x,y;
}tr[10];
int dx[] = {0,1,-1,0,0},dy[] = {0,0,0,1,-1};
void citire(){
int i,j;
f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) f>>a[i][j];//citim labirintul
f>>ls>>cs>>lb>>cb;//citim poziția șoricelului și poziția finală
}
void border(){//marginea e perete
int i;
for(i=0;i<=n+1;i++) a[i][0] = a[i][m+1] = 1;
for(i=0;i<=m+1;i++) a[0][i] = a[n+1][i] = 1;
}
int solutie(int k) { //ajungem la solutie daca am ajuns la branza
if(tr[k].x== lb && tr[k].y == cb) return 1;
return 0;
}
void tipar(int k) {
int i;
g<<"("<<tr[0].x<<","<<tr[0].y<<")";//afisam punctual de plecare
for(i=1;i<=k;i++) g<<", ("<<tr[i].x<<","<<tr[i].y<<")";//afisam traseul
g<<"\n";
}
void init(int k){
sol[k] = 0;
}
int succesor(int k){
if(sol[k]<4) {
sol[k] = sol[k] + 1;//generam succesorul
tr[k].x = tr[k-1].x + dx[sol[k]];//calculam noua pozitie
tr[k].y = tr[k-1].y + dy[sol[k]];
return 1;
}
else
return 0;
CN Onisifor Ghibu Oradea Cerc de informatică }
int valid(int k){//verificam daca noua pozitie e valida
if(a[tr[k].x][tr[k].y]==1) return 0;//daca e perete nu e valida
int i;
//daca am mai fost in pozitia respectiva, nu e valida
for(i=1;i<k;i++) if(tr[i].x == tr[k].x && tr[i].y == tr[k].y) return 0;
return 1;
}
void bkt(int k){
init(k);
while(succesor(k)) {
if(valid(k)) {
if(solutie(k)) tipar(k);
else bkt(k+1);
}
}
}
int main()
{
citire();
border();
tr[0].x=ls;tr[0].y=cs;//pozitia de plecare
bkt(1);
return 0;
}
Aplicații
1. Fiind data o tabla de sah cu dimensiunea de nxn si un cal plasat in coltul din stanga sus, se cere sa se
afiseze o posibilitate de mutare a acestei piesede sah astfel incat sa treaca o singura data prin fiecare
patrat al tablei.
Pentru n = 5 o soluție ar putea fi
2. Se da un labirint sub forma de matrice cu m linii si n coloane. Fiecare element al matricei reprezinta
o camera a labirintului. Intr-una din camere, de coordonate lin si col, se gaseste un om. Se cere sa se
gaseasca toate iesirile din labirint. Ieșirea din labirint se poate face prin oricare cameră situată pe
prima sau ultima linie, respective pe prima sau ultima coloană. Nu este permis ca un drum sa treaca
de doua ori prin aceiasi camera. În camerele codificate cu 0 se poate intra în timp e în camerele
codificate cu 1 nu se poate intra.
5. Probleme propuse
5.1. Examen
Un student primeşte la un examen n subiecte, numerotate de la 1 la n (1≤n≤20). Pentru fiecare subiect
este cunoscut punctajul care se obţine rezolvând subiectul respectiv (nu se acordă punctaje parţiale), precum şi
dificultatea subiectului. Studentul vrea să obţină cel puţin un punctaj total P, dar nu poate să rezolve subiecte cu
dificultate > D.
CN Onisifor Ghibu Oradea Cerc de informatică
Determinaţi toate variantele în care studentul poate obţine un punctaj satisfăcător.
Fişierul de intrare examen.in conţine pe prima linie trei numere naturale separate prin spaţii n, P şi D, cu
semnificaţia din enunţ. Pe cea de a doua linie se află n numere naturale separate prin spaţii, reprezentând, în
ordine, dificultăţile subiectelor. Pe cea de a treia linie se află n numere naturale separate prin spaţii,
reprezentând, în ordine, punctajele subiectelor.
Fişierul de ieşire examen.out va conţine câte o linie pentru fiecare variantă generată. Descrierea unei
variante este constituită din numerele subiectelor rezolvate, separate prin câte un spaţiu. Dacă nu există nici o
variantă satisfăcătoare, fişierul de ieşire va conţine pe prima linie mesajul MAI INVATA!.
5.2 Jucării - http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1072
Alex are pe un raft n jucării. Pe fiecare jucărie se află scris unul dintre numerele 1, 2, ..., n. Nu există două
jucării pe care să fie scris acelaşi număr. După ce se joacă cu aceste jucării, Alex le pune din nou pe raft,
aranjate în şir, astfel încât să existe cel puţin k dintre ele în ordine crescătoare (nu neapărat pe poziţii
consecutive). Spre exemplu, pentru n=5 şi k=3 şirul de jucării 3 1 4 2 5 este corect, dar 4 3 5 2 1 nu este corect.
Primul şir are jucării are cel puţin trei jucării aşezate în ordine crescătoare (de exemplu 1, 2, 5), iar cel de-al
doilea nu are trei jucării în ordine crescătoare.
Cerinţă
Să se scrie un program care determină cea de a p-a modalitate de a aşeza jucăriile pe raft astfel încât să respecte
condiţia din enunţ, considerând modalităţile în ordine lexicografică.
Date de intrare
Fişierul de intrare jucarii.in are pe prima linie numerele naturale n k p separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire jucarii.out va conţine o singură linie pe care vor fi scrise n numere naturale distincte cuprinse
între 1 şi n, separate prin câte un singur spaţiu, reprezentând cea de a p–a modalitate în ordine lexicografică.
Restricţii
0 < k ≤ n < 11
0 < p ≤ maxim(numărul de modalităţi, 50050)
Un şir de numere x=(x1, x2, ..., xn) este mai mic în ordine lexicografică decât şirul y=(y1, y2, ..., yn), dacă
există un indice h, cu proprietăţile: x1=y1, …, xh-1=yh-1 şi xh<yh.
Exemple
jucarii.in jucarii.out Explicaţie
4 3 7 2 3 1 4 Modalităţile în ordine lexicografică sunt următoarele: 1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
2 1 3 4
2 3 1 4
CN Onisifor Ghibu Oradea Cerc de informatică
2 3 4 1
3 1 2 4
4 1 2 3
5.3. Scara - http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=798
Ion şi-a construit o vilă pe frumosul vârf al unui munte. Acum proiectează o scară specială, pe care va urca de la
şosea până la vilă. Diferenţa de nivel dintre şosea şi vilă este H (deci aceasta trebuie să fie înălţimea totală a
scării). Scara va avea N trepte, toate de aceeaşi lăţime, dar de înălţimi distincte două câte două.
Ion a sesizat că efortul pe care îl depune pentru a urca o treaptă este egal cu înălţimea treptei. Dar dacă el urcă x
trepte deodată, efortul depus este egal cu media aritmetică a înălţimilor acestor x trepte pe care le urcă deodată +
un efort de valoare constantă p (necesar pentru a-şi lua avânt).
Fiind un tip atletic, Ion poate urca mai multe trepte deodată, dar suma înălţimilor treptelor urcate deodată nu
trebuie să depăşească o valoare maximă M.
Cerinţă
Scrieţi un program care să determine efortul minim necesar pentru a urca pe o scară construită conform
restricţiilor problemei, precum şi o modalitate de a construi scara care va fi urcată cu efort minim.
Date de intrare
Fişierul de intrare scara.in va conţine pe prima linie 4 numere naturale separate prin câte un spaţiu H N M p
(cu semnificaţia din enunţ).
Date de ieşire
Fişierul de ieşire scara.out va conţine
– pe prima linie va fi scris efortul minim necesar (cu 2 zecimale cu rotunjire);
– pe cea de a doua linie vor fi scrise N numere naturale nenule care reprezintă înălţimile celor N trepte ale scării
(în ordinea de la şosea către vilă), separate prin câte un spaţiu.
Restricţii şi precizări
0 < H 75
0 < N 8
0 < M < 14
0 p 10
Pentru datele de test, problema are întotdeauna soluţie.
Dacă există mai multe soluţii (modalităţi de a construi scara astfel încât să obţineţi efortul minim dorit), veţi
afişa prima soluţie în ordine lexicografică.
Spunem că vectorul x=(x1, x2, ..., xk) precedă în ordine lexicografică vectorul y=(y1, y2, ..., yk) dacă există i1
astfel încât xj=yj, pentru orice j<i şi xi<yi.
Dacă a doua zecimală a efortului minim este 0, sau chiar ambele zecimale sunt 0 nu este necesar să le afişaţi.
Deci în exemplu s-ar fi putut scrie efortul minim 9 sau 9.0.
Exemplu
scara.in scara.out
10 4 5 2 9.00
1 4 2 3
Backtracking în plan:
CN Onisifor Ghibu Oradea Cerc de informatică
1. Monkey - http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=713
2. Immortal OJI 2010 - http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1078
Cei care au văzut filmul Nemuritorul, ştiu că fraza cu care nemuritorii încep lupta este "Nu poate să rămână decât unul
singur". Să încercăm să simulăm povestea nemuritorilor.
Într-o zonă dreptunghiulară formată din n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m) se află
maxim nxm-1 nemuritori. Doi nemuritori vecini se "luptă" între ei şi cel care pierde lupta este eliminat. "Lupta" constă în
săritura unuia dintre nemuritori peste celălalt, dacă această săritură se poate face. Săritura se poate face pe orizontală
sau verticală şi nemuritorul peste care s-a sărit dispare. Prin vecin al nemuritorului din poziţia (i,j) înţelegem un
nemuritor din una dintre poziţiile (i-1,j), (i+1,j), (i,j-1), (i,j+1). Deci, după luptă nemuritorul din câmpul
(i,j) se va găsi în una dintre poziţiile: (i-2,j), (i+2,j), (i,j-2) sau (i,j+2), dacă această poziţie este liberă şi
este în interiorul zonei.
Cerinţă: Se cere să se determine o succesiune a luptelor ce pot fi purtate, astfel încât la final să rămână un singur
nemuritor.
Date de intrare: Fişierul de intrare immortal.in conţine pe prima linie trei valori naturale n m I, separate prin câte
un spaţiu, reprezentând numărul de linii, numărul de coloane ale zonei descrise şi respectiv numărul de nemuritori
existenţi iniţial. Următoarele I linii conţin fiecare câte două numere naturale x y separate printr-un spaţiu,
reprezentând poziţiile unde se găsesc iniţial cei I nemuritori (linia şi coloana).
Date de ieşire: Fişierul de intrare immortal.out va conţine I-1 linii, fiecare linie descriind o "luptă". Luptele vor fi
scrise în ordinea în care au avut loc. O linie va conţine 4 numere naturale care indică: primele două poziţia de pe care
pleacă un nemuritor la "luptă", ultimele două poziţia pe care acesta ajunge după "luptă". Pentru ca "lupta" să fie
corectă, în poziţia peste care nemuritorul "sare" trebuie să existe un nemuritor care va "muri". O poziţie va fi specificată
prin indicele de linie urmat de indicele de coloană. Valorile scrise pe aceeaşi linie vor fi separate prin spaţii.
Restricţii
1 < n, m ≤ 20
1 < I ≤ min{15, n*m-1}
Pentru datele de test există întotdeauna soluţie.
Exemplu
immortal.in immortal.out 3 4 4
1 2
2 1
3 2
3 3
3 3 3 1
3 1 1 1
1 1 1 3
1 2 3 4
================= (3,3) --> (3,1) dispare (3,2)
1| | * | | | (3,1) --> (1,1) dispare (2,1)
|---------------| (1,1) --> (1,3) dispare (1,2)
2| * | | | |
|---------------|
3| | * | * | |
=================
Timp maxim de execuţie/test: 0.5 secunde/test
Memorie totală disponibilă: 2 MB, din care 1 MB pentru stivă.
Dimensiune maximă a sursei: 20 KB