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

Black Friday cu preturi microscopice la produsele de la GSMnet
Black Friday cu preturi microscopice la produsele de la GSMnet

Ziua de Black Friday aduce numeroase avantaje pentru pasionatii de tehnologie. In prezent, pretentiile ce fac referire la ultimele gadget-uri tehnologice sunt destul de mari. Utilizatorii sunt foarte bine documentati cu privire la specificatiile smartphone-urilor, dar și în ceea ce

Despre mecanici auto si ateliere de reparatii
Despre mecanici auto si ateliere de reparatii

Sunt foarte puțini mecanici auto de încredere pe piață. Sunt foarte puțini mecanici auto în general, care sunt bombardați de o mulțime de clienți cu lucrări de reparații din care toți își doresc să fie ei o prioritate,

Gadgeturile studentului modern
Gadgeturile studentului modern

Cat de mult s-a schimbat viata intr-un campus in ultimii 20-25 de ani? Cel mai probabil, nu foarte mult la capitolul distractie, interactiuni sociale si provocari pe linie materiala, dar cu siguranta sunt schimbari radicale in ceea ce priveste modul in care tehnologia isi face simtita prezenta in

Cum sa ajuti copilul sa invete cu placere - Trucuri eficiente
Cum sa ajuti copilul sa invete cu placere - Trucuri eficiente

Fiecare parinte se loveste de aceasta problema: cum sa imi ajut copilul sa invete mai bine, cum sa il determin sa ia note bune la scoala si cum sa il fac sa inteleaga ca educatia este cea mai importanta pentru el. In primul rand, trebuie sa stii ca este foarte important ca tu, ca parinte, sa te

Ce este o pergola
Ce este o pergola

Zilele cu prea mult soare pot fi un adevărat chin dacă nu încercăm să ne protejăm corpul de razele ultraviolete. In ajutorul nostru sar pergolele, care reprezintă de mult timp un centru de greutate in arhitectura grădinilor. Pergolele sunt structuri

Teste Online

TEST DE EVALUARE LA BIOLOGIE - Sistemul digestiv nr 4

TEST DE EVALUARE LA BIOLOGIE - Sistemul digestiv nr 4

mai multe »
Acest site foloseste Cookie-uri.
Folosim cookie-uri pentru a personaliza continutul si reclamele, pentru a oferi caracteristici specifice retelelor sociale si pentru a analiza traficul nostru. De asemenea, impartasim informatii despre felul in care ne utilizati site-ul, cu partenerii nostri de pe retelele sociale, de publicitate si de statistica in conformitate cu Politica de confidentialitate. Va puteti administra preferintele in Setari cookie.