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

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

Heliport la Marie Curie pentru copiii bolnavi
Heliport la Marie Curie pentru copiii bolnavi

Spitalului Clinic de Urgenta pentru Copii “M. S. Curie” va fi dotat cu heliport pentru a facilita transportul rapid al copiilor care au nevoie de interventie medicala de urgenta. Lucrarile la constructia heliportului, care va fi amplasat pe acoperisul spitalului, vor incepe in toamna

6 lucruri noi de incercat in vacanta
6 lucruri noi de incercat in vacanta

Mai sunt cateva luni pana la mult asteptata vacanta de vara. Chiar si cand stii ca o sesiune lunga si grea te desparte de zilele insorite de relaxare, nu poti sa nu iti faci macar cateva planuri pentru distractie. De la a-ti incerca norocul intr-o sala de jocuri virtuala si pana la a petrece o

Teste Online

SEBI MODOL

Cât de bine îl cunoşti pe Sebi Modol?

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.