Colorarea unei harti folosind metoda backtracking

Publicat: 24 Mar 2015 00:00

La dispozitia celor care rezolva probleme cu ajutorul calculatorului exista mai multe metode. Dintre acestea cel mai des utilizate sunt:

  • metoda Greedy;
  • metoda Divide et impera;
  • metoda Branch and Bound;
  • metoda Backtracking;


Metoda Backtracking se aplica problemelor in care solutia poate fi reprezentata sub forma unui vector – x = (x1, x2, x3, …xk,… xn) € S, unde S este multimea solutiilor problemei si S = S1 x S2 x… x Sn, si Si sunt multimi finite având s elemente si xi € si, (¥)i = 1..n.

Pentru fiecare problema se dau relatii intre componentele vectorului x, care sunt numite conditii interne; solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Metoda de generare a tuturor solutiilor posibile si apoi de determinare a solutiilor rezultat prin verificarea indeplinirii conditiilor interne necesita foarte mult timp.

Metoda backtracking evita aceasta generare si este mai eficienta. Elementele vectorului x, primesc pe rând valori in ordinea crescatoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica indeplinirea unor conditii de continuare referitoare la x1…x[k-1]. Daca aceste conditii nu sunt indeplinite, la pasul k, acest lucru inseamna ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o solutie rezultat.

Trebuie sa citesti

Ce sa-ti cumperi de la reduceri din bugetul de student
Ce sa-ti cumperi de la reduceri din bugetul de student

Atunci cand ai la dispozitie un buget de student, in mare parte constituit din banii primiti de la parinti si, poate, un salariu dintr-o slujba part-time, trebuie sa te gandesti cu atentie ce vrei sa cumperi si mai ales cand vrei sa cumperi. Campaniile de reduceri de pret din timpul iernii iti

Credite accesibile studentilor
Credite accesibile studentilor

Perioada studenției este una dintre cele mai frumoase în viața unui om. Este o perioadă plină de experiențe noi, de însușire de informații și noi abilități. Cu toate acestea, poate fi și o perioadă dificilă, în special

De ce nu este bine sa pregateasca parintii gustarea pentru scoala
De ce nu este bine sa pregateasca parintii gustarea pentru scoala

Una dintre cele mai vechi amintiri ne duce departe înapoi pe firul timpului, în copilărie, când un prichindel cu ochii cârpiți de somn primea de la mama pachețelul cu mâncarea de la grădiniță și apoi de la școală. Dorind să

Ce ar trebui sa ia in considerare studentii atunci cand inchiriaza o locuinta
Ce ar trebui sa ia in considerare studentii atunci cand inchiriaza o locuinta

Cand esti student in alt oras fata de cel natal, inchirierea unei locuinte confortabile la un pret rezonabil este un aspect foarte important. Totusi, din dorinta de a face economii sau de a rezolva aceasta chestiune cat mai rapid, multi tineri ajung sa se confrunte cu diferite situatii relativ

Unde sa iti petreci vacanta in aceasta iarna? Iata cele mai frumoase destinatii la munte
Unde sa iti petreci vacanta in aceasta iarna? Iata cele mai frumoase destinatii la munte

O vacanță la munte nu reprezintă doar o binemeritată doză de aer curat, de pace și de liniște, dar și o ocazie de a te bucura cu gașca sau cu familia de peisaje spectaculoase, aventură și neprevăzut. Iar vacanțele de iarnă de la

Teste Online

Varianta 018 informatica

Varianta 018 informatica intensiv

mai multe »

Calculator Sarcina