Metoda backtracking (cautare cu revenire)

Metoda backtracking (cautare cu revenire)

Aceasta metoda se aplica problemelor ce pot fi reprezentate sub forma unui arbore finit iar cautarea solutiei presupune parcurgerea arborelui in adancime (DF=Depth First).

Problemele de acest tip au in general solutia de forma x=(x₁, . . . ,x_n) I S₁x . . . xS_n, fiecare S_k fiind o multime finita. Mai facem cateva precizari preliminare:

a) pentru fiecare problema sunt date anumite relatii intre componentele x₁, . . . ,x_n ale lui

x numite conditii interne;

b) produsul cartezian S=S₁xxS_n se mai numeste spatiul solutiilor posibile, iar solutiile

posibile care satisfac conditiile interne se numesc solutii rezultat;

c) in general se cer doua lucruri in astfel de probleme:

- determinarea tuturor solutiilor rezultat;

- determinarea doar a acelor solutii care optimizeaza o functie obiectiv data.

Cum rezolvam astfel de probleme? Exista doua modalitati de rezolvare:

1) tehnica directa (numita si tehnica fortei brute) prin care se genereaza toate elementele spatiului de solutii posibile si apoi se verifica fiecare daca este sau nu o solutie rezultat; aceasta tehnica necesita un timp prohibitiv (daca fiecare S_i are doar 2 componente complexitatea este O(2ⁿ); totodata ar fi necesara imbricarea a n cicluri cu n aprioric necunoscut).

2) backtracking care evita generarea tuturor solutiilor posibile.

Sa dam in continuare cateva repere ale rezolvarii:

solutia este construita progresiv, componenta cu componenta;

lui x_k i se atribuie o valoare (evident ca numai din S_k) daca si numai daca x₁, . . . ,x_k-1 au deja valori;

se verifica conditiile de continuare (strans legate de conditiile interne) daca are sens trecerea la x_k+1;

daca nu are sens (adica conditiile de continuare nu sunt indeplinite atunci facem o noua alegere pentru x_k sau daca am epuizat valorile din S_k atunci k:=k-1 si se face o noua alegere pentru x_k-1; s.a.m.d.

2. daca are sens atunci k:=k+1 si se testeaza daca k>n:

2₁) daca inegalitatea este adevarata atunci se afiseaza solutia astfel determinata

si k:=k-1 continuand procesul de la punctul 1;

2₂) daca inegalitatea este falsa se continua procesul de la punctul 1.

Procedura rezolvarii 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 cateva precizari:

1^o. Predicatul Æ_k(x₁, . . . , x_k) reprezinta conditiile de continuare pentru x₁, . . . , x_k;

2^o. Cod este o valoare ce indica indeplinirea/neindeplinirea conditiilor de continuare;

3^o. Daca predicatul Æ_k(x₁, . . . , x_k) este adevarat k I atunci se vor afla toti vectorii din S;

4^o. Backtracking poate fi usor reprezentat pe un arbore construit astfel:

- nivelul 1 contine radacina;

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

s_k elemente ale lui S_k;

- nivelul n+1 va contine s₁*s₂*. . .* s_n noduri frunza;

- pentru fiecare nod de pe nivelul n+1 etichetele muchiilor continute in drumul ce

leaga radacina de acest nod reprezinta o solutie posibila;

Daca multimile S_k reprezinta progresii aritmetice atunci algoritmul general se modifica 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) reprezinta vectorul primilor termeni ai progresiilor aritmetice;

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

- ratia(n) reprezinta vectorul ratiilor progresiilor aritmetice;

De retinut cele doua avantaje ale acestui procedeu:

evitarea imbricarii unui numar oarecare de cicluri aprioric variabil (in algoritmul propus se imbrica doar doua cicluri pretestate while);

evitarea construirii spatiului tuturor solutiilor posibile S₁xS₂x . . . xS_n.

Problema rezolvata

In cate moduri se pot aranja 8 dame pe tabla de sah astfel incat sa nu se 'bata' reciproc. Sa se foloseasca al doilea algoritm dintre cei mentionati anterior.

