Colegiul NaÈ›ional “Petru RareÈ™” Suceava
Introducere
Din când în când suntem puÈ™i în situaÈ›ia de a găsi o soluÈ›ie optimă la o problemă, cu toate că nu există nici o teorie aplicabilă pentru rezolvarea acesteia, cu excepÈ›ia verificării tuturor soluÈ›iilor. Acest tip de probleme care necesită generarea tuturor soluÈ›iilor È™i, eventual, alegerea unei soluÈ›ii optime se rezolvă cu ajutorul metodei backtracking.
Backtracking este o metodă de parcurgere sistematică a spaÅ£iului soluÅ£iilor posibile ale unei probleme. Este o metodă generală de programare, ÅŸi poate fi adaptată pentru orice problemă pentru care dorim să obÅ£inem toate soluÅ£iile posibile, sau să selectăm o soluÅ£ie optimă, din mulÅ£imea soluÅ£iilor posibile. Backtracking este însă ÅŸi cea mai costisitoare metodă din punct de vedere al timpului de execuÅ£ie.
În Informatică s-au impus în domeniul tehnicilor de programare metode definite ÅŸi elaborate de Artificial Intelligence: metoda backtracking (metoda „revenirii” implementată sub diverse forme); Metoda face legătura dintre programarea procedurală È™i programarea declarativă.
Tehnica backtracking se poate aplica doar pentru probleme ce admit conceptul de „candidat parÈ›ial de soluÈ›ie” È™i oferă un test relativ rapid asupra posibilității ca un astfel de candidat să fie completat către o soluÈ›ie validă. Când se poate aplica, însă, backtracking-ul este adesea mult mai rapid decât căutarea prin metoda forÈ›ei brute prin toÈ›i candidaÈ›ii, întrucât este capabilă să elimine dintr-un singur test, un mare număr de candidaÈ›i.
Termenul „backtrack” a fost inventat de matematicianul american D. H. Lehmer în anii 1950.
Metoda Backtracking = metoda „revenirii”, definită ÅŸi elaborată de AI; este rezultatul unei istorii din 1852, când studentul englez Francis Guthrie a enunÅ£at problema celor 4 culori: „sunt suficiente 4 culori pentru a colora o hartă ce reprezintă diverse ţări, cu condiÅ£ia ca oricare două ţări vecine (cu frontiera comună) să fie colorate cu culori diferite”.
Istorie
Forma generală a unei funcţii backtracking
Implementarea recursivă a algoritmului furnizat de metoda backtracking, este mai naturală ÅŸi deci mai uÅŸoară. Segmentul de stivă pus la dispoziÅ£ie prin apelul funcÅ£iei este gestionat în mod automat de sistem. Revenirea la pasul precedent se realizează în mod natural prin închiderea nivelului de stivă.
void BK(int k) //k-poziţia din vector care se completează
{
int i;
for (i=1; i<=nr_elemente_Sk; i++) //parcurge elementele mulţimii Sk
{
v[k]=i; //selectează un element din mulţime
if (validare(k)==1) //validează condiţiile de continuare ale problemei
{
if (solutie(k)==1) //verifică dacă s-a obţinut o soluţie
afisare(k); //afişează soluţia
else
BK(k+1); //reapelează functia pentru poziţia k+1
}
} //dacă nu mai există nici un element neselectat în mulÅ£imea Sk,
} //se închide nivelul de stivă ÅŸi astfel se revine pe poziÅ£ia k-1 a vectorului
//execuÅ£ia funcÅ£iei se încheie.
-după ce s-au închis toate nivelurile stivei, înseamnă că în vectorul v nu mai poate fi selectat nici un elemente din multimile Sk.
Problema celor n dame
Fiind dată o tablă de ÅŸah de dimensiune nxn, se cere să se aranjeze cele n dame în toate modurile posibile pe tabla de ÅŸah, astfel încât să nu se afle pe aceeaÅŸi linie, coloană, sau diagonală (damele să nu se atace).
​
Exemplu pentru n=4 se obţin două soluţii:
Soluţie:
-
pe linia k nu trebuie să mai fie o altă damă: această condiţie este satisfăcută datorită modului de reprezentare a soluţiei;
-
pe coloana corespunzătoare, care este S[k] nu trebuie să mai fie o altă damă: S[k]≠S[i], pentru iÎ[1,k-1];
-
oricare dintre damele aÅŸezate nu trebuie să se afle pe o acceiaÅŸi diagonală cu dama de pe linia k: pentru iÎ[1,k-1] damele aflate pe poziÅ£iile (i,S[i]) respectiv (k,S[k]) nu sunt pe acceaÅŸi diagonală dacă |i-k|≠|S[i]-S[k]|.
Programul C++
Descrierea metodei
În general vom modela soluÅ£ia problemei ca un vector v=(v1,v2,v3,...,vn) în care fiecare element vk aparÅ£ine unei mulÅ£imi finite ÅŸi ordonate Sk, cu k=1,n. În anumite cazuri particulare, mulÅ£imile S1 ,S2, S3,...,Sn pot fi identice . Procedăm astfel:
1. La fiecare pas k pornim de la o soluÅ£ie parÅ£ială v=( v1,v2,v3,...,vk-1) determinată până în acel moment ÅŸi încercăm să extindem această soluÅ£ie adăugând un nou element la sfârÅŸitul vectorului.
2. Căutăm în mulÅ£imea Sk , un nou element.
3. Dacă există un element neselectat încă, verificăm dacă acest element îndeplineÅŸte condiÅ£iile impuse de problemă, numite condiÅ£ii de continuare.
4. Dacă sunt respectate condiţiile de continuare, adăugăm elementul soluţiei parţiale.
5. Verificăm dacă am obţinut o soluţie completă.
- dacă am obţinut o soluţie completă o afişăm şi se reia algoritmul de la pasul 1.
- dacă nu am obţinut o soluţie, k <----- k+1 si se reia algoritmul de la pasul 1.
6. Dacă nu sunt respectate condiţiile de continuare se reia algoritmul de la pasul 2.
7. Dacă nu mai există nici un element neverificat în mulÅ£imea Sk înseamnă că nu mai avem nici o posibilitate din acest moment, să construim soluÅ£ia finală aÅŸa că trebuie să modificăm alegerile făcute în prealabil, astfel k <----- k-1 ÅŸi se reia problema de la pasul 1.
Revenirea în caz de insucces sau pentru generarea tuturor soluÅ£iilor problemei, a condus la denumirea de ”backtracking” a metodei, traducerea aproximativă ar fi “revenire în urmă”.
Proiect de atestat
Metoda de programare backtracking
Îndrumător:
Prof. Ududec Marius
Elev:
Săvuț Daniel-Serafim
Rezolvarea unei probleme poate conduce la obÅ£inerea unui număr foarte mare de soluÅ£ii posibile. Nu întotdeauna ne interesează toate soluÅ£iile, ci numai o parte dintre ele, care îndeplinesc anumite condiÅ£ii. In astfel de cazuri este indicată folosirea metodei Backtracking (BKT).
Problemele care se rezolvă prin metoda BKT generează soluÅ£ii care îndeplinesc anumite condiÅ£ii specifice problemei, denumite condiÅ£ii de validare (condiÅ£ii interne).
SoluÅ£iile posibile care îndeplinesc condiÅ£iile de validare sunt numite soluÅ£ii rezultat (soluÅ£ii finale).
Unele probleme impun obţinerea unei singure soluţii, numită soluţia optimă.
ImaginaÅ£i-vă că astăzi este ziua vostră ÅŸi aveÅ£i invitaÅ£i. AranjaÅ£i o masă frumoasă, apoi vă gândiÅ£i cum să vă aÅŸezaÅ£i invitaÅ£ii la masă. AÅ£i vrea să ÅŸtiÅ£i toate posibilităţile de aÅŸezare a invitaÅ£ilor la masă, dar realizaÅ£i în acelaÅŸi timp că trebuie să Å£ineÅ£i seama ÅŸi de preferinÅ£ele lor. Printre invitaÅ£i există anumite simpatii dar ÅŸi unele antipatii, de care doriÅ£i neapărat să Å£ineÅ£i seama, pentru ca petrecerea să fie o bucurie pentru toÅ£i.
Să ne gândim cum procedaÅ£i pentru a identifica toate posibilităţile de a plasa invitaÅ£ii la masă. ÎncepeÅ£i prin a scrie niÅŸte cartonaÅŸe cu numele invitaÅ£ilor.
AlegeÅ£i un invitat. Pentru a-l alege pe al doilea, selectaÅ£i din mulÅ£imea cartonaÅŸelor rămase un alt invitat. Dacă ÅŸtiÅ£i că cele două persoane nu se agreează, renuntaÅ£i la cartonaÅŸul lui ÅŸi alegeÅ£i altul ÅŸi aÅŸa mai departe. Se poate întâmpla ca la un moment dat, când vreÅ£i să alegeÅ£i cartonaÅŸul unui invitat să constataÅ£i că nici unul dintre invitaÅ£ii rămaÅŸi nu se potriveÅŸte cu ultima persoană slectată până acum. Cum procedaÅ£i? SchimbaÅ£i ultimul invitat plasat cu un invitat dintre cei rămaÅŸi ÅŸi încercaÅ£i din nou, dacă nici aÅŸa nu reuÅŸiti, schimbaÅ£i penultimul invitat cu alcineva ÅŸi încercaÅ£i din nou ÅŸi aÅŸa mai departe până când reuÅŸiÅ£i să plasati toÅ£i invitaÅ£ii. Înseamnă că aÅ£i obÅ£inut o soluÅ£ie. Pentru a obÅ£ine toate celelalte soluÅ£ii, nu vă rămâne decât să o luaÅ£i de la început. AveÅ£i cam mult de muncit, iar dacă numărul invitaÅ£ilor este mare...operaÅ£iunea devine foarte anevoioasă. Iată de ce aveÅ£i nevoie de un calculator ÅŸi cunoÅŸtinÅ£e de programare.
Prezentare generală
Mai 2017
Suceava