LUCRARE DE DIPLOMA

TEMA LUCRARII:

COLORAREA HARTILOR FOLOSIND METODA BACKTRACKING

Motivul alegerii acestei teme este:

Studierea si aprofundarea rezolvarii problemelor prin metoda backtracking.

CUPRINS:

METODA BACKTRACKING     3

APLICATII REZOLVATE    5

PROBLEMA COLORARII HARTILOR 13

METODA BACKTRACKING

NOTIUNI GENERALE

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 avand 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 rand 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 x1x[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.

Metoda backtracking construieste un vector solutie in mod progresiv incepand cu prima componenta a vectorului si mergand spre ultima cu eventuale reveniri asupra atribuirilor anterioare.

Metoda se aplica astfel :

se alege prima valoare sin S1 si I se atribuie lui x1 ;

se presupun generate elementele x1x[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 testeaza indeplinirea conditiilor de continuare.

Pot aparea urmatoarele situatii :

a)    x[k] indeplineste conditiile de continuare. Daca s-a ajuns la solutia finala (k = n) atunci se afiseaza solutia obtinuta. Daca nu s-a ajuns la solutia finala se trece la generarea elementului urmator x [k-1];

b)    x[k] nu indeplineste conditiile de continuare. Se incearca urmatoarea valoare disponibila din S[k]. Daca nu se gaseste nici o valoare in S[k] care sa indeplineasca conditiile de continuare, se revine la elementul x[k-1] si se reia algoritmul pentru o noua valoare a acestuia. Algoritmul se incheie cand au fost luate in considerare toate elementele lui S1.

Problemele rezolvate prin aceasta metoda necesita timp mare de executie, de aceea este indicat sa se foloseasca metoda numai daca nu avem alt algoritm de rezolvare.

Daca multimile S1,S2,Sn au acelasi numar k de elemente, timpul necesar de executie al algoritmului este k la n. Daca multimile S1, S2.. Sn nu au acelasi numar de elemente, atunci se noteaza cu m minimul cardinalelor multimilor S1Sn si cu M, maximul. Timpul de executie este situat in intervalul [m la n .. M la n]. Metoda backtracking are complexitatea exponentiala, in cele mai multe cazuri fiind ineficienta. Ea insa nu poate fi inlocuita cu alte variante de rezolvare mai rapide in situatia in care se cere determinarea tuturor solutiilor unei probleme.

APLICATII REZOLVATE

Exemple:

Generarea permutarilor. Se citeste un numar natural n. Sa se genereze toate permutarile multimii .

Generarea permutarilor se va face tinand cont ca orice permutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.

Prezentam algoritmul corespunzator cazului n=3:

se incarca in stiva pe nivelul 1 valoarea 1;

incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stivei;

incarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnita;

valoarea 1 din nivelul al 3-lea se regaseste pe nivelul 1;

valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-lea;

valoarea 3 pe nivelul al 3-lea nu e intalnita pe nivelurile anterioare; intrucat nivelul 3 este completat corect. Tiparim: 1 2 3

Algoritmul continua pana cand stiva devine vida.

Problema celor n dame. Fiind data o tabla de sah n n se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (damele sa nu se atace reciproc).

Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4 4, o solutie ar fi urmatoarea:

Cum procedam? Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1 coloana 1.

A doua dama nu poate fi asezata decat pe coloana a 3-a.

Observam ca a treia dama nu poate fi plasata in linia a 3-a. Incercam atunci plasarea celei de-a doua dame in coloana a 4-a.

A treia dama nu poate fi plasata decat pe coloana a 2-a.

In aceasta situatie dama a patra nu mai poate fi asezata. Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana a treia, nici in coloana a patra, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana a doua.

A doua dama nu poate fi asezata decat in coloana a patra.

Dama a treia se aseaza in prima coloana.

Acum este posibil sa plasam a patra dama in coloana a treia si astfel am obtinut o solutie a problemei.

Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.

Pentru prezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama). Exemplu: pentru solutia gasita avem vectorul st ce poate fi asimilat unei stive.

Doua dame se gasesc pe aceeasi diagonala daca si numai daca este indeplinita conditia. |st (i) st (j)| = |i-j| : (diferenta, in modul, intre linii si coloane este aceeasi).

Exemplu: In tabla 4 4 avem situatia:

Sau situatia:

Intrucat doua dame nu se pot gasi pe aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema (ca doua dame sa nu fie plasate in aceeasi diagonala). A proceda astfel, inseamna sa lucra conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea. Fata de programul de generare a tuturor solutiilor problemei celor n dame, are o singura conditie suplimentara, in procedura valid.

Produsul cartezian a n multimi. Se dau multimile de mai jos si se cere produsul cartezian al lor.

A₁ =