Prima varianta

Acest program respecta algoritmul anterior cu unele mici modificari. Facem precizarea ca vectorul x contine in componenta x[i] numarul coloanei de pe tabla de sah pe care se va afla dama de pe linia i. Tiparirea va reprezenta o permutare (din cele 8! solutii posibile). Se vor afla 92 de solutii. Lasam pe seama cititorului sa deduca analogiile si diferentele intre algoritm si program.

#include <stdio.h>

#include <math.h>

void main (void)

// sfarsit while

} // sfarsit if

// sfarsit while

if (cod= =0) k‑‑;

else }

else x[++k]=0;

}

A doua varianta:

#include <stdio.h>

#include <math.h>

#define n 100

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

int Verifica(void)

return cod1;

void ScrieSolutie(void)

void CitesteDate(void)

void main (void)

if (cod= =0) k‑‑;

else

A doua varianta este modulara, mai usor de inteles si generalizeaza problema damelor pana la tabla de sah de 100x100. Lasam pe seama cititorului modificarea functiei ScrieSolutie pentru a afisa in mod grafic tabla de sah.

Daca in functia Verifica se sterge instructiunea notata cu (*) atunci se obtin toate permutarile de n obiecte.

Probleme propuse

Sa se rezolve problema turelor de sah dupa al doilea algoritm. In cate moduri se pot aranja n turnuri pe tabla de sah astfel incat sa nu se 'bata' reciproc.

Sa se afiseze pozitiile succesive ale unui cal pe tabla de sah, pornind dintr-o pozitie data, astfel incat sa fie atinse toate casutele tablei de sah.

Avand un fisier cu o multime de cuvinte din limba romana de aceeasi lungime k sa se scrie un program C care afiseaza toate careurile rebusiste fara puncte negre. ( Problema e fascinanta implicand si cunostinte gramaticale dar si cunoscand faptul ca nu s-au construit careuri de 10x10 fara puncte negre manual si nici cu ajutorul calculatorului; se poate incerca apoi si cu k:=11,12, . . .).

Un intreprinzator dispune de un capital C si are n variante de investitii. Pentru fiecare investitie i cunoaste fondurile de investitie f_i precum si beneficiile b_i. Se cere un program care sa deduca toate variantele posibile de investitii al intreprinzatorului. Se mai dau si conditiile C³c_i iI

Avand un graf neorientat caracterizat prin matricea costurilor sa se determine prin bactraking circuitul de cost minim pornind dintr-un varf dat.

Avand un graf neorientat caracterizat prin matricea de incidenta a varfurilor sa se determine prin bactraking multimile interior stabile maximale.

Sa se determine toate cuvintele binare de lungime 10 care contin exact 5 cifre de 1.

Sa se determine toate cuvintele binare de lungime 10 care contin cel mult 5 cifre de 1.

Sa se determine toate cuvintele din ^* (multimea tuturor cuvintelor peste alfabetul Σ se noteaza cu Σ^* ) de lungime 10 care contin exact 2 simboluri 'a'; 3 simboluri 'b' si 5 simboluri 'c'.

Sa se determine toate cuvintele din ^* de lungime n care contin exact n_a simboluri 'a'; n_b simboluri 'b' si n_c simboluri 'c' (cu conditia n=n_a+n_b+n_c).

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

x₁+x₂+x₃£suma

x₁*x₂*x₃£produs

cu valorile suma si produs date iar x₁IS₁, x₂IS₂ si x₃IS₃ ; S₁, S₂ si S₃ fiind trei progresii aritmetice date deasemenea.

Sa se determine toate variantele de pronosport cu 13 rezultate din care contin exact n₁ simboluri '1'; n_x simboluri 'x' si n₂ simboluri '2' (cu conditia n₁+n_x+n₂=13).

Sa se determine toate variantele de pronosport cu 13 rezultate din care contin cel mult n₁ simboluri '1'; cel mult n_x simboluri 'x' si simboluri '2' in rest (cu conditia n₁+n_x£