Acasa | Trimite referat | Cere referat | Contact

Referat Colorarea unei harti folosind metoda backtracking

Colorarea unei harti folosind metoda backtracking

Categorie: Referate Informatica

Referat downloadat de: 490 ori.

Cauta referat dupa: colorarea unei harti folosind metoda backtracking

Descriere referat:

La dispozi?ia celor care rezolv? probleme cu ajutorul calculatorului exist? 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 aplic? problemelor �n care solu?ia poate fi reprezentat? sub forma unui vector � x = (x1, x2, x3, �xk,� xn) � S, unde S este mul?imea solu?iilor problemei ?i S = S1 x S2 x� x Sn, ?i Si sunt mul?imi finite av�nd s elemente si xi � si , (�)i = 1..n. Pentru fiecare problem? se dau rela?ii �ntre componentele vectorului x, care sunt numite condi?ii interne; solu?iile posibile care satisfac condi?iile interne se numesc solu?ii rezultat. Metoda de generare a tuturor solu?iilor posibile si apoi de determinare a solu?iilor rezultat prin verificarea �ndeplinirii condi?iilor interne necesit? foarte mult timp. Metoda backtracking evit? aceast? generare ?i este mai eficient?. Elementele vectorului x, primesc pe r�nd valori �n ordinea cresc?toare 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 �ndeplinirea unor condi?ii de continuare referitoare la x1�x[k-1]. Daca aceste condi?ii nu sunt �ndeplinite, la pasul k, acest lucru �nseamn? ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o solu?ie rezultat. Metoda backtracking construie?te un vector solu?ie �n mod progresiv �ncep�nd cu prima component? a vectorului ?i merg�nd spre ultima cu eventuale reveniri asupra atribuirilor anterioare. Metoda se aplica astfel : 1) se alege prima valoare sin S1 si I se atribuie lui x1 ; 2) se presupun generate elementele x1�x[k-1], cu valori din S1..S[k-1]; pentru generarea lui x[k] se alege primul element din S[k] disponibil si pentru valoarea aleasa se testeaz? �ndeplinirea condi?iilor de continuare. Pot ap?rea urm?toarele situa?ii : a) x[k] �ndepline?te condi?iile de continuare. Daca s-a ajuns la solu?ia final? (k = n) atunci se afi?eaz? solu?ia ob?inut?. Daca nu s-a ajuns la solu?ia final? se trece la generarea elementului urm?tor � x [k-1]; b) x[k] nu �ndepline?te condi?iile de continuare. Se �ncearc? urm?toarea valoare disponibila din S[k]. Daca nu se g?se?te nici o valoare �n S[k] care s? �ndeplineasc? condi?iile de continuare, se revine la elementul x[k-1] ?i se reia algoritmul pentru o nou? valoare a acestuia. Algoritmul se �ncheie c�nd au fost luate in considerare toate elementele lui S1.

Alte referate din materia: Informatica

Nr.	Nume referat	Hits
1	mtSZPKbW	20
2	TkkvMlabSupl	50
3	qzpymq@dxuzju.com	147
4	email@gmail.com	268
5	pfuqxd@exjswl.com	287
6	ncqcez@hdtnnq.com	244
7	Hard	722
8	ISTORIA INTERNET-ULUI	782
9	Impera	469
10	Info Doc	524
11	Info-TIRON	467
12	Informatica - Grafica pentru web	938
13	Informatica - Introducere in HTML	711
14	Initiere in pc	701
15	Instalarea sistemului de operare Windows	593
16	Internetul ca sursa de comunicare	580
17	Istoria Internetului	617
18	Istoria calculatorului	539
19	Istoria metodelor de proiectare	359
20	Java visavis de C++	401
21	Java vizavi de C	333
22	LIMBAJUL DE PROGRAMARE PASCAL - Programul defineste tipul salariat, o inregistrare cu variante, valorile citite fiind salvate in fisierul salariat.dat	0
23	Limbajul C	413
24	Lista vinuri prg	322
25	Lotus software	293

Acasa Trimite referat Cere referat Adauga la favorite Seteaza ca homepage Contact libertateailuziei Trailere Filme Filme Noi Jocuri Online Jocuri Barbie Jocuri pentru Copii GameBox.ro Make Money Bucuresti regim hotelier