Metode evoluate de programare Limbajele c şi C++

14.3. Metoda backtracking (căutare cu revenire)

Această metodă se aplică problemelor ce pot fi reprezentate sub forma unui arbore finit iar căutarea soluţiei presupune parcurgerea arborelui în adâncime (DF=Depth First).

Problemele de acest tip au în general soluţia de forma x=(x₁, . . . ,x_n)  S₁x . . . xS_n, fiecare S_k fiind o mulţime finită. Mai facem câteva precizări preliminare:

a) pentru fiecare problemă sunt date anumite relaţii între componentele x₁, . . . ,x_n ale lui

x numite condiţii interne;

b) produsul cartezian S=S₁x...xS_n se mai numeşte spaţiul soluţiilor posibile, iar soluţiile

posibile care satisfac condiţiile interne se numesc soluţii rezultat;

c) în general se cer două lucruri în astfel de probleme:

- determinarea tuturor soluţiilor rezultat;

- determinarea doar a acelor soluţii care optimizează o funcţie obiectiv dată.

Cum rezolvăm astfel de probleme? Există două modalităţi de rezolvare:

1) tehnica directă (numită şi tehnica forţei brute) prin care se generează toate elementele spaţiului de soluţii posibile şi apoi se verifică fiecare dacă este sau nu o soluţie rezultat; această tehnică necesită un timp prohibitiv (dacă fiecare S_i are doar 2 componente complexitatea este O(2ⁿ); totodată ar fi necesară imbricarea a n cicluri cu n aprioric necunoscut).

2) backtracking care evită generarea tuturor soluţiilor posibile.

Să dăm în continuare câteva repere ale rezolvării:

1. 
   soluţia este construită progresiv, componentă cu componentă;
   
2. 
   lui x_k i se atribuie o valoare (evident că numai din S_k) dacă şi numai dacă x₁, . . . ,x_k-1 au deja valori;
   
3. 
   se verifică condiţiile de continuare (strâns legate de condiţiile interne) dacă are sens trecerea la x_k+1;
   

1. 
   dacă nu are sens (adică condiţiile de continuare nu sunt îndeplinite atunci facem o nouă alegere pentru x_k sau dacă am epuizat valorile din S_k atunci k:=k-1 şi se face o nouă alegere pentru x_k-1; ş.a.m.d.
   

2. dacă are sens atunci k:=k+1 şi se testează dacă k>n:

2₁) dacă inegalitatea este adevărată atunci se afişează soluţia astfel determinată

şi k:=k-1 continuând procesul de la punctul 1;

2₂) dacă inegalitatea este falsă se continuă procesul de la punctul 1.

Procedura rezolvării unor astfel de probleme este:

procedure BT(n,x)

integer n;

array x(n);

k:=1;

while k>0 do

cod:=0;

while ([mai exist o valoare α din S_k netestat] and cod=0)

x(k):=α;

if _k(x(1),...,x(k)) then cod:=1;

endif;

endwhile;

if cod=0 then

k:=k-1

else

if k=n then write (x(1),...,x(n))

else k:=k+1

endif

endif;

endwhile;

return;

end procedure

Vom face câteva precizări:

1^o. Predicatul _k(x₁, . . . , x_k) reprezintă condiţiile de continuare pentru x₁, . . . , x_k;

2^o. Cod este o valoare ce indică îndeplinirea/neîndeplinirea condiţiilor de continuare;

3^o. Dacă predicatul _k(x₁, . . . , x_k) este adevărat  k  {1,...,n} atunci se vor afla toţi vectorii din S;

4^o. Backtracking poate fi uşor reprezentat pe un arbore construit astfel:

- nivelul 1 conţine rădăcina;

- din orice nod de pe nivelul k pleacă s_k muchii spre nivelul k+1, etichetate cu cele

s_k elemente ale lui S_k;

- nivelul n+1 va conţine s₁*s₂*. . .* s_n noduri frunză;

- pentru fiecare nod de pe nivelul n+1 etichetele muchiilor conţinute în drumul ce

leagă rădăcina de acest nod reprezintă o soluţie posibilă;
Dacă mulţimile S_k reprezintă progresii aritmetice atunci algoritmul general se modifică astfel:
procedure BTA(n,a,b,h)

integer n;

array primul(n),ultimul(n),ratia(n),x(n);

k:=1;

x(1):=primul(1)-ratia(1);

while k>0 do

cod:=0;

while ( x(k)+ratia(k)  ultimul(k) and cod=0 )

x(k):=x(k)+ratia(k);

if _k(x(1),...,x(k)) then cod:=1 endif;

endwhile;

if cod=0 then

k:=k-1

else

if k=n then write (x(1),...,x(n))

else k:=k+1

x(k):=a(k)-h(k)

endif

endif;

endwhile;

return;

end procedure

unde:

- primul(n) reprezintă vectorul primilor termeni ai progresiilor aritmetice;

- ultimul(n) reprezintă vectorul ultimilor termeni ai progresiilor aritmetice;

- ratia(n) reprezintă vectorul raţiilor progresiilor aritmetice;

De reţinut cele două avantaje ale acestui procedeu:

1. 
   evitarea imbricării unui număr oarecare de cicluri aprioric variabil (în algoritmul propus se imbrică doar două cicluri pretestate while);
   
2. 
   evitarea construirii spaţiului tuturor soluţiilor posibile S₁xS₂x . . . xS_n.
   

Problemă rezolvată
În câte moduri se pot aranja 8 dame pe tabla de şah astfel încât să nu se "bată" reciproc. Să se folosească al doilea algoritm dintre cei menţionaţi anterior.
Prima variantă
Acest program respectă algoritmul anterior cu unele mici modificări. Facem precizarea că vectorul x conţine în componenta x[i] numărul coloanei de pe tabla de şah pe care se va afla dama de pe linia i. Tipărirea va reprezenta o permutare (din cele 8! soluţii posibile). Se vor afla 92 de soluţii. Lăsăm pe seama cititorului să deducă analogiile şi diferenţele între algoritm şi program.
#include

