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

Lucretia Titirca - personalitatea care a ridicat prestigiul meseriei de asistent medical
Lucretia Titirca - personalitatea care a ridicat prestigiul meseriei de asistent medical

Un nume cunoscut atât pe plan național, cât și internațional, este al doamnei Lucreția Titircă, o personalitate importantă care a ridicat prestigiul meseriei de asistent medical, câștigând numeroase diplome, insigne, cât și titlul de

In fruntea lantului trofic urban: Brain Boost
In fruntea lantului trofic urban: Brain Boost

Un nou studiu publicat de catre Simon Fraser University, Canada, a descoperit ca odata ce am trecut de varsta de 24 de ani, timpul nostru de reactie scade, relateaza softpedia.com. Studiul a sugerat ca factorii precum dexteritatea mainilor (incheieturi, degete) si presiunea sociala sau culturala

Top 7 bloguri de contabilitate pe care ar trebui sa le citesti
Top 7 bloguri de contabilitate pe care ar trebui sa le citesti

Chiar daca esti student, lucrezi deja in domeniu sau pur si simplu te pasioneaza contabilitatea digitala , pentru a creste si a deveni un profesionist contabil de exceptie, trebuie sa inveti si sa iti dezvolti abilitatile in mod continuu. Cercetarile sustin faptul ca 77% dintre utilizatorii de

Cum reuseste McDonald`s sa vanda eficient?
Cum reuseste McDonald`s sa vanda eficient?

McDonald’s serveste 68 de milioane de clienti zilnic, asa ca sistemul lor de vanzare a trebuit sa fie instalat in toate cele 37.000 de restaurante din intreaga lume si a fost, cu siguranta, o decizie foarte importanta. Te-ai intrebat vreodata ce fel de sistem foloseste McDonald's pentru a se

15 lucruri interesante despre lumea modei
15 lucruri interesante despre lumea modei

De-a lungul timpului au aparut diferite stiluri de moda, iar multe dintre ele revin in magazinele noastre preferate odata la cativa ani. Unii oameni adora si fac tot posiblilul sa tina pasul cu tendintele recente, in timp ce altii nu acorda foarte mare importanta celor mai noi stiluri. Indiferent

Teste Online

Esti pregatit pentru testul de cultura de clasa a 4-a ?

Aici iti vei imbunatati cunostintele despre cultura generala! Vei invata multe lucruri importante, care te vor ajuta mai tarziu ! BAFTA!

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.