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

Finette - pentru un somn odihnitor
Finette - pentru un somn odihnitor

Unul dintre cele mai importante aspecte care duc la o viata activa, este calitatea somnului. Acest moment este destul de neglijat, mai ales in perioada tineretii. Orele de somn sunt din ce in ce mai scurte din cauza petrecerilor si a volumului mare de proiecte de realizat. Anii de adolescenta vin

Stailer - programari la salon in orice zi
Stailer - programari la salon in orice zi

Vizitele la saloanele de înfrumusețare sunt destul de rare pentru unele persoane din cauza timpului și totuși, atunci când se decid să meargă nu pot găsi un loc liber. Tot acest proces de a te programa la salon necesită mult prea mult timp și

Afla cand trecem la ora de vara in 2021!
Afla cand trecem la ora de vara in 2021!

Ora de vară presupune un ceas în minus de somn, motivul pentru care majoritatea dintre noi nu suntem mari fani ai modificării. Dar argumentele pentru această schimbare sezonieră țin de economie și nu mai au aceeași relevanță în societatea

5 Motive pentru care sa faci cadou iubitei tale o geanta Alluxuri
5 Motive pentru care sa faci cadou iubitei tale o geanta Alluxuri

Valentine's Day, Dragobete, 1 Martie, Ziua Femeii sau ziua ei de nastere, cu alte cuvinte, suficiente ocazii în care să-ți surprinzi iubita cu un dar original, prin care să-ți exprimi dragostea și afecțiunea pe care i le porți. Ca idee de cadou pentru astfel

Cel mai eficient mod de a scapa de firele crescute sub piele
Cel mai eficient mod de a scapa de firele crescute sub piele

Picioarele catifelate și netede sunt visul oricărei fete și femei, dar de la fantezie la realitate este cale lungă. Nesuferitele fire crescute sub piele , fenomen care poartă numele de foliculită sau Pili recurvati. Află de mai jos de ce te confrunți

Teste Online

Lucrare scrisa semestriala - Istoria Romanilor

Lucrare scrisa semestriala - Istoria Romanilor

mai multe »

Calculator Sarcina