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 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

Top 5 lucruri pentru a te mentine la greutatea ideala
Top 5 lucruri pentru a te mentine la greutatea ideala

Te uiți în oglindă și ai impresia că te rotunjești? Vestea bună, dacă o putem numi așa, este că nu ești o excepție. Conform statisticilor , 21,8% dintre tinerii români cu vârsta între 18 și 24 de ani sunt

Alegerea unui echipament sportiv - trei criterii esentiale
Alegerea unui echipament sportiv - trei criterii esentiale

Indiferent de forma de miscare aleasa, cu siguranta te-ai gandit cel putin o data ce tip de echipament sportiv trebuie sa iti alegi. Mai jos îți spunem care sunt cele mai importante criterii pe care trebuie sa le respecti atunci cand urmeaza sa iti cumperi un echipament pentru sport.

Despre Sarbatorile legale in 2019

Ca in fiecare an, si in 2019 romanii asteapta cu nerabdare sa afle de ce zile libere vor putea profita pentru o vacanta sau o escapada in afara agitatiei zilnice, weekendul fiind de multe ori mult prea scurt pentru asa ceva. Se pare insa ca acest an va fi mai putin darnic cu cei care lucreaza

Iubesti pisicile? Iata unde-ti poti petrece vacanta pentru a te bucura de compania lor
Iubesti pisicile? Iata unde-ti poti petrece vacanta pentru a te bucura de compania lor

Iti doresti o vacanta atfel? In care sa te relaxezi si sa uiti complet de examenele si lucrarile pe care trebuie sa le predai la termen? Dar vrei sa te bucuri in acelasi timp de compania animalelor tale preferate? Avem solutia perfecta pentru tine: destinatiile de vacanta perfecte pentru iubitorii

Teste Online

Cu ce zodie esti compatibila?

Stelele vor sa descoperi partenerul ideal. Afla ce spun despre iubitul tau!

mai multe »
Link-uri recomandate: design interior | nikydecor.ro | designer interior cluj | mobilier dormitor preturi | modern interior design
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.