clasa XI-B, Tema: Metoda reluarii (backtracking). 04.05-08.05

 Metoda reluării (Backtracking)

Vizionati prezentarea la metoda reluarii (backtracking)

  Metoda reluării se utilizează la rezolvarea problemelor, care oferă mai multe soluţii. Fiecare soluţie se memorează într-o structură de date de tip stivă, implementată cu ajutorul unui vector. Într-un algoritm backtracking ne interesează toate soluţiile posibile. Pentru a obţine fiecare soluţie finală, vom completa vectorul-stivă pas cu pas, nivel cu nivel, trecînd astfel prin nuişte soluţii parţiale. În plus, atît soluţiile parţiuale, cît şi cele finale, pentru afi luate în consideraţie, trebuie să îndeplinească anumite condiţii de validare. O soluţie, care îndeplineşte aceste condiţii, devine soluţie validă.

Toate configuraţiile stivei, ce reprezintă soluţii finale, sunt alcătuite din elementele unei mulţimi bine definite, numită mulţimea soluţiilor posibile.

Fiecare soluţie nouă parţială se obţine prin completarea soluţiei parţiale precedente cu încă un nivel în stivă. La fiecare nivel  vom încerca să punem pe nivelul respectiv valori din mulţimea soluţiilor posibile neîncercate încă, pînă cînd obţinem o soluţie validă. În acest moment urcăm cu încă un nivel în stivă, pentru a completa mai departe soluţia, după care reluăm încercările pe noul nivel.

Va apărea însă şi următoarea situaţie: la un moment dat, pe un anumit nivel, nu mai există nici o valoare neîncercată din mulţimea soluţiilor. În acest caz vom face un pas înapoi, la nivelul anterior, şi reluăm căutarea cu valorile rămase neîncercate pe acest nivel anterior. Respectivul nivel a mai fost vizitat, dar l-am abandonat după ce am pus o valoare care a generat o soluţie validă, deci se poate să fi rămas aici valori neîncercate. Dacă nici pe acest nivel nu mai avem valori neîncercate, mai facem un pas înapoi ş.a.m.d. mecanismul revenirilor a determinat denumirea metodei.

1. Combinări de n elemente luate cîte k.

     Fiind date două numere naturale n şi k, să se genereze toate combinările de n elemente luate cîte k.

Algoritmul: Considerăm mulţimea {1, 2,…,n}. Aranjamentele de n elemente luate cîte k reprezintă seturile alcătuite cu cîte k elemente distincte din mulţimea dată, luate în diverse ordini. O parte din aceste aranjamente conţin aceleaşi elemente luate în alte ordini. Luînd numai cîte unul din seturle cu aceleşi elemente, obţinem combinările de n elemente luate cîte k. Fiecare soluţie va fi o configuraţie a stivei St[1], St[2],…,St[k], alcătuită din k elemente distincte ale mulţimii {1, 2,…,n}. O soluţie pe careva nivel p este validă, dacă ea nu se conţine pe nivelele anterioare. Dar pentru a nu lua drept soluţii două seturi cu aceleaşi elemente în ordini diferite, vom pune condiţia ca elementele unei soluţii să fie în ordine crescătoare.

Programul în limbajul Pascal:

Program Combinari; Uses CRT;  Type Lin=Array[1..20] Of Byte;

Var N,K:Byte;    St:Lin;    F:Text;

Procedure Citire; Var I:Byte;

Begin  Assign(F,'IN.TXT');Reset(F);  ReadLn(F,N,K);

  For I:=1  To K Do   St[I]:=0;  Close(F) End;

Procedure Tipar(P:Byte); Var I:Byte;

Begin  For I:=1 To P Do      Write(F,St[I],' ');      WriteLn(F)  End;

Function V(P:Byte):Boolean; Var Q:Boolean;    I:Byte;

Begin        Q:=True; I:=1;

  While Q And (I<P) Do

  If St[I]<St[P] Then Inc(I)  Else Q:=False;   V:=Q  End;

Procedure BkTr(P:Byte); Var Val:Byte;

Begin  For Val:=1 To N Do

      Begin      St[P]:=Val;

      If V(P) Then If P=K Then Tipar(P)  Else BkTr(P+1)      End  End;

Begin         Citire;  Assign(F,'out.txt');Rewrite(F);         BkTr(1);  Close(F) End.

2. Problema comis-voiajorului.

Se consideră n oraşe numerotate 1, 2, ...,n. Un comis-voiajor trebuie să-şi prezinte produsele în toate cele n oraşe, plecînd dintr-un oraş de start, trecînd prin fiecare oraş exact o singură dată şi revenind în oraşul din care a plecat. Ştiind că între unele dintre oraşe există drumuri directe, iar între altele nu, să se afişeze toate traseele pe care le poate urma comis-voiajorul.

Algoritmul: Oraşele sunt numerotate 1, 2,...,n. Notăm St- vectorul stivă, ce va conţine soluţia, Start – oraşul de plecare. Memorăm legătuile directe dintre oraşe în matricea A, unde un element A[I,J] va fi>

1, dacă există drum direct între oraşele I şi J;

0, în caz contrar.

Pe primul nivel al stivei vom pune oraşul de plecare Start. Fiecare soluţie finală reprezintă un traseu al comis-voiajorului şi conţine toate oraşele, fiecare oraş fiind luat o singură dată. O soluţie pe careva nivel p este validă, dacă ea nu se conţine pe nivelele anterioare şi dacă între oraşul de pe nivelul p-1 şi cel de pe nivelul p există drum direct.  Soluţia finală trebuie să respecte următarele condiţii de validare:

1) să conţină n oraşe,

2) între oraşul de pe nivelul n şi oraşul start să existe drum direct.

Programul în limbajul Pascal.

Program Problema_comis_voiajor; Uses CRT;

Type T=Array[1..10,1..10] Of 0..1;     Lin=Array[1..30] Of Integer;

Var A:T; (* matricea conexiunilor dintre orase *)    St:Lin;  (* vectorul solutiei *)

    F:Text; Nume_iesire:String[12];    N,Ostart:Byte;

Procedure Citire;  Var I,J:Byte;    Nume_intrare:String[12];

Begin  Write('Numele fisierului de intrare:');ReadLn(Nume_intrare);

Assign(F,Nume_intrare);Reset(F);    ReadLn(F,N, Ostart);

For I:=1 To N Do    Begin

  For J:=1 To N Do      Read(F,A[I,J]);    ReadLn(F)    End;

    Close(F);          St[1]:=Ostart  End;

Procedure Tipar; Var I:Byte;

Begin  Write(F,'( ');  For I:=1 To N Do      Write(F,St[I],' ');      WriteLn(F,')')  End;

Function Valid(L:Byte):Boolean; Var I:Byte;    V:Boolean;

Begin        I:=1; V:=True;

  While V And (I<L) Do   If St[I]=St[L] Then V:=False                 Else Inc(I);

     Valid:=V And (A[St[L],St[L-1]]=1)  End;

Procedure BkTr(L:Byte);Var Val:Byte;

Begin  For Val:=1 To N Do      Begin      St[L]:=Val;

      If Valid(L) Then If L=N Then Begin   If A[Ostart,N]=1 Then Tipar    End      Else BkTr(L+1)

      End  End;

Begin  Citire;  Write('Numele fisierului de iesire:');ReadLn(Nume_iesire);

    Assign(F,Nume_iesire); Rewrite(F);  BkTr(2);    Close(F) End.

Sarcini pentru rezolvare:
1. de studiat paragraful 5.4, pagina 126
2. de rezolvat prob. 6, pagina 132, prob. 12, pagina 124