1

Programare Delphi

Laborator 3

Backtracking iterativ

Metoda backtracking este o strategie generală de căutare din aproape în aproape a unei

soluţii dintr-o mulţime finită de posibilităţi. Problema trebuie formulată astfel încât soluţia să

se prezinte sub forma unei “combinaţii câştigătoare” � = (��, ��, … , ��) cu un număr finit de

componente ≤ �, cu n fixat, fiecare componentă având un număr finit de valori posibile

�� ∈ ��, cu ��, ��, … , �� mulţimi finite. Metoda constă în construirea pas cu pas a unor

combinaţii parţiale care să conducă la o soluţie, căutând mereu pentru ultimul loc un candidat

valid, care să păstreze şansele combinaţiei de a fi completată până la o soluţie, şi în revenirea

pe propriile urme (backtracking) în cazul în care nu mai este găsit un astfel de candidat, până

la cel mai apropriat loc al combinaţiei unde mai există candidaţi valizi.

Metoda poate fi implementată atât recursiv cât şi iterativ, fiind de preferat varianta ite-

rativă.

Prezentăm în continuare o abordare iterativă generală a metodei backtracking, abor-

dare care poate fi folosită în toate cazurile în care problema poate fi pusă sub forma enunţată

mai sus.

Incepem prin a stabili un vocabular comun. Numim condiţii interne acel set de condi-

ţii pe care trebuie să le satisfacă componentele vectorului

� = (��, ��, … , ��) pentru a fi declarat soluţie.

Spunem că am ales un candidat pentrul locul ∈ {1, 2, … , �}, atunci când am fixat o

valoare eligibilă pentru componenta ��, adică o valoare care verifică anumite condiţii de eli-

gibilitate, condiţii care definesc de fapt mulţimea finită ��.

Alegerea unui candidat ��are scopul de a extinde combinaţia parţială ��, ��, … , ����

la una cu şanse de a deveni soluţie, prin urmare �� trebuie să respecte anumite condiţii de

continuare, caz în care spunem că este un candidat valid. Vom extinde numai combinaţiile

valide, formate numai din candidaţi valizi. Metoda este cu atât mai eficientă cu cât avem con-

diţii de continuare mai restrictive, care să elimine din start cât mai multe dintre combinaţiile

sortite eşecului.

In sfârşit, pentru aplicarea metodei mai avem de precizat condiţiile de oprire pe care

trebuie să le satisfacă o combinaţie validă pentru a fi declarată soluţie.

De exemplu, să considerăm următoarea problemă: find date numerele naturale n şi p,

cu � ≤ �, să se listeze toate aranjamentele de n obiecte ale mulţimii {1,2, … , �}.Prin soluţie

vom înţelege un vector de întregi (��, ��, … , ��) cu exact n componente care satisfac condi-

ţiile interne �� ≠ �� pentru � ≠ �.

In acest caz, un candidat �� este eligibil numai dacă aparţine mulţimii {1, 2, … , �},

condiţia de continuare este ca �� să fie diferit de toţi termenii precedenţi, ��, ��, … , ����, iar

condiţia de oprire a extinderii este = �.

Metoda generală constă în gestionarea unei serii de căutări, câte o căutare pe fiecare

loc = 1, 2, … , �. Construcţia soluţiei începe cu căutarea unui candidat valid pentru locul

= 1. Să presupunem că am reuşit să construim combinaţia validă ��, ��, … , ���� şi suntem

acum pe locul k. Vom căuta un candidat valid pentru acest loc parcurgând în ordine valorile

eligibile pentru �� şi testând condiţiile de continuare pentru fiecare candidat găsit. Dacă pe

2

locul k am ajuns prin extinderea combinaţiei ��, ��, … , ����, atunci trebuie să avem grijă să fi

presetat din timp valoarea lui �� astfel încât căutarea să înceapă cu prima valoare eligibilă din

��. Dacă pe locul k am ajuns prin restrângerea combinaţiei ��, ��, … , ��, ����, atunci con-

tinuăm parcurgerea lui �� de la valoarea memorată a lui ��.

