Metoda backtracking (cautare cu revenire) - varianta iterativa a metodei backtracking

1. NECESITATE

Deseori in practica trebuie sa rezolvam probleme care au un numar foarte mare de solutii posibile. De cele mai multe ori insa, nu ne intereseaza toate solutiile, ci numai o parte dintre ele, care indeplinesc anumite conditii specifice problemei. Pentru astfel de probleme este indicata folosirea metodei backtracking care evita generarea solutilor inutile.

Desigur ca o persoana cu o gandire simplista ar putea spune : " generam toate solutiile, apoi le alegem pe cele care indeplinesc conditiile cerute". Foarte simplu, dar oare si eficient ? Ce rost ar avea sa se genereze niste solutii care oricum nu convin? Din punctul de vedere al timpului necesar calculatorului pentru a obtine toate solutiile, cat de realista este o astfel de abordare?

APLICABILITATE

a.      Se aplica in cadrul problemelor a caror solutie este de tip vector.

b.      Deoarece are un timp de executie exponential, se aplica numai atunci cand nu exista o alta cale de rezolvare a problemei respective

DESCRIERE

Metoda utilizeaza structura de tip stiva si poate fi programata atat iterativ cat si recursiv.

Stiva este acea forma de organizare a datelor (structura de date) cu proprietatea ca operatiile de introducere si scoatere a datelor se fac in varful ei.

Stivele se pot simula utilizand vectori.

Prima idee pe care trebuie sa o retinem ar fi: nu se genereaza toate solutiile posibile, ci numai acelea care indeplinesc anumite conditii specifice problemei, numite conditii de validare (in unele lucrarii de specialitate acestea mai sunt numite si conditii interne).

Varianta iterativa a metodei backtracking

Forma solutiei:

Componentele vectorului X satisfac anumite relatii, numite conditii interne.

Exemplu:

Fie:   

conditii interne

Solutiile din spatiul solutiilor posibile S, care satisfac conditiile interne, se numesc solutii rezultat.

(a,m), (b,m), (c,m), (c,n)

Construirea solutiei:

P.p. ca x₁, . ,x_k-1 au primit valori si satisfac conditiile de continuare

Atribuim o valoare lui x_kS_k

Verificam conditiile de continuare referitoare la x₁,x₂, . ,x_k

daca sunt indeplinite conditiile de continuare atunci se trece la atribuirea unei   valori pentru x_k+1S_k+1

daca nu sunt indeplinite conditiile de continuare:

oricum vom alege x_k+1, . , x_n nu se va ajunge la o solutie rezultat

se va face o noua alegere pentru x_k S_k

- daca S_k s-a epuizat k=k-1 si se face o noua alegere pentru x_k-1S_k-1

Obs:      

Conditiile de continuare trebuie sa fie necesare si suficiente pentru obtinerea unui rezultat

Cand k=n conditiile interne = conditii de continuare (se refera la vectorul solutie)

Conditia k=n+1 este utilizata pentru a sesiza obtinerea unei solutii

Conditia k=0 este utilizata pentru a sesiza sfarsitul procesului de construire a solutiilor

st

Aplicatii

Utilizand metoda backtracking se genereaza in ordine lexicografica cuvintele de cate patru litere din multimea A=, cuvinte care nu contin doua vocale alaturate. Primele

opt cuvinte generate sunt, in ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Cate dintre cuvintele generate incep cu litera b si se termina cu litera e?

a. 9 b. 15 c. 12 d. 20

Utilizand metoda backtracking se genereaza in ordine lexicografica cuvintele de cate patru litere din multimea A=, cuvinte care nu contin doua vocale alaturate. Primele

opt cuvinte generate sunt, in ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Care este ultimul cuvant generat?

a. edcb b. eeee c. edde d. eded

Utilizand metoda backtracking se genereaza in ordine lexicografica cuvintele de cate patru litere din multimea A=, cuvinte care nu contin doua vocale alaturate. Primele

opt cuvinte generate sunt, in ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Care este penultimul cuvant generat?

a. edec b. eded c. edde d. edcb

Utilizand metoda backtracking se genereaza in ordine lexicografica cuvintele de cate patru litere din multimea A=, cuvinte care nu contin doua vocale alaturate. Primele

opt cuvinte generate sunt, in ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Care este antepenultimul cuvant generat?

a. edde b. eddb c. edeb d. edcb

Folosind modelul combinarilor se genereaza numerele naturale cu cate trei cifre distincte din multimea , numere cu cifrele in ordine strict crescatoare, obtinandu-se, in ordine:

, 127, 137, 237. Daca se utilizeaza exact aceeasi metoda pentru a genera numerele

naturale cu patru cifre distincte din multimea , cate dintre numerele

generate au prima cifra 2 si ultima cifra 7?

a. 8 b. 3 c. 4 d. 6

Utilizand metoda backtracking sunt generate numerele de 3 cifre, avand toate cifrele

distincte si cu proprietatea ca cifrele aflate pe pozitii consecutive sunt de paritate diferita.

Stiind ca primele sase solutii generate sunt, in aceasta ordine, 103, 105, 107, 109, 123,

, care este a zecea solutie generata?

a. 145 b. 147 c. 230 d. 149

Folosind tehnica bactracking un elev a scris un program care genereaza toate numerele de cate n cifre (0<n ), cifrele fiind in ordine strict crescatoare. Daca n este egal cu 5, scrieți

in ordine crescatoare toate numerele avand cifra unitaților 6, care vor fi generate de

program.

C₉⁵ =126 numere

Utilizand metoda backtracking sunt generate numerele de 3 cifre care au cifrele in ordine

crescatoare, iar cifrele aflate pe pozitii consecutive sunt de paritate diferita. Stiind ca primele

cinci solutii generate sunt, in aceasta ordine, 123, 125, 127, 129, 145, care este cel de al

-lea numar generat?

a. 169               b. 149 c. 167 d. 147

Utilizand metoda backtracking, sunt generate n ordine crescatoare toate numerele de 3 cifre, astfel incat cifrele sunt in ordine crescatoare, iar cifrele aflate pe pozitii consecutive sunt de paritate diferita. Stiind ca primele trei solutii generate sunt, in aceasta ordine, 123, 125, 127, scrieti toate numerele generate care au suma cifrelor egala cu 12.

Un algoritm de tip backtracking genereaza, in ordine lexicografica, toate sirurile de 5 cifre 0 si 1 cu proprietatea ca nu exista mai mult de doua cifre 0 pe pozitii consecutive. Primele 7 solutii generate sunt: 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este a

-a solutie generata de acest algoritm?

a. 01110 b. 01100 c. 01011 d. 01101

Utilizand metoda backtracking se genereaza permutarile cuvantului info. Daca primele trei solutii generate sunt: fino, fion, fnio care este cea de-a cincea solutie? (4p.)

a. foin b. fnoi c. foni d. ifon

Cate numere cu exact doua cifre pot fi construite folosind doar cifre pare distincte? (4p.)

a. 12 b. 16 c. 20 d. 25

Un algoritm genereaza in ordine crescatoare toate numerele de n cifre, folosind doar cifrele 3, 5 si 7. Daca pentru n=5, primele cinci solutii generate sunt 33333, 33335, 33337,

, 33355, precizati care sunt ultimele trei solutii generate, in ordinea generarii.

Un algoritm genereaza in ordine descrescatoare toate numerele de 5 cifre, fiecare dintre ele avand cifrele in ordine strict crescatoare. Stiind ca primele cinci solutii generate sunt 56789,

, 45789, 45689, 45679, precizati care sunt ultimele trei solutii generate, in ordinea

generarii.

Algoritm in pseudocod (solutii cu acelasi numar de componente = n)

k=1;

st[k]=0; // initializare stiva

while (k>0)

if (k= =n+1) // configuratia e de tip solutie

tipar();

k--;

else

if (exista valori neconsumate in S_k)

else

Aplicatii

Generarea permutarilor multimii  

Exp:

X=(x₁,x₂.x₃)S=xx

Nr. sol:   3! = 6

Conditii interne: st[i]!=st[k]    

#include<iostream.h>

int st[10],k,n,nrsol=0;

void init()

void tipar()

int valid(int k)

void back()

else

if (st[k]<n)

else

}

void main()