#include

void main (void)

{ int x[9],cod,k,i,nr;

k=1; x[1]=0;nr=0;

while (k>0)

{ cod=0;

while (((x[k]+1)<=8)&&(cod= =0))

{ x[k]++;

if ((k= =1) && (x[k]= =1)) cod=1;

else { i=1; cod=1;

while ((cod==1)&&(i

{ if ((x[i]==x[k])||(abs(x[i] x[k])==k i)) cod=0;

i++; } // sfarsit while

} // sfarsit if

} // sfarsit while

if (cod= =0) k  ;

else {if (k= =8)

{ printf("\n%3d. ",++nr);

for (i=1;i<9;printf("%d ",x[i++]));

}}

else x[++k]=0;

}

}

}

A doua variantă:
#include

#include

#define n 100

int x[100],cod,k,nc,nsol;

int Verifica(void)

{ int i,cod1; // cod1=1 conditiile de continuare

cod1=1; // sunt verificate

if (k>1) // cod1=0 in caz contrar;

for(i=1; i<= (k 1); i++)

{ if (x[k]= =x[i]) cod1=0;

if (abs(x[k] x[i]) = = k i) cod1=0; // (*)

}

return cod1;

}
void ScrieSolutie(void)

{ int i;

printf("\n%3d. ",++nsol);

for (i=1; i<=nc; printf("%3d",x[i++]));

}
void CitesteDate(void)

{ int i;

nsol=0;

clrscr();

nc=n+1;

while ((nc>n) || (nc<0))

{ printf ("Dati n = ");

scanf ("%d",&nc);

};

}

void main (void)

{ CitesteDate();

k=1; x[1]=0;

while (k>0)

{ cod=0;

while (((x[k]+1) <= nc) && (cod= =0))

{x[k]++;

cod=Verifica();

}

if (cod= =0) k  ;

else {if (k==nc) ScrieSolutie();

else x[++k]=0;

}

}

}

A doua variantă este modulară, mai uşor de înţeles şi generalizează problema damelor până la tabla de şah de 100x100. Lăsăm pe seama cititorului modificarea funcţiei ScrieSolutie pentru a afişa în mod grafic tabla de şah.

Dacă în funcţia Verifica se şterge instrucţiunea notată cu (*) atunci se obţin toate permutările de n obiecte.

Probleme propuse
14.3.1

Să se rezolve problema turelor de şah după al doilea algoritm. În câte moduri se pot aranja n turnuri pe tabla de şah astfel încât să nu se "bată" reciproc.

14.3.2.

Să se afişeze poziţiile succesive ale unui cal pe tabla de şah, pornind dintr-o poziţie dată, astfel încât să fie atinse toate căsuţele tablei de şah.

14.3.3.

Având un fişier cu o mulţime de cuvinte din limba română de aceeaşi lungime k să se scrie un program C care afişează toate careurile rebusiste fără puncte negre. ( Problema e fascinantă implicând şi cunoştinţe gramaticale dar şi cunoscând faptul că nu s-au construit careuri de 10x10 fără puncte negre manual şi nici cu ajutorul calculatorului; se poate încerca apoi şi cu k:=11,12, . . .).

14.3.4.

Un intreprinzător dispune de un capital C şi are n variante de investiţii. Pentru fiecare investiţie i cunoaşte fondurile de investiţie f_i precum şi beneficiile b_i. Se cere un program care să deducă toate variantele posibile de investiţii al intreprinzătorului. Se mai dau şi condiţiile Cc_i  i {1, . . . ,n}.

14.3.5.

Având un graf neorientat caracterizat prin matricea costurilor să se determine prin bactraking circuitul de cost minim pornind dintr-un vârf dat.

14.3.6.

Având un graf neorientat caracterizat prin matricea de incidenţă a vârfurilor să se determine prin bactraking mulţimile interior stabile maximale.

14.3.7.

Să se determine toate cuvintele binare de lungime 10 care conţin exact 5 cifre de 1.

14.3.8.

Să se determine toate cuvintele binare de lungime 10 care conţin cel mult 5 cifre de 1.

14.3.9.

Să se determine toate cuvintele din {a,b,c}^* (mulţimea tuturor cuvintelor peste alfabetul Σ se notează cu Σ^* ) de lungime 10 care conţin exact 2 simboluri 'a'; 3 simboluri 'b' şi 5 simboluri 'c'.

14.3.10.

Să se determine toate cuvintele din {a,b,c}^* de lungime n care conţin exact n_a simboluri 'a'; n_b simboluri 'b' şi n_c simboluri 'c' (cu condiţia n=n_a+n_b+n_c).

14.3.11.

Să se determine toate tripletele (x₁,x₂,x₃) de numere astfel ca:

x₁+x₂+x₃suma

x₁*x₂*x₃produs

cu valorile suma şi produs date iar x₁S₁, x₂S₂ şi x₃S₃ ; S₁, S₂ şi S₃ fiind trei progresii aritmetice date deasemenea.
14.3.12.

Să se determine toate variantele de pronosport cu 13 rezultate din {1,x,2} care conţin exact n₁ simboluri '1'; n_x simboluri 'x' şi n₂ simboluri '2' (cu condiţia n₁+n_x+n₂=13).

14.3.13.

Să se determine toate variantele de pronosport cu 13 rezultate din {1,x,2} care conţin cel mult n₁ simboluri '1'; cel mult n_x simboluri 'x' şi simboluri '2' în rest (cu condiţia n₁+n_x13).