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

Cum sa castigi bani si experienta pe piata muncii in timpul studentiei
Cum sa castigi bani si experienta pe piata muncii in timpul studentiei

Sa lucrezi cu jumatate de norma in timp ce esti student este o modalitate excelenta de a capata experienta, de a cunoaste oameni care, ulterior, te pot ajuta in cariera si, mai presus de toate, de a castiga bani pentru a-ti satisface nevoile. In timpul facultatii, cursurile sunt prioritare, de

Ce poti sa faci pentru a incepe sa fii pe banii tai ca student
Ce poti sa faci pentru a incepe sa fii pe banii tai ca student

Daca esti student, cel mai probabil din toamna vei incepe cursurile fata in fata sau cel putin seminarele si laboratoarele, o buna ocazie de a interactiona mai mult cu colegii, de a-ti crea legaturi si de a schimba cunostinte si experiente. Totodata, odata cu reluarea acestor conexiuni sociale cu

E ziua colegului si nu stii ce cadou sa-i oferi? Giftexpress iti propune cateva idei geniale
E ziua colegului si nu stii ce cadou sa-i oferi? Giftexpress iti propune cateva idei geniale

Cand esti student, viata inseamna 70 la suta distractie si 30 la suta invatat. Oricat te-ai stradui in primul an al studentiei sa fii cu capul pe umeri, sa te autoconvingi ca tu nu mergi la chefuri, ca vei fi cuminte, responsabil si mananci cartea pe paine ca zacusca de la mama, inevitabil te corup

Trucuri geniale ca sa inveti mai usor si mai repede
Trucuri geniale ca sa inveti mai usor si mai repede

Toata lumea stie ca unii invata mai usor, in timp ce pentru altii acumularea materiei este mai dificila. In cazul celor dintai poate sa fie vorba despre unele abilitati naturale, dar ar putea fi la mijloc si o strategie mai buna care sa-i faca eficienti. In consecinta, poate fi util sa iei in

Nu rata ofertele de bilete avion in Zakynthos! E sansa ta sa pleci in vacanta!
Nu rata ofertele de bilete avion in Zakynthos! E sansa ta sa pleci in vacanta!

Peisaje de munte, golfuri ascunse si mult, mult soare! Bine ai venit in Zakynthos! Cei care iubesc marea si razele blande ale soarelui cu siguranta vor fi incantati de aceasta destinatie. Un motiv in plus pentru a-ti achizitiona din timp bilete avion Zakynthos , o mica insula din Marea Ionica,

Teste Online

Sti ce inseamna logica?

Este simplu,usor, toata lumea il poate face!

mai multe »