Metoda backtracking

METODA BACKTRACKING

Tehnica folosita:Metoda Backtracking

Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simulltan urmatoarele conditii:

1 solutia lor poate fi pusa sub forma unui vector S=x1x2, ,xn cu x1 A1,x2 A2, ,xn An;

2 multimile A1,A2, ,An sunt multimi finite,iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

3 nu se dispune de alta metoda de alta metoda de rezolvare mai rapida

Observatii:

1 nu pentru toate problemele n este cunoscut de la inceput;

2 x1,x2, ,xn pot fi la randul lor vectori;

3 in multe probleme,multimile A1,A2, ,An coincid ;

La intalnirea unei astfel de probleme,daca nu cunoastem aceasta tehnica,suntem tentati sa generam toate elementele produsului cartezian A1*A2* *An si fiecare element sa fie testat daca este solutie.

Rezolvand problema in mod,timpul de executie este atat de mare incat poate fi considerat infinit,algoritmul neavand nici o valoare practica.

De exemplu,daca dorim sa generam toate permutarile unei multimi finite A,nu are rost sa generam produsul cartezian A*A* *A,pentru ca apoi,sa testam,pentru fiecare element al acestuia,daca este sau nu permutare(nu are rost sa generam 1,1,1, ,1,pentru ca apoi sa constatam ca nu am obtinut o permutare,cand de la a doua cifra1 ne putem da seama ca cifrele nu sunt distincte).

Tehnica Backtrahing are la baza un principiu extrem de simplu:

1 se construieste solutia pas cu pas:x1,x2, ,xn;

2 daca se constata ca,pentru o valoare aleasa nu avem cum sa ajungem la solutie,se renunta la acea valoare si se reia cautarea din p care am ramas.

Start

K:=1;st[k]:=0;

Se citeste n

NU DA

k>0

Stop

NU Exista DA

K:=k-1 Succesor pe nivelul

K ?

DA Solutia NU

Partiala este

Valida?

NU Este DA

K:=k+1; solutie finala? Tipareste sol.

St[k]:=0;

Figura 1.schema logica a metodei backtracking

ENUNTUL PROBLEMEI :

Se dau n tari si m culori. Sa se afiseze toate posibilitatile de colorare a hartilor,astfel incat doua tari vecine sa nu aiba aceeasi culoare.

SURSA PROGRAMULUI CARE REZOLVA ACEASTA PROBLEMA

Program tari;

type stiva=array[1 10]of integer;

matrice=array[1 10,1 10] of integer

var st:stiva;

a:matrice;

k,n,i,j,m:integer;

as,ev:boolean;

PROCEDURE init(var st:stiva;k:integer);

begin

st[k]:=0;

end;

PROCEDURE succesor(var st:stiva;var as:boolean;k:integer);