A₂ =

A_n =

Exemplu: A₁ =

A₂ =

A₃ =

A₁ A₂ A₃ = .

Pentru rezolvare, se folosesc stiva ST si un vector A ce retine numerele k₁, k_2, k_n. Utilizam metoda backtracking, usor modificata din urmatoarele motive:

a)      Orice element aflat la nivelul k al stivei este valid, motiv pentru care procedura valid nu face altceva decat sa atribuie variabilei ev valoarea TRUE.

b)      Limita superioara pe nivelul k al stivei este data de A(k).

Modul de concepere a algoritmului rezulta din cele ce urmeaza:

Observatii:

Algoritmul prezentat aici este de tip backtracking? Intrebarea are sens pentru ca este absent mecanismul de intoarcere. Vom admite ca si aceasta este backtracking, dar degenerat.

Generarea aranjamentelor. Se citesc n si p. Sa se genereze toate aranjamentele de n luate cate p.

Din analiza problemei rezulta urmatoarele:

stiva are inaltimea p;

fiecare nivel ia valori intre 1 si n;

elementele plasate pe diverse niveluri trebuie sa fie distincte.

Algoritmul este asemanator cu cel de la permutari, cu deosebirea ca aici stipa are inaltimea p.

Generarea combinarilor. Se citesc n si p numere naturale, n p. Se cere sa se genereze toate submultimile cu p elemente ale multimii .

Pentru rezolvarea problemei trebuie tinut cont de urmatoarele:

stiva are inaltimea p;

elementele aflate pe niveluri diferite ale stivei trebuie sa fie distincte;

pentru a evita repetitia elementele se aseaza in ordine crescatoare: pe nivelul k se va afla o valoare mai mare decat pe nivelul k-1 si mai mica sau egala cu n-p+k.

Problema comis-voiajorului. Un comis voiajor trebuie sa viziteze un numar n de orase. Initial, el se afla intr-unul dintre ele, notat 1. Comis voiajorul doreste sa nu treaca de doua ori prin acelasi oras, iar la intoarcere sa revina in orasul 1. Cunoscand legaturile existente intre orase, se cere sa se tipareasca toate drumurile posibile pe care le poate efectua comis voiajorul.

Exemplu: In figura alaturata sunt simbolizate cele 6 orase, precum si drumurile existente intre ele.

Comis voiajorul are urmatoarele posibilitati de parcurgere:

Legaturile existente intre orase sunt date in matricea A_n,n. Elementele matricei A pot fi 0 sau 1 (matricea este binara).

1, daca exista drum intre orasele i si j;

A(i,j) =

0 , altfel

Se observa ca A(i,j) = A(j,i), oricare ar fi i,j I matricea este simetrica.

Pentru rezolvarea problemei folosim stiva st. la baza stivei (nivelul 1) se incarca numarul 1. Prezentam in continuare modul de rezolvare a problemei.

Algoritmul continua in acest mod pana se ajunge din nou la nivelul 1, caz in care algoritmul se incheie.

Un succesor, intre 2 si n, aflat pe nivelul k al stivei, este considerat valid daca sunt indeplinite urmatoarele conditii:

nu s-a mai trecut prin orasul simbolizat de succesor, deci acesta nu se regaseste in stiva;

exista drum intre orasul aflat la nivelul k-1 si cel aflat la nivelul k;

daca succesorul se gaseste la nivelul n, sa existe drum de la el la orasul 1.

Observatii:

Problemele rezolvate prin aceasta metoda necesita un timp indelungat de executie. Din acest motiv este bine sa utilizam metoda atunci numai atunci cand nu mai avem la dispozitie un alt algoritm mai eficient

Mentionam    ca nu exista probleme pentru care nu se cunosc algoritmi eficienti de rezolvare, deci backtracking este indicata.

Rezolvarea iterativa incalca principiul stivei atunci cand verificam conditiile de continuare, sau atunci cand tiparim solutia gasita, pentru ca accesam orice nivel al stivei. Consider ca o structura trebuie folosita ca atare atunci cand este strict necesar. De exemplu, chiar si segmentul de stiva al calculatorului poate fi accesat oriunde. Asta nu inseamna ca acolo nu se utilizeaza din plin mecanismul stivei.

PROBLEMA COLORARII HARTILOR

Enunt:

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.

Rezolvare:

Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre cuprinse intre 1 si 5:

   

O solutie a acestei probleme este urmatoarea:

tara 1 culoarea 1

tara 2 culoarea 2

tara 3 culoarea 1;

tara 4 culoarea 3;

tara 5 culoarea 4;

Harta este furnizata programului cu ajutorul unei matrice A_n,n

1, daca tara i se invecineaza cu tara j;

A(i,j) =

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 [1100] 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.