informatica - Metoda Backtracking. Problema comis-voiajorului

 

Metoda Backtracking.

Problema

comis-voiajorului

Argument

Din cand in cand suntem pusi in situatia de a gasi o solutie optima la o problema, cu toate ca nu exista nici o teorie aplicabila pentru rezolvarea acesteia, cu exceptia verificarii tuturor solutiilor. Acest tip de probleme care necesita generarea tuturor solutiilor si, eventual, alegerea unei solutii optime se rezolva cu ajutorul metodei backtracking.

Notiuni teoretice

Se foloseste in rezolvarea problemei care indeplinesc urmatoarele conditii:

1. Solutia lor poate fi pusa sub forma unui vector S=(x₁, x₂,.x_n) cu x_i A_i
2. Multimile A_i , i=1,n sunt finite iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita
3. Nu se dispune de o alta metoda de rezolvare mai rapida

Pentru o astfel de problema suntem tentati sa generam toate elementele produsului cartezian A₁ xA₂x A₃x.xA_n. si fiecare element sa fie testat daca este solutie. Timpul este foarte mare. Tehnica Backtracking evita aceasta construind solutia pas cu pas:

1. Se alege primul element x₁A₁
2. Presupune generate elementele (x₁, x₂,.x_n )(A₁xA₂x A₃x.xA_n.). Se alege X_k+1 primul element disponibil din A_k+1. Exista doua situatii:
• Nu s-a gasit un astfel de element si se reia cautarea considerand generate X₁ pana la     X_k+1
• A fost gasit, caz in care se testeaza daca indeplineste anumite conditii de continuare:

a) S-a ajuns la solutie, se tipareste, si se reia algoritmul considerandu-se generate elementele (x₁, x₂,.x_k) ,(se cauta X_k+1, netestat)

b) Nu le indeplineste, se reia algoritmul considerandu-se generate (x₁, x₂,.x_n) si se cauta alt element X_k+1 A_k+1 netestat.

Algoritmul se incheie cand nu mai exista nici un element X₁A₁ netestat.

Tehnica are ca rezultat obtinerea tuturor solutiilor problemei. Se poate si forta oprirea dupa gasirea unei solutii.

Generarea solutiilor se face intr-o stiva "st".

Folosim procedurile si functiile:

• INIT(k,st)-pentru initializarea cu o valoare a nivelului k al stivei
• SUCCESOR(as, k,st)-pentru gasirea urmatorului element netestat al multimii A_k . Parametrul as este variabila booleana(am succesor sau nu)
• VALID(ev,k,st)-testarea elementului de pe nivelul k al stivei
• SOLUTIE(k)- functia    testeaza daca s-a ajuns la solutia finala
• TIPAR-procedura de tiparire a solutiei

Aplicatii:

1. Generarea permutarilor multimii
2. Fiind data o tabla de sah de nxn se cer toate solutiile de aranjare a n dame astfel incat ele sa nu se atace
3. Idem pentru cai
4. Generarea tuturor modurilor de descompunere a unui numar natural n ca suma de numere naturale

Rutina iterativa backtracking;

k

init(1,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;

Backtracking recursiv;

Observatii:

1. SUCCESOR=functie booleana(dispare as)
2. RUTINA BACKTRACKING se transforma in procedura apelata prin BACK(1)

Principiul de functionare:

• In situatia in care avem o solutie, o tiparim si revin la nivelul anterior
• In caz contrar se initializeaza nivelul si se cauta un successor
• Cand am gasit unul, verificam daca este valid ; procedura se autoapeleaza pentru k+1 ; in caz contrar se continua cautarea succesorului ;
• Daca nu avem succesor se trece pe nivelul inferior(k+1) prin iesirea din procedura back

Procedure back(k:integer);

Begin

if solutie (k) then TIPAR

else begin

init(k,st)s

while successor(st,k) do

begin

valid(ev,st,k)s

if ev then back(k+1)

end;

end;

Descrierea programului

Un comis-voiajor trebuie sa viziteze un numar de n orase. Initial acesta se afla in primul oras. Comis-voiajorul nu doreste sa viziteze acelasi oras de doua ori, iar la intoarcere trebuie sa revina in primul oras.

Cunoscand legaturile directe existente intre orase si distantele dintre acestea, sa se gaseasca drumul de lungime minima pe care trebuie sa il parcurga comis-voiajorul.

Legaturile directe intre orase vor fi pastrate in matricea distanta astfel:

distanta[i,j]= 0, daca nu exista o legatura directa intre orasul

i si orasul j

k>0, daca exista legatura directa de lungime k, intre orasul i si orasul j

In rezolvare s-au folosit procedurile descrise in capitolul anterior .

var sol, optim:array[1..100] of integer;

distanta:array[1..100,1..100]of integer;

n,dist,min:integer;

exista_solutie:boolean;

i,j,m,01,02,lung:integer;

procedure solutie;

var k:dist;

begin

dist:=0;

for k:=1 to n do

dist:=dist+distanta[sol[k],sol[k+1]];

if not exista_solutie or (dist<dist min) then

begin

exista_solutie:=true;

dist min:=dist;

for k:=1 to n+1 do

optim[k]:=sol[k];

end;

end;

function continuare(i:integer):boolean;

var k:integer;

begin

if ((i=1) and (sol[1]<>1)) or ((i=n+1) and (sol[n+1]<>1)) or

((i>1) and (distanta [sol[i-1], sol[i]]=0)) then begin

continuare:=false;

exist;

end;

if (i=n+1)then begin

continuare:=true;

exist;

end;

k:=i-1;

while(k>=0) and (sol[i]<> sol[k]) do dec(k);

continuare:=not(k>=0);

end;

procedure backtracking_recursiv;

var k:integer;

begin

if i=n+2 then

solutie

else begin

for k:=1 to n do begin

sol[i]:=k;

if continuare(i) then

backtracking_recursiv(i+1);

end;end;

end;

procedure backtracking_nerecursiv;

var i:integer;

begin

for i:=1 to n+1 do

sol[i]:=0;

i:=1;

while(i>0) do begin

if (i=n+2) then begin

solutie;

dec(i);

end else begin

inc(sol[i]);

if (sol[i]>n) then begin

sol[i]:=0;

dec(i);

end else begin

if continuare(i) then

inc(i);

end;

end;

end;

procedure afiseaza_solutie;

var k:integer;

begin

if not exista_solutie then

writeln('Nu exista solutie!')

else begin

for k:=1 to n+1 do

write(optim[k],' ')

writeln('lungime:',dist min);

end;

end;

begin

write('Numarul de orase:');

readln(n);

write('Numarul de drumuri:');

readln(m);

for i:=1 to n do

for j:=1 to n do

distanta[i,j]:=0;

for i:=1 to m do

begin

write('oras1 oras2 lungime:');

readln(01,02,lung);

distanta(01,02):p=lung;

distanta(02,01):=lung;

end;

exista_solutie:=false;

writeln('Backtracking recursiv:');

backtracking_recursiv(1);

afiseaza_solutie;

exista_solutie:=false;

writeln('Backtracking nerecursiv:');

backtracking_nerecursiv;

afiseaza_solutie;

end.

Bibliografie

"Informatica- manual pentru clasa a X-a", Tudor Sorin, Editura Teora, Bucuresti, 2000

"Algoritmi logica si programare ", Ioan Tutunea, Leprografia universittatii din Craiova, Craiova, 1993