Problema Colorarii Hartilor Cu Metoda Backtracking

Previzualizare referat:

Extras din referat:

Fiind data o harta nu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari de frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata.

Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre cuprinse intre 1 si 5: tara 5 culoarea 4; Harta este furnizata programului cu ajutorul unei matrice An, n 0, altfel Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k al stivei simbolizeaza tara k, iar st[k] culoarea atasata tarii k. Stiva are inaltimea n si pe fiecare nivel ia valori intre 1 si 4. Rezolvare PASCAL: Program colorarea hartilor; Type stiva = array [1 100] of integer; var st: stiva; i, j, n, k: integer; as, ev: boolean; a: array [1. 20, 1. 20] of integer; procedure init (k: integer; var st: stiva); begin st[k]: =0; end; procedure succesor (var as: boolean; var st: stiva; k: integer); begin if st[k] < 4 then begin st[k]: =st[k]+1; as: true end else as: false end; procedure valid (var ev: boolean; st: stiva; k: integer); var i: integer; begin ev: true; for i: =1 to k-1 do if (st[i]=st[k]) and (a[i, k]=1) then ev: false end; function solutie (k: integer): integer; begin solutie: = (k=n); end; procedure tipar; var i: integer; begin for i: = 1 to n do writeln (Tara =, i, ; culoarea=, st[i]); writeln; end; begin write (Numarul de tari =); readln (n); for i: = 1 to n do for j: =1 to i-1 do begin write (a[, i, , , j,]=); readln (a[i, j]) end; k: =1; init (k, st); while k>0 do begin repeat succesor (as, st, k); if as then valid (ev, st, k); until (not as) or (as and ev); if as then if solutie (k) then tipar else begin k: =k+1; init (k, st) end else k: =k-1 end end.

...

Download referat

Primești referatul în câteva minute,
cu sau fără cont

Alte informații:
Tipuri fișiere:
doc
Diacritice:
Da
Nota:
8/10 (3 voturi)
Anul redactarii:
2007
Nr fișiere:
1 fisier
Pagini (total):
4 pagini
Imagini extrase:
3 imagini
Nr cuvinte:
359 cuvinte
Nr caractere:
2 175 caractere
Marime:
7.32 KB (arhivat)
Nivel studiu:
Gimnaziu
Tip document:
Referat
Materie:
Informatica
Data publicare:
26.12.2009
Structură de fișiere:
  • Problema Colorarii Hartilor Cu Metoda Backtracking
    • Referat.doc
Predat:
la gimnaziu

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
1. PERMUTARI. Se citeste un numar natural N. Sa se genereze permutarile multimi {1, 2, ..., N};...
In decursul anilor, informatica a fost revolutionata de cateva noi metode de programare. Printre...
Capitolul 1 INTRODUCERE Pentru notiunile din acest paragraf am consultat Behzad, Chartrand,...
Exista multe culegeri de probleme de informatica ce permit invatarea si perfectionarea in...
Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele...
Sus!