studentie.ro  » universitar » lucrari de diploma » Colorarea unei harti folosind metoda backtracking

Colorarea unei harti folosind metoda backtracking

Publicat: 24 Mar 2015 | Vizualizari: 1022

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.

 
 

Quiz

În acest ”Test” este vorba cât de bine poți gândi. Deoarece unii greșesc la cele mai simple întrebări.Acesta este un așa numit „Test de Logică”.

 
 

Jobs

Firma: Studio20
Nivel cariera: 1 - 2 ani
Tipul postului: Full-time
Oras: BUCURESTI, Cluj Napoca, Iasi, Pitesti, Ploiesti
Perioada de valabilitate: 2021-10-20 00:00:00 - 2021-11-10 00:00:00