Eseu: Contabilitatea conturilor la trezoreria statului si banci comerciale Referat: Organizarea compartimentului financiar-contabil si relatiile cu celelalte compartimente

Generarea aranjamentelor A_n^p

Exp:

p=2

Dim. sol: p

Conditii interne: st[i]!=st[k]

#include<iostream.h>

int st[10],n,i,k, nrsol=0, p;

void init()

void tipar()

int valid (int k)

void back()

else

if (st[k]<n)

else

}

void main()

Generarea combinarilor C_n^k

Exp:

p=2

Dim. sol: p

Conditii interne:   st[k]>st[k-1]

#include<iostream.h>

int st[10],n,i,k,nrsol=0,p;

void init()

void tipar()

int valid (int k)

void back()

else

if (st[k]<n)

else

}

void main()

Problema celor n dame pe o tabla de sah

Fiind data o tabla de sah, de dimensiune n, x_n, se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (dame sa nu se atace reciproc).

Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4x4, o solutie ar fi urmatoarea:

Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1, coloana 1.

A doua dama nu poate fi asezata decat in coloana 3.

Observam ca a treia dama nu poate fi plasata in linia 3. Incercam atunci plasarea celei de-a doua dame in coloana 4.

A treia dama nu poate fi plasata decat in coloana 2.

In aceasta situatie dama a patra nu mai poate fi asezata.

Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana 3, nici in coloana 4, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana 2.

A doua dama nu poate fi asezata decat in coloana 4.

Dama a treia se aseaza in prima coloana.

Acum este posibil sa plasam a patra dama in coloana 3 si astfel am obtinut o solutie a problemei.

Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.

Pentru reprezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama).

Exemplu pentru solutia gasita avem vectorul ST ce poate fi asimilat unei stive.

Doua dame se gasesc pe aceeasi diagonala daca si numai daca este indeplinita conditia: |st(i)-st(j)|=|i-j| ( diferenta, in modul, intre linii si coloane este aceeasi).

ST(4)

ST(3) In general ST(i)=k semnifica faptul ca pe linia i dama ocupa pozitia k.                       ST(2)

ST(1)

Exemplu: in tabla 4 x4 avem situatia:

st(1) i = 1

st(3)= 3 j = 3

|st(1) - st(3)| = |1 - 3| = 2

|i - j| = |1 - 3| = 2

sau situatia

st(1) = 3 i = 1

st(3) = 1 j = 3

|st(i) - st(j)| = |3 - 1| = 2

|i - j| = |1 - 3| = 2

Intrucat doua dame nu se pot gasi in aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema ca doua dame sa nu fie plasate in aceeasi diagonala. A proceda astfel, inseamna ca lucram conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea.

lata algoritmul, conform strategiei generate de backtracking:

- In prima pozitie a stivei se incarca valoarea 1, cu semnificatia ca in linia unu se aseaza prima dama in coloana.

- Linia 2 se incearca asezarea damei in coloana 1, acest lucru nefiind posibil intrucat avem doua dame pe aceeasi coloana.

- In linia 2 se incearca asezarea damei in coloana 2 , insa acest lucru nu este posibil, pentru ca damele se gasesc pe aceiasi diagonala (|st(1)-st(2)|=|1-2|);

- Asezarea damei 2 in coloana 3 este posibila.

- Nu se poate plasa dama 3 in coloana 1, intrucat in liniile 1-3 damele ocupa acelasi coloana.

- Si aceasta incercare esueaza intrucat damele de pe 2 si 3 sunt pe aceeasi diagonala.

- Damele de pe 2-3 se gasesc pe aceeasi coloana.

­- Damele de pe 2-3 se gasesc pe aceeasi diagonala.

­- Am coborat in stiva mutand dama de pe linia 2 si coloana 3 in coloana 4.

Algoritmul se incheie atunci cand stiva este vida.

Conditii interne:

Damele nu pot fi plasate pe aceeasi diagonala

Damele nu pot fi plasate pe aceeasi coloana

#include<iostream.h>

#include<math.h>

int st[10],n,i,k,nrsol=0,j;

void init()

void tipar()

}

int valid (int k)

void back()

else

if (st[k]<n)

else

}

void main()