Dacă pe locul k nu mai găsim nici un candidat valid spunem că am epuizat locul şi îl

decrementăm pe k, continuând căutarea următorului candidat valid de pe locul k-1.

Dacă pe locul k am găsit un candidat valid atunci testăm dacă am format sau nu o so-

luţie; dacă da o afişăm şi continuăm căutarea tot pe locul k, iar dacă nu încercăm să extindem

combinaţia validă ��, ��, … , �� prin incrementarea lui k şi iniţierea căutării de pe locul urmă-

tor.

Pe scurt, pentru fiecare candidat valid găsit pe locul k parcurgem toată mulţimea ����

în căutare de continuări valide, iar când am epuizat locul k ne întoarcem la căutarea de pe lo-

cul k-1. Intreaga construcţie a combinaţiilor se opreşte atunci când am epuizat primul loc şi,

conform algoritmului, ajungem la valoarea = 0.

In concluzie, dacă într-un program Pascal avem declarată o variabilă globală type combinatie = array [1 .. n] of integer; var a: combinatie;

în care construim rând pe rând seria de combinaţii parţiale, şi dacă presupunem că avem deja

implementate subprogramele procedure preseteazaCandidat(k: integer);

function avemCandidatEligibil(k: integer): boolean; function avemCandidatValid(k: integer): boolean;

function avemSolutie(k: integer): boolean;

şi procedure scrieSolutie(k: integer);

atunci procedura generală de generare şi afişare a tuturor “combinaţiilor câştigătoare” prin

metoda backtracking iterativă este următoarea:

procedure generare; var k: integer; amGasit: boolean; begin k := 1; preseteazaCandidat(k); repeat repeat // cautam urmatorul candidat valid pe locul k amGasit := avemCandidatEligibil(k); until not amGasit or avemCandidatValid(k); if not amGasit then // daca nu mai sunt candidati ne intoarcem Dec(k) //si continuam cautarea de pe locul precedent else if avemSolutie(k) then // altfel, daca avem o solutie, o afisam scrieSolutie(k) // si continuam cautarea tot pe locul k else if k<n then begin // iar daca nu am ajuns la o solutie Inc(k); // extindem combinatia si preseteazaCandidat(k);// presetam cautarea pentru locul nou end; until k<1; end;

3

Pentru exemplificare, prezentăm în continuare listingul complet al programului care

generează toate aranjamentele de p obiecte luate câte n.

program backtracking; {$mode objfpc}{$H+} // Sa se genereze toate aranjamentele de p elemente luate cate n // prin backtracking iterativ uses SysUtils; const n = 3; p = 4; type combinatie = array [1 .. n] of integer; var a: combinatie; procedure preseteazaCandidat(k: integer); begin a[k] := 0 end; function avemCandidatEligibil(k: integer): boolean; begin Inc(a[k]); if a[k] > p then Exit(False); Exit(True); end; function avemCandidatValid(k: integer): boolean; var i: integer; begin for i := 1 to k - 1 do if a[i] = a[k] then Exit(False); Exit(True); end; function avemSolutie(k: integer): boolean; begin Exit(k = n); end; procedure scrieSolutie(k: integer); var i: integer; begin for i := 1 to k do Write(a[i]:2); Writeln; end;

4

procedure generare; var k: integer; amGasit: boolean; begin k := 1; preseteazaCandidat(k); repeat repeat // cautam urmatorul candidat valid pe locul k amGasit := avemCandidatEligibil(k); until not amGasit or avemCandidatValid(k); if not amGasit then // daca nu mai sunt candidati ne intoarcem Dec(k) //si continuam cautarea de pe locul precedent else if avemSolutie(k) then // altfel, daca avem o solutie, o afisam scrieSolutie(k) // si continuam cautarea tot pe locul k else if k<n then begin // iar daca nu am ajuns la o solutie Inc(k); // extindem combinatia si preseteazaCandidat(k);// presetam cautarea pentru locul nou end; until k<1; end; /////////////////////////////////////// begin generare; writeln('Press any key to continue'); Readln; end. { REZULTAT: 1 2 3 1 2 4 1 3 2 1 3 4 1 4 2 1 4 3 2 1 3 2 1 4 2 3 1 2 3 4 2 4 1 2 4 3 3 1 2 3 1 4 3 2 1 3 2 4 3 4 1 3 4 2 4 1 2 4 1 3 4 2 1 4 2 3 4 3 1 4 3 2 Press ENTER }

5

Temă

1. Plata unei sume de bani. Să se listeze toate posibilităţile de plată a unei sume S având la

dispoziţie numai bancnote cu valorile distincte ��, ��, … , ��. Considerăm că S şi �� sunt

exprimate prin numere întregi strict pozitive şi că avem la dispoziţie un număr nelimitat de

bancnote de fiecare tip.

Indicaţie. O “plată” este formată din �� bancnote de tip ��, din �� bancnote de tip ��, ... , din

�� bancnote de tip ��. Evident, considerăm că valorile componentelor vectorului soluţie

� = (��, ��, … , ��) pot fi de la 0 la S.

Valoarea unei combinaţii parţiale ��, ��, … , �� este

�� () = ���� + ���� + ⋯ + ���� şi nu trebuie să depăşească în nici un moment suma de plată. Aceasta este chiar condiţia de

continuare, condiţia de oprire fiind �� () = #. Inceputul programului este următorul:

program backtracking_plata; {$mode objfpc}{$H+} // plata unei sume cu bancnote de valoare data // a[i] = nr de bancnote cu valoarea v[i] // a[i] are valori de la 0 la sumaDePlata const n = 5; type combinatie = array [1 .. n] of integer; var sumaDePlata: integer = 65; a: combinatie; v: combinatie = (1, 5, 10, 50, 100); function val(k: integer): integer; var i: integer; begin Result := 0; for i := 1 to k do Result := Result + v[i] * a[i]; end; procedure preseteazaCandidat(k: integer); begin a[k] := -1 end; function avemCandidatEligibil(k: integer): boolean; begin Inc(a[k]); if (a[k] > sumaDePlata) then Exit(false); Exit(true); end;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2. Partiţiile unei mulţimi. Se dă un număr natural � > 1. Se cere să se genereze toate par-

tiţiile mulţimii

� = {1, 2, … , �}.

Indicaţie. Numim partiţie a lui A o familie de submulţimi mutual disjuncte şi nevide

�� ⊂ �, � = 1, 2, … , , a căror reuniune este A. Submulţimile �� vor fi numite clase.

Pentru a lista o singură dată fiecare partiţie posibilă a lui A vom adopta următoarea

metodă de numerotare a claselor: ordonăm clasele partiţiei în ordine crescătoare după valoa-

rea primului lor element şi le numerotăm în acestă ordine.

Exemplu:

� = {1, 2, 3, 4, 5}, �� = {1, 3}, �� = {2}, �) = {4, 5}. Reprezentăm partiţiile în vectorul � = (��, ��, … , ��), �� fiind indicile clasei din care

face parte elementul k. Partiţia din exemplul dat este descrisă de vectorul

� = (1, 2, 1, 3, 3). Evident că avem �� = 1 întodeauna; �� = 1 sau �� = 2 după cum 1 şi 2 sunt sau nu

în aceeaşi clasă; �) = 1, 2 sau 3 după cum = 3 se găseşte sau nu în una din clasele lui 1

sau 2. Rezultă imediat că valorile eligibile pentru candidatul�� sunt 1, 2, ... , k; mai mult ��

poate avea una din valorile precedente, dacă elementul k se află în una din clasele elementelor

precedente sau poate fi exact cu o unitate mai mare decât valoarea maximă atinsă de compo-

nentele ��, … , ����, în cazul în care k nu se află în nici una din clasele elementelor preceden-

te. Obţinem următoarea condiţie de continuare:

�� ≤ 1 + max {��, … , ����}. In sfârşit, condiţia de oprire este k = n.

Atenţie, prima componentă a vectorului a fiind totdeauna egală cu 1, backtracking-ul

va începe de la k=2.

Incercaţi să afişaţi pe monitor atât vectorul a cât şi partiţia asociată acestuia, conform

modelului următor: (* REZULTAT pentru A={1,2,3,4}: 1 1 1 1 <--> { 1 2 3 4 } 1 1 1 2 <--> { 1 2 3 } { 4 } 1 1 2 1 <--> { 1 2 4 } { 3 } 1 1 2 2 <--> { 1 2 } { 3 4 } 1 1 2 3 <--> { 1 2 } { 3 } { 4 } 1 2 1 1 <--> { 1 3 4 } { 2 } 1 2 1 2 <--> { 1 3 } { 2 4 } 1 2 1 3 <--> { 1 3 } { 2 } { 4 } 1 2 2 1 <--> { 1 4 } { 2 3 } 1 2 2 2 <--> { 1 } { 2 3 4 } 1 2 2 3 <--> { 1 } { 2 3 } { 4 } 1 2 3 1 <--> { 1 4 } { 2 } { 3 } 1 2 3 2 <--> { 1 } { 2 4 } { 3 } 1 2 3 3 <--> { 1 } { 2 } { 3 4 } 1 2 3 4 <--> { 1 } { 2 } { 3 } { 4 } Press ENTER *)

7

3. Subşiruri crescătoare. Se dă un şir finit ��, ��, … , �� de numere întregi. Se cere să se

determine un subşir crescător de lungime maximă.

Indicaţie. Completăm şirul la cele două capete astfel încât �- să fie cel mai mic element iar

���� cel mai mare. Astfel, vom considera numai subşiruri (��.) crescătoare care încep de la

�- = 0 şi se sfârşesc la �� = � + 1, orice subşir crescător al şirului iniţial fiind de forma

��/≤��0

≤ ⋯ ≤ ��.1/ cu �- = 0 < �� < �� < ⋯ < ���� < � + 1 = ��.

Prin soluţie vom înţelege vectorul indicilor subşirului, � = (�-, ��, … , ��), iar prin solu-

ţie optimă o soluţie cu un număr maxim de componente.

Valorile eligibile pentru candidatul �� sunt de la ���� + 1 până la � + 1, condiţia de

continuare este ��.1/≤��.

, iar condiţia de oprire �� = � + 1. Pe măsură ce afişăm soluţiile

păstrăm întru-un vector martor soluţia optimă până în acel moment.

4. Permutări speciale. Fiind dat numărul natural � ≥ 2 se cere să se genereze prin

backtracking toate permutările mulţimii {1, 2, … , �} cu proprietatea că fiecare componentă (în

afară de prima) are în faţa ei cel puţin o componentă de care să difere prin exact o unitate. De

exemplu, 3 4 2 5 1 6 este o astfel de permutare specială pentru � = 6.

Arătaţi că există o corespondenţă biunivocă între mulţimea permutărilor speciale de

ordin n şi mulţimea cuvintelor binare de lungime � − 1 şi, pe baza acestei proprietăţi,

implementaţi un nou algoritm de generare a permutărilor speciale.

5. Paranteze. Fiind dat numărul par �, să se genereze toate combinaţiile de n paranteze

rotunde care se închid corect. De exemplu, pentru � = 4 se obţin numai următoarele două

combinaţii: ( ( ) ) şi ( ) ( ) .

6. Drumuri în plan. Fiind date în plan punctele ��(6�, 7�), ��(6�, 7�),… , ��(6�, 7�), să se

listeze toate drumurile dintre �� şi �� formate numai din segmente ���� cu lungimea mai

mică decât o constantă 8�6 > 0 precizată. Se consideră numai drumuri fără cicluri, care nu

trec de două ori prin acelaşi punct ��.

7. Drumuri de dreapta. Fiind date în plan punctele ��(6�, 7�), ��(6�, 7�), … , ��(6�, 7�),

să se listeze toate drumurile fără cicluri dintre �� şi �� formate numai din segmente ���� şi

care au “orientare de dreapta”: parcurgând drumul în sensul de la �� şi �� nu avem voie să

cotim la stânga!

Bibliografie:

Cornelia Ivaşc, Mona Prună, Tehnici de programare. Aplicaţii. Ed. PETRION, Bucureşti,

1999.