Algoritmi cu revenire (backtracking)

Algoritmi cu revenire (backtracking)

Unul din subiectele de mare interes ale programarii se refera la rezolvarea unor probleme cu caracter general.

Ideea este de a concepe algoritmi generali pentru gasirea solutiilor unor probleme specifice, care sa nu se bazeze pe un set fix de reguli de calcul, ci pe incercari repetate si reveniri in caz de nereusita.

Modalitatea comuna de realizare a acestei tehnici consta in descompunerea obiectivului (taskului) in obiective partiale (taskuri partiale).

De regula aceasta descompunere este exprimata in mod natural in termeni recursivi si consta in explorarea unui numar finit de subtaskuri.

In general, intregul proces poate fi privit ca un proces de incercare sau cautare care construieste in mod gradat si parcurge in acelasi timp un arbore de subprobleme.

Obtinerea unor solutii partiale sau finale care nu satisfac, provoaca revenirea recursiva in cadrul procesului de cautare si reluarea acestuia pana la obtinerea solutiei dorite.

Din acest motiv, astfel de algoritmi se numesc algoritmi cu revenire ('backtracking algorithms').

In multe cazuri arborii de cautare cresc foarte rapid, de obicei exponential, iar efortul de cautare creste in aceeasi masura.

In mod obisnuit, arborii de cautare pot fi simplificati numai cu ajutorul euristicilor, simplificare care se reflecta de fapt in restrangerea volumului de calcul si incadrarea sa in limite acceptabile.

Scopul acestui paragraf:

Nu este acela de a discuta regulile generale ale euristicii.

Mai degraba, se vor aborda principiile separarii unei probleme in subproblemele care o rezolva;

Si utilizarea recursivitatii in acest context.

1. Turneul calului

Specificarea problemei:

Se considera o tabla de sah (esicher) cu n² campuri.

Un cal caruia ii este permis a se misca conform regulilor sahului, este plasat in campul cu coordonatele initiale x₀ si y₀ .

Se cere sa se gaseasca acel parcurs al calului - daca exista vreunul - care acopera toate campurile tablei, trecand o singura data prin fiecare.

Primul pas in abordarea problemei parcurgerii celor n² campuri este acela de a considera problema urmatoare:

'La un moment dat se incearca executia unei miscari urmatoare sau se constata ca nu mai este posibila nici una si atunci se revine in pasul anterior'.

Pentru inceput se va defini algoritmul care incearca sa execute miscarea urmatoare a calului.

PROCEDURE IncearcaMiscareaUrmatoare;

BEGIN

*initializeaza lista miscarilor

REPEAT

*selecteaza posibilitatea urmatoare din lista

miscarilor

IF *este acceptabila THEN

BEGIN [1.a]

*inregistreaza miscarea curenta;

IF *tabela nu e plina THEN

BEGIN

IncearcaMiscareaUrmatoare;

IF NOT *miscare reusita THEN

*sterge inregistrarea curenta

END

ELSE

*miscare reusita

END

UNTIL (*miscare reusita) OR (*nu mai exista

posibilitati in lista miscarilor)

END;

In continuare se vor preciza cateva dintre structurile de date care vor fi utilizate.

In primul rand tabela de sah va fi reprezentata prin matricea t pentru care se introduce tipul TipIndice [1.b].

TYPE TipIndice = 1..n; [1.b]

TipTabela = ARRAY[TipIndice,TipIndice] OF integer;

Dupa cum se observa, in campurile tabelei t se memoreaza valori intregi si nu valori booleene care sa indice ocuparea.

Acest lucru se face cu scopul de a pastra urma traseului parcurs conform urmatoarei conventii [1.c].

t[x,y] = 0;

t[x,y] = i; [1.c]

In continuare se vor stabili parametrii specifici de apel ai procedurii. Acestia trebuie sa precizeze:

(1) Conditiile de start ale noii miscari (parametri de intrare)

(2) Sa precizeze daca miscarea respectiva este reusita sau nu (parametru de iesire).

Pentru prima cerinta (1) sunt suficiente:

Coordonatele x,y de la care va porni miscarea

Si valoarea i care precizeaza numarul mutarii curente (din ratiuni de inregistrare).

Pentru cea de-a doua cerinta (2) se introduce parametrul de iesire q = true desemnand miscare reusita respectiv q = false nereusita, din punctul de vedere al acceptarii miscarii.

Problema care se pune in continuare este aceea a rafinarii propozitiilor precedate de caracterul '*' in secventa [1.a].

In primul rand faptul ca *tabela nu este plina se exprima prin i < n².

Daca se introduc variabilele locale u si v pentru a preciza coordonatele unei posibile destinatii a miscarii conform regulilor dupa care se efectueaza saltul calului,

atunci propozitia *este acceptabila poate fi exprimata ca si o combinatie logica a conditiilor 1   u   n si  v   n (adica noul camp este pe tabela) si ca el nu a fost vizitat anterior (t[u,v] = 0).

Asertiunea *inregistreaza miscarea devine t[u,v] = i;

Asertiunea *sterge inregistrarea curenta, se exprima prin t[u,v] = 0.

Se mai introduce variabila booleana locala q1 utilizata ca si parametru rezultat pentru apelul recursiv al procedurii. Variabila q1 substituie de fapt conditia *miscare reusita .

Se ajunge in definitiv la urmatoarea formulare a procedurii [1.d].

PROCEDURE Incearca(i: integer; x,y: indice;

VAR q: boolean);

VAR u,v: integer; q1: boolean;

BEGIN

*initializeaza lista miscarilor

REPEAT

*fie u,v coordonatele miscarii urmatoare conform

regulilor sahului

IF (1<=u<=n) AND (1<=v<=n) AND (t[u,v]=0) THEN

BEGIN

t[u,v]:= i; [1.d]

IF i<n*n THEN

BEGIN

Incearca(i+1,u,v,q1);

IF NOT q1 THEN t[u,v]:= 0

END

ELSE

q1:= true

END

UNTIL q1 OR (nu mai exista posibilitati in lista

miscarilor);

q:= q1

END;

Relativ la aceasta secventa se fac urmatoarele precizari.

Tehnica utilizata este cea cunoscuta in literatura de specialitate sub denumirea de 'look ahead' (tehnica scrutarii). In baza acestei tehnici:

(1) Se apeleaza procedura cu coordonatele curente x si y;

(2) Se selecteaza o noua miscare de coordonate u si v (urmatoarea din cel 8 posibile din lista de miscari);

(3) Se incearca realizarea miscarii urmatoare plecand de la pozitia u,v.

Daca miscarea nu este reusita, respectiv s-au parcurs fara succes toate cele 8 posibilitati ale listei de miscari, se anuleaza miscarea curenta (u,v), ea fiind lipsita de perspectiva (bucla REPEAT).

Privind in perspectiva evolutiei cautarii, fiecare dintre cele 8 miscari este tratata in maniera similara:

Respectiv pornind de la fiecare dintre miscari se merge atat de departe cat se poate,

In caz de nereusita se incerca miscarea urmatoare din lista de miscari pana la epuizarea tuturor posibilitatilor,

Daca s-au epuizat toate posibilitatile, se anuleaza miscarea curenta.

Dupa cum se observa, procedura se extinde de fapt peste trei niveluri de cautare, element care ii permite revenirea in caz de esec in vederea selectarii unui nou parcurs.

Arborele de apeluri asociat cautarii:

Este de ordinul 8 (din fiecare punct se pot selecta 8 posibilitati de miscare)

Are inaltimea n² (numarul de pasi necesari pentru solutia finala), element care explica complexitatea procesului de determinare a solutiei problemei.

In pasul urmator si ultimul de rafinare mai raman cateva puncte de specificat.

Precizarea saltului calului.

Fiind data o pozitie initiala <x,y> exista opt posibilitati pentru generarea coordonatelor destinatiei miscarii urmatoare <u,v>, care sunt numerotate de la 1 la 8 in fig.1.a.

Fig.1.a. Miscarile posibile ale calului pe esicher

O metoda simpla de obtinere a lui u si v din x si y este de a aduna la acestea din urma diferentele specifice de coordonate memorate in doua tablouri, unul pentru x notat cu a si unul pentru y notat cu b.

Indicele k precizeaza numarul urmatorului candidat din lista miscarilor (1   k 

Detaliile de implementare apar in programul [1.e].

Procedura recursiva este initiata printr-un apel cu coordonatele x0,y0 de la care porneste parcursul turneului calului.

Acestui camp i se atribuie valoarea 1, restul campurilor se marcheaza ca fiind libere (valoare nula).

Se face urmatoarea precizare: o variabila t[u,v] exista numai daca u si v sunt in domeniul 1..n.

In program aceasta cerinta a fost implementata cu ajutorul operatorului IN, utilizand multimea S, implementare care pentru valori mici ale lui u respectiv v este foarte eficienta.

PROGRAM TurneulCalului;

CONST n=5;

TYPE TipIndice = 1..n;

VAR i,j: TipIndice;

q: boolean;

S: SET OF integer;

a,b: ARRAY[1..8] OF integer;

t: ARRAY[TipIndice,TipIndice] OF integer;

PROCEDURE Incearca(i: integer; x,y: TipIndice;
VAR q: boolean);

VAR k,u,v: integer;

k: integer;

q1: boolean;

BEGIN

k:= 0;

REPEAT

k:= k+1; q1:= false;

u:= x+a[k]; v:= y+b[k];

IF (u IN S) AND (v IN S) THEN

IF t[u,v]=0 THEN

BEGIN

t[u,v]:= i; [1.e]

IF i<n*n THEN

BEGIN

Incearca(i+1,u,v,q1);

IF NOT q1 THEN t[u,v]:= 0

END

ELSE

q1:= true

END

UNTIL q1 OR (k=8);

q:= q1

END;

BEGIN

S:= [1,2,3,4,5];

a[1]:= 2; b[1]:= 1;

a[2]:= 1; b[2]:= 2;

a[3]:=‑1; b[3]:= 2;

a[4]:=‑2; b[4]:= 1;

a[5]:=‑2; b[5]:=‑1;

a[6]:=‑1; b[6]:=‑2;

a[7]:= 1; b[7]:=‑2;

a[8]:= 2; b[8]:=‑1;

FOR i:=1 TO n DO

FOR j:= 1 TO n DO t[i,j]:= 0;

t[1,1]:= 1; Incearca(2,1,1,q);

IF q THEN

FOR i:= 1 TO n DO

BEGIN

FOR j:= 1 TO n DO Write(' ',t[i,j]);

Writeln

END

ELSE Writeln(' nu exista solutie ')

END.

In figura 1.b se prezinta rezultatele executiei programului TurneulCalului

pentru pozitiile initiale (1,1),(3,3) cu n = 5 si (1,1) cu n = 6.

6 15 10 21 23 10 15 4 25

14 9 20 5 16 16 5 24 9 14

19 2 7 22 11 11 22 18 3

8 13 24 17 4 6 17 20 13 8

25 18 3 12 23 21 12 7 2 19

16 7 26 11 14

34 25 12 15 6 27

17 2 33 8 13 10

32 35 24 21 28 5

23 18 3 30 9 20

36 31 22 19 4 29

Fig.1.b. Exemple de executie ale programului TurneulCalului

Caracteristica esentiala a acestui algoritm:

Inainteaza spre solutia finala pas cu pas, tatonand si inregistrand drumul parcurs.

Daca la un moment dat constata ca drumul ales nu conduce la solutia dorita ci la o fundatura, revine, stergand inregistrarile pasilor pana la proximul punct care permite o noua alternativa de drum.

Aceasta activitate se numeste revenire (backtraking).

2. Probleme (n,m). Determinarea unei solutii

Modelul principal general al unui algoritm de revenire se preteaza foarte bine pentru rezolvarea problemelor pentru care:

Solutia finala presupune parcurgerea a n pasi succesivi,

Fiecare pas putand fi selectat dintre m posibilitati.

O astfel de problema se numeste problema de tip (n,m).

In secventa [2.a] apare modelul principial de rezolvare a unei astfel de probleme in forma procedurii Incearca . Modelul ofera o singura solutie a problemei.

Procedura Incerca;

BEGIN

*initializeaza selectia posibilitatilor;

REPEAT

*selecteaza posibilitatea urmatoare;

IF acceptabila THEN [2.a]

BEGIN

*inregistreaz‑o ca si curenta;

IF *solutie incompleta THEN

BEGIN

Incerca *pasul urmator;

IF *nu este reusit THEN

*sterge inregistrarea curenta

END

ELSE

*pas reusit (solutie completa)

END

UNTIL (*pas reusit) OR (*nu mai sunt posibilitati)

END;

Acest model principial poate fi concretizat in diverse forme. In continuare se prezinta doua variante.

(1) In prima varianta, procedura Incearca1 are drept parametru de apel numarul pasului curent

Explorarea posibilitatilor se realizeaza in bucla interioara REPEAT [2.b].

Procedura Incerca1(i: TipPas);

VAR posibilitate: TipPosibilitate;

BEGIN

posibilitate:= 0;

REPEAT

posibilitate:= posibilitate+1;

IF *acceptabila THEN

BEGIN [2.b]

*inregistreaz-o ca si curenta;

IF I<n THEN

BEGIN

Incerca1(I+1);

IF *nereusit THEN

*sterge inregistrarea curenta

END

ELSE

*solutie completa (afisare)

END

UNTIL *solutie completa OR (posib=m)

END;

(2) In cea de-a doua varianta, procedura Incearca2 are drept parametru de apel o posibilitate de selectie

Constructia solutiei se realizeaza apeland recursiv procedura pe rand pentru fiecare posibilitate in parte [2.c].

Din punctul de vedere al finalitatii cele doua variante sunt identice, ele difera doar ca forma.

Procedura Incearca2(posibilitate: TipPosibilitate);

BEGIN

IF *acceptabila THEN

BEGIN

*inregistreaz-o ca si curenta;

IF *solutie incompleta THEN

BEGIN [2.c]

Incearca2(Posibilitate₁);

Incearca2(Posibilitate₂);

Incearca2(Posibilitate_m);

*sterge inregistrarea curenta

END

ELSE

*solutie completa (afisare)

END

END;

Se presupune ca la fiecare pas numarul posibilitatilor de examinat este fix (m) si ca procedura este apelata initial prin Incearca2(1).

In continuare in cadrul acestui paragraf vor fi prezentate cateva aplicatii ale algoritmilor cu revenire, care se preteaza deosebit de bine unei abordari recursive.

3. Problema celor 8 regine

Problema celor 8 regine reprezinta un exemplu bine cunoscut de utilizare a algoritmilor cu revenire.

Aceasta problema a fost investigata de K.F. Gauss in 1850, care insa nu a rezolvat-o complet, intrucat pana in prezent nu a fost gasita o solutie analitica completa.

In schimb ea poate fi rezolvata prin incercari, necesitand o mare cantitate de munca, rabdare, exactitate si acuratete, atribute in care masina de calcul exceleaza asupra omului chiar atunci cand acesta este un geniu.

Specificarea Problemei celor 8 regine:

Pe o tabla de sah trebuiesc plasate 8 regine astfel incat nici una dintre ele sa nu le ameninte pe celelalte.

Se observa imediat ca aceasta este o problema de tip(n,m):

Deoarece exista 8 regine care trebuiesc plasate, deci solutia necesita 8 pasi,

Pentru fiecare din cele 8 regine existand, dupa cum se va vedea, 8 posibilitati de a fi asezate pe tabla de sah.

Pornind de la modelul [2.a] se obtine imediat urmatoarea formulare primara a algoritmului [3.a].

PROCEDURE Incerca(i: regina);

BEGIN

*initializeaza selectia locului de plasare pentru

a i‑a regina

REPEAT

*selecteaza locul urmator

IF *loc sigur THEN

BEGIN [3.a]

*plaseaza regina i

IF i<8 THEN

BEGIN

Incearca(i+1);

IF *incercare nereusita THEN *ia regina

END

ELSE

*incercare reusita (i=8)

END

UNTIL *incercare reusita OR (*nu mai exista locuri)

END;

Sunt necesare cateva precizari.

Deoarece din regulile sahului se stie ca regina ameninta toate campurile situate pe aceeasi coloana, rand sau diagonala in raport cu campul pe care ea se afla, rezulta ca fiecare coloana a tablei de sah va putea contine o singura regina.

Astfel alegerea pozitiei celei de-a i-a regine poate fi restransa numai la coloana i.

In consecinta:

Parametrul i din cadrul algoritmului devine indexul coloanei in care va fi plasata regina i,

Procesul de selectie se restrange la una din cele 8 valori posibile ale indicelui j care precizeaza randul in cadrul coloanei.

In concluzie:

Avem o problema tipica (8,8),

Solutionarea ei necesita 8 pasi (asezarea celor 8 regine),

Fiecare intr-una din cele 8 pozitii ale coloanei proprii (8 posibilitati).

Arborele de apeluri recursive este de ordinul 8 si are inaltimea 8.

In continuare se impune alegerea modalitatii de reprezentare a pozitiei celor 8 regine pe tabla de sah.

Solutia imediata este aceea a reprezentarii tablei cu ajutorul unei matrice t de dimensiuni 8x8 , dar o astfel de reprezentare conduce la operatii greoaie si complicate de determinare a campurilor disponibile.

Pornind de la principiul ca de fiecare data trebuiesc utilizate reprezentarile directe cele mai relevante si mai eficiente ale informatiei, in cazul de fata nu se vor reprezenta pozitiile reginelor pe tabla de sah ci faptul ca o regina a fost sau nu plasata pe un anumit rand sau pe o anumita diagonala.

Stiind ca pe fiecare coloana este plasata o singura regina, se poate alege urmatoarea reprezentare a datelor [3.b].

VAR x: ARRAY[1..8] OF integer;

a: ARRAY[1..8] OF boolean;

b: ARRAY[b1..b2] OF boolean; [3.b]

c: ARRAY[c1..c2] OF boolean;

Presupunand ca regina i se plaseaza in pozitia (i,j) pe tabla de sah, semnificatia acestei reprezentari apare in secventa [3.c].

x[i]:= j precizeaza locul j al reginei in coloana i

a[j]:= true nici o regina nu ameninta randul j [3.c]

b[k]:= true nici o regina nu ameninta diagonala / k

c[k]:= true nici o regina nu ameninta diagonala k

Se precizeaza ca pe tabela de sah exista 15 diagonale / (inclinate spre dreapta) si 15 diagonale (inclinate spre stanga).

Caracteristica unei diagonale / este aceea ca suma coordonatelor i si j pentru oricare camp care ii apartine este o constanta,

Pentru diagonalele este caracteristic faptul ca diferenta coordonatelor i si j pentru oricare camp este o constanta.

In figura 3.a apar reprezentate aceste doua tipuri de diagonale.

Dupa cum se observa, pentru diagonalele / sumele i+j sunt cuprinse in domeniul [2,16]

Iar pentru diagonalele diferentele apartin domeniului [-7,7].

i + j

-7 i - j

Fig.3.a. Categorii de diagonale in problema celor 8 regine

Aceste considerente fac posibila alegerea valorilor limitelor b1,b2,c1,c2 pentru indicii tabelelor b si c [3.b].

Una din posibilitati este cea utilizata in continuare pentru care s-au ales b1 = 2, b2 = 16, c1 = 0, c2 = 14 .

Pentru b1 si b2 s-au ales chiar limitele intervalului in care sumele indicilor iau valori,

Intervalul in care iau valori diferentele indicilor a fost translatat cu valoarea 7 spre dreapta pentru a obtine valori pozitive pentru indicele de acces in tabela c.

Cu alte cuvinte, accesul in tabloul b destinat evidentei diagonalelor / se realizeaza prin b[i+j]

Iar accesul in tabloul c destinat evidentei diagonalelor prin c[i-j+7].

Initial, locatiile tablourilor a,b si c se pozitioneaza pe true.

Cu ajutorul acestor reprezentari afirmatia *plaseaza regina pe pozitia (i,j), i fiind coloana proprie, devine [3.d]:

x[i]:= j; a[j]:= false; b[i+j]:= false; [3.d]

c[i‑j+7]:= false

In acelasi context, afirmatia *ia regina apare rafinata in secventa [3.e]:

a[j]:= true; b[i+j]:= true; c[i‑j+7]:= true [3.e]

Conditia *sigura este indeplinita daca campul (i,j) destinatie apartine unui rand si unor diagonale care sunt libere (true), situatie ce poate fi exprimata de urmatoarea expresie logica [3.f]:

a[j] AND b[i+j] AND c[i‑j+7] [3.f]

Programul care materializeaza aceste considerente apare in secventa [3.g].

PROGRAM Regine1;

VAR i: integer; q: boolean;

a: ARRAY[1..8] OF boolean;

b: ARRAY[2..16] OF boolean;

c: ARRAY[0..14] OF boolean;

x: ARRAY[1..8] OF integer;

PROCEDURE Incearca(i: integer; VAR q: boolean);

VAR j: integer;

BEGIN

j:= 0;

REPEAT

j:= j+1; q:= false;

IF a[j] AND b[i+j] AND c[i‑j+7] THEN

BEGIN

x[i]:= j; [3.g]

a[j]:= false; b[i+j]:= false;

c[i‑j+7]:= false;

IF i<8 THEN

BEGIN

Incearca(i+1,q);

IF NOT q THEN

BEGIN

a[j]:= true; b[i+j]:= true;

c[i‑j+7]:= true

END

END

ELSE

q:= true

END

UNTIL q OR (j=8)

END;

BEGIN

FOR i:=1 TO 8 DO a[i]:= true;

FOR i:=2 TO 16 DO b[i]:= true;

FOR i:=0 TO 14 DO c[i]:= true;

Incearca(1,q);

IF q THEN

FOR i:=1 TO 8 DO Write(x[i]);

Writeln

END

Solutia determinata de program este x =(1,5,8,6,3,7,2,4) si apare reprezentata grafic in figura 3.b.

Fig.3.b. Solutia problemei celor 8 regine

4. Determinarea tuturor solutiilor unei probleme (n,m). Generalizarea problemei celor 8 regine

Modelul de determinare a unei solutii pentru o problema de tip (n,m) poate fi usor extins pentru a determina toate solutiile unei astfel de probleme.

Pentru aceasta este necesar ca generarea pasilor care construiesc solutia sa se faca intr-o maniera ordonata ceea ce garanteaza ca un anumit pas nu poate fi generat decat o singura data.

Aceasta proprietate corespunde cautarii in arborele de apeluri, intr-o maniera sistematica, astfel incat fiecare nod sa fie vizitat o singura data.

De indata ce o solutie a fost gasita si inregistrata, se trece la determinarea solutiei urmatoare pe baza unui proces de selectie sistematica pana a la epuizarea tuturor posibilitatilor.

Schema generala de principiu derivata din [2.a], care rezolva aceasta problema apare in [4.a].

In mod surprinzator, gasirea tuturor solutiilor unei probleme de tip (n,m) presupune un algoritm mai simplu decat gasirea unei singure solutii.

Procedura Incearca;

BEGIN

FOR *toate posibilitatile de selectie DO

IF *selectie acceptabila THEN

BEGIN

*inregistreaz-o ca si curenta [4.a]

IF *solutia incompleta THEN

Incearca *pasul urmator

ELSE

*evidentiaza solutia;

*sterge inregistrarea curenta

END

END;

Ca si in cazul anterior, acest model principial va fi concretizat in doua variante.

(1) In prima varianta, procedura Incearca1 are drept parametru de apel numarul pasului curent si realizeaza explorarea posibilitatilor in bucla interioara FOR [4.b].

Deoarece pentru evidentierea tuturor posibilitatilor in fiecare pas trebuiesc parcurse toate valorile lui k=[1,m], ciclul REPEAT a fost inlocuit cu unul FOR.

PROCEDURE Incearca1(i: TipPas);

VAR posib: TipPosibilitate;

BEGIN

FOR posib:= 1 TO m DO

IF acceptabila THEN

BEGIN

*inregistreaz-o ca si curenta;

IF i<n THEN [4.b]

Incearca1(i+1)

ELSE

*afiseaza solutia;

*sterge inregistrarea

END

END;

(2) In cea de-a doua varianta, procedura Incearca2 are drept parametru de apel o posibilitate de selectie

Constructia solutiei se realizeaza apeland recursiv procedura pe rand pentru fiecare posibilitate in parte. [4.c].

Procedura Incearca2(posib: TipPosibilitate);

BEGIN

IF *acceptabila THEN

BEGIN

*inregistreaz-o ca si curenta;

IF *solutie incompleta THEN

BEGIN [4.c]

Incearca2(Posibilitate₁);

Incearca2(Posibilitate₂);

Incearca2(Posibilitate_m);

END

ELSE

*afiseaza solutia

*sterge inregistrarea curenta

END

END;

Pentru exemplificare, se prezinta generalizarea problemei celor 8 regine in vederea determinarii tuturor solutiilor [4.d].

PROGRAM OptRegine;

VAR i: integer;

a: ARRAY[1..8] OF boolean;

b: ARRAY[2..16] OF boolean;

c: ARRAY[0..14] OF boolean;

x: ARRAY[1..8] OF integer;

PROCEDURE Afisare;

VAR k: integer;

BEGIN

FOR k:=1 TO 8 DO Write(x[k]); [4.d]

Writeln

END;

PROCEDURE Incearca(i: integer);

VAR j: integer;

BEGIN

FOR j:=1 TO 8 DO

IF a[j] AND b[i+j] AND c[i‑j+7] THEN

BEGIN

x[i]:= j;

a[j]:= false; b[i+j]:= false; c[i‑j+7]:=

false;

IF i<8 THEN

Incearca(i+1)

ELSE

Afisare;

a[j]:= true; b[i+j]:= true; c[i‑j+7]:= true

END

END;

BEGIN

FOR i:=1 TO 8 DO a[i]:= true;

FOR i:=2 TO 16 DO b[i]:= true;

FOR i:=0 TO 14 DO c[i]:= true;

Incearca(1)

END

Algoritmul prezentat anterior determina cele 92 de solutii ale problemei celor 8 regine.

De fapt, din cauza simetriei exista doar 12 solutii distincte care apar evidentiate in figura 4.a.

R1 R2 R3 R4 R5 R6 R7 R8

5 8 6 3 7 2 4

6 8 3 7 4 2 5

7 4 6 8 2 5 3

7 5 8 2 4 6 3

2 4 6 8 3 1 7 5

2 5 7 1 3 8 6 4

2 5 7 4 1` 8 6 3

2 6 1 7 4 8 3 5

2 6 8 3 1 4 7 5

2 7 3 6 8 5 1 4

2 7 5 8 1 4 6 3

2 8 6 1 3 5 7 4

Fig.4.a. Solutiile problemei celor 8 regine

5. Problema relatiilor stabile

Specificarea problemei:

Se dau doua multimi disjuncte A si B de cardinalitate egala n.

Se cere sa se gaseasca o multime de n perechi  <a,b>  astfel incat a I A si b I B , perechi care sa satisfaca anumite constrangeri.

Exista multe criterii de alcatuire a perechilor, unul dintre ele este cel cunoscut sub denumirea de 'regula relatiei stabile' ('stable marriage rule').

Se presupune ca ia fiinta un ansamblu de dansuri pentru care s-au inscris baieti si fete in numar egal (n).

In general fiecare baiat si fiecare fata are preferinte distincte fata de partenerul sau.

In baza acestor preferinte se constituie n perechi de dansatori.

Daca in aceasta repartizare exista un baiat si o fata care nu formeaza o pereche, dar care se prefera reciproc fata de actualii lor parteneri, se spune ca repartizarea este instabila.

Daca nu exista astfel de perechi, repartizarea se numeste stabila.

Aceasta situatie se refera la o serie de probleme asemanatoare din viata de toate zilele in care atribuirile trebuiesc executate in raport cu anumite preferinte: casatorie, alegerea unei facultati de catre un candidat, alegerea unei meserii etc.

In cazul de fata problema va fi oarecum simplificata intrucat se presupune ca lista de preferinte este un invariant si ca ea nu se modifica dupa o atribuire particulara.

O modalitate de rezolvare a problemei este aceea de a se incerca alcatuirea perechilor de dansatori pe rand, pana la epuizarea celor doua grupuri.

Pentru aflarea tuturor repartizarilor stabile se poate realiza rapid schita algoritmului de rezolvare intrucat aceasta este evident o problema de tip (n,m) careia ii trebuiesc determinate toate solutiile.

Pornind de la modelul [4.a], procedura Incearca reprezinta prima forma a algoritmului care determina perechile.

Ideea este de a lua pe rand baietii si de a le distribui partenere, cautarea desfasurandu-se conform listei de preferinte a baietilor [5.a].

PROCEDURE Incearca (b: TipBaiat);

VAR o: TipOrdin;

BEGIN

FOR o:=1 TO n DO

BEGIN

*alege cea de‑a o‑a preferinta a baiatului b

IF *acceptabila THEN

BEGIN [5.a]

*inregistreaza perechea;

IF b nu este ultimul baiat THEN

Incearca(Succ(b))

ELSE

*inregistreaza setul stabil ;

*sterge perechea

END

END

END;

In continuare se vor preciza tipurile de date.

Din ratiuni de claritate a programului se introduc trei tipuri scalare identice ca definitie, dar cu nume diferite [5.b].

Datele initiale sunt reprezentate prin doua matrice care indica preferintele baietilor respectiv preferintele fetelor.

PrefBaieti[b] reprezinta lista de preferinte a baiatului b, respectiv PrefBaieti[b,o] este fata care ocupa pozitia o in lista baiatului b.

Similar PrefFete[f] este lista de preferinte a fetei f, iar PrefFete[f,o] este cea de-a o-a alegere a sa (fig.5.a).

TYPE TipBaiat = 1..n;

TipFata = 1..n; [5.b]

TipOrdin = 1..n;

VAR PrefBaieti: ARRAY[TipBaiat,TipOrdin] OF TipFata;

PrefFete: ARRAY[TipFata,TipOrdin] OF TipBaiat;

Un exemplu de date de intrare apare in figura 5.a

Fig.5.a. Date de intrare pentru determinarea relatiei stabile

Rezultatul executiei algoritmului va fi prezentat in forma unui tablou de fete x, astfel incat x[b] reprezinta partenera baiatului b.

Pentru egalitatea dintre intre baieti si fete se mai introduce un tablou de baieti y, astfel incat y[f] precizeaza partenerul fetei f [5.c].

VAR x: ARRAY[TipBaiat] OF TipFata;  [5.c]

y: ARRAY[TipFata] OF TipBaiat;

Este evident ca nu sunt necesare ambele tablouri, unul putandu-se determina din celalalt conform relatiilor: x[y[f]]=f si y[x[b]]=b care sunt valabile pentru perechile constituite.

Desi valorile lui y[f] pot fi determinate printr-o simpla baleere a lui x , totusi y va fi pastrat, pe de o parte din ratiuni de echitate iar pe de alta parte pentru claritatea si eficienta programului generat.

Informatiile cuprinse in x si y servesc la determinarea stabilitatii setului de perechi de dansatori care se construieste.

Deoarece acest set este construit pas cu pas, generand cate o pereche careia i se verifica imediat stabilitatea, x si y sunt necesari chiar inainte ca toate componentele lor sa fie definite.

Pentru a pastra evidenta componentelor definite se utilizeaza doua tablouri booleene auxiliare: Bneales respectiv FNealeasa [5.d].

BNeales: ARRAY[baiat] OF boolean; [5.d]

FNealeasa: ARRAY[fata] OF bolean;

BNeales[b]= false

FNealeasa[f]= false

Semnificatia campurilor celor doua tablouri apare in aceeasi secventa.

Dupa cum se observa, BNeales[b]= false implica ca x[b] este definit, deci baiatul b are pereche

Iar FNealeasa = false implica ca y[f] este definit, deci fata f are pereche.

Deoarece alcatuirea perechilor se face pornind de la baieti care sunt parcursi in ordine (bucla FOR din [5a]), faptul ca un baiat k a fost selectat sau nu, se poate determina din valoarea lui b conform relatiei [5.e]:

NOT BNeales[k] s k < b  [5.e]

Aceasta sugereaza faptul ca tabloul BNeales nu este necesar si in consecinta se va utiliza un singur tablou FNealeasa destinat fetelor.

Conditia *acceptabila va fi rafinata prin intermediul conditiilor FNealeasa[f] si *stabila, unde conditia *stabila va fi rafinata ulterior.

Aplicand aceste dezvoltari se obtine [5.f] .

PROCEDURE Incearca(b: TipBaiat);

VAR o: TipOrdin; f: TipFata;

BEGIN

FOR o:=1 TO n DO

BEGIN

f:= PrefB[b,o];

IF FNealeasa[f] AND *stabila THEN [5.f]

BEGIN

x[b]:= f; y[f]:= b; FNealeasa[f]:= false

IF b<n THEN

Incearca(Succ(b))

ELSE

*inregistreaza setul stabil;

FNealeasa[f]:= true

END

END;

Elementul esential in acest context este determinarea stabilitatii.

O prima observatie se refera la faptul ca stabilitatea se stabileste prin definitie din compararea ordinelor de preferinte.

Ordinul unui baiat sau al unei fete nu sta direct la dispozitie din datele utilizate pana in acest moment: el poate fi determinat printr-o cautare costisitoare in tablourile PrefBaieti respectiv PrefFete.

Deoarece in determinarea stabilitatii stabilirea ordinului de preferinta este o operatie foarte frecventa, pentru a o face cat mai eficienta se introduc doua noi structuri de date [5.g].

Astfel, OFB[b,f] reprezinta ordinul de preferinta pe care il are fata f in lista baiatului b,

Iar OBF[f,b] reprezinta prioritatea baiatului b in lista fetei f.

Este evident ca cele doua matrice sunt invariante si pot fi usor determinate din matricele initiale PrefBaieti si PrefFete.

OFB: ARRAY[TipBaiat,TipFata] OF TipOrdin;

[5.g]

OBF: ARRAY[TipFata,TipBaiat] OF TipOrdin;

In continuare stabilitatea se determina in raport strict cu definitia sa initiala.

Se reaminteste faptul ca in cadrul algoritmului se incearca alcatuirea perechilor, selectand pe b I[1,n] si pe f unde f = PrefBaieti[b,o] adica f este cea de-a o-a clasata in lista de preferinte a lui b.

In general, se presupune ca stabilitatea este predominanta si in continuare se incearca gasirea surselor de perturbatie posibile. In acest sens exista doua posibilitati:

(1) Presupunand ca baiatului b i-a fost repartizata fata f, ar putea exista o fata fp, preferata lui f de catre b (f fiind perechea repartizata lui b), care la randul ei prefera pe b perechii sale actuale b1 [5.h (1)].

(2) Presupunand ca fata f a fost repartizata baiatului b, ar putea exista un baiat bp preferat lui b de catre f (f fiind perechea repartizata lui b), baiat care la randul sau prefera pe f perechii f1 repartizate lui [5.h (2)].

(1) b ----> f

b1 ----> fp

y[fp] [5.h]

(2) f ----> b

f1 ----> bp

x[bp]

Initial se urmareste sursa (1) de perturbatie in vederea determinarii instabilitatii:

Pentru toate fetele fp care au ordinul de preferinta mai mic in lista lui b (adica sunt mai preferate) decat fata f repartizata lui, se verifica daca nu cumva vreuna il prefera mai mult pe b decat perechea ce i-a fost repartizata.

Pentru aceasta se compara ordinele OBF[fp,b] si OBF[fp,y[fp]] pentru toate fetele fp preferate lui f de catre b , adica pentru toate fp = PrefBaieti[b,i] astfel incat 1  i < o , unde o este ordinul de preferinta al fetei f repartizate lui b.

De fapt, toate aceste fete sunt deja distribuite in perechi, deoarece oricare dintre ele ar fi fost nedistribuita, ar fi fost repartizata lui b anterior.

Se face precizarea ca un ordin de preferinta cu valoare mai mare inseamna o preferinta mai slaba.

Rezultatul comparatiei este variabila booleana s. Atata vreme cat s ramane true relatia este stabila.

Procesul descris poate fi formulat printr-o simpla cautare liniara [5.i].

s:= true; i:= 1;

WHILE (i<o) AND s DO [5.i]

BEGIN

fp:= PrefBaieti[b,i]; i:= i+1;

IF NOT FNealeasa[fp] THEN

s:= OBF[fp,b]>OBF[fp,y[fp])

END;

In continuare se urmareste sursa (2) de perturbatie:

Pentru toti baietii bp care au ordinul de preferinta in lista fetei f mai mic ca si ordinul baiatului b caruia i-a fost repartizata, se verifica daca nu cumva vreunul o prefera mai mult pe f decat perechea lui actuala.

In acest scop sunt investigati toti baietii preferati bp = PrefFete[f,i] pentru i < OBF[f,b].

In mod analog ca si la cealalta sursa de perturbatie, este necesara compararea ordinelor OFB[bp,f] si OFB[bp,x[bp]].

Vor trebui insa evitate comparatiile care se refera la baietii bp carora inca nu le-au fost repartizate fete. Testul care realizeaza acest lucru este bp<b, deoarece tuturor baietilor care-l preced pe b li s-au repartizat deja perechi.

Rezultatul comparatiei este tot variabila booleana s care atata vreme cat ramane true relatia este stabila.

Secventa de cod care implementeaza verificarea celei de-a doua surse de perturbatie apare in [5.j].

i:= 1; lim:= OBF[f,b];

WHILE (i<lim) AND s DO [5.j]

BEGIN

bp:= PrefFete[f,i]; i:= i+1;

IF bp<b THEN s:= OFB[bp,f]>OFB[bp,x[bp]]

END;

Algoritmul complet apare in [5.k].

PROGRAM RelatieStabila;

CONST n=8;

TYPE TipBaiat = 1..n; TipFata = 1..n; TipOrdin = 1..n;

VAR b: TipBaiat; f: TipFata; o: TipOrdin;

PrefBaieti: ARRAY[TipBaiat,TipOrdin] OF TipFata;

PrefFete: ARRAY[TipFata,TipOrdin] OF TipBaiat;

OFB: ARRAY[TipBaiat,TipFata] OF TipOrdin;

OBF: ARRAY[TipFata,TipBaiat] OF TipOrdin;

x: ARRAY[TipBaiat] OF TipFata;

y: ARRAY[TipFata] OF TipBaiat;

FNealeasa: ARRAY[TipFata] OF boolean;

PROCEDURE Afiseaza;

VAR b1: TipBaiat;

ob,of:integer;

BEGIN [5.k]

ob:= 0; of:= 0;

FOR b1:=1 TO n DO

BEGIN

Write(x[b1]);

ob:= ob+OFB[b1,x[b1]]; of:= of+OBF[x[b1],b1]

END;

Writeln(ob,of)

END;

PROCEDURE Incearca(b:baiat);

VAR o: TipOrdin; f: TipFata;

FUNCTION Stabila: boolean;

VAR bp: TipBaiat; fp: TipFata;

i,lim: TipOrdin; s: boolean;

BEGIN

s:= true; i:= 1;

WHILE (i<o) AND s DO

BEGIN

fp:= PrefBaieti[b,i]; i:= i+1;

IF NOT FNealeasa[fp] THEN

s:= OBF[fp,b]>OBF[fp,y[fp]]

END;

i:= 1; lim:= OBF[f,b];

WHILE (i<lim) AND s DO

BEGIN

bp:= PrefF[f,i]; i:= i+1;

IF bp<b THEN s:= OFB[bp,f]>OFB[bp,x[bp]]

END;

Stabila:= s

END;

BEGIN

FOR o:=1 TO n DO

BEGIN

f:= PrefBaieti[b,o];

IF FNealeasa[f] THEN

IF Stabila THEN

BEGIN

x[b]:= f; y[f]:= b; FNealeasa[f]:= false;

IF b<n THEN

Incearca(Succ(b))

ELSE

Afisare;

FNealeasa[f]:= true

END

END

END;

BEGIN

FOR b:=1 TO n DO

FOR o:=1 TO n DO

BEGIN

Read(PrefBaieti[b,o]);

OFB[b,PrefBaieti[b,o]]:=o

END;

FOR f:=1 TO n DO

FOR o:=1 TO n DO

BEGIN

Read(PrefFete[f,o]); OBF[f,PrefFete[f,o]]:=o

END;

FOR f:=1 TO n DO FNealeasa[f]:= true;

Incearca(1)

END

Pentru datele de intrare din fig.5.a se obtin solutiile stabile din figura 5.b.

Programul are la baza un algoritm cu revenire din categoria celor tratati in acest paragraf.

Eficienta sa depinde in primul rand de gradul de sofisticare al solutiei de reducere a parcurgerii arborelui cautarilor. Exista si alte metode mai eficiente decat cea propusa [MW71].

Algoritmii de genul celor prezentati care genereaza toate solutiile posibile ale unei probleme sub incidenta anumitor constrangeri, sunt adesea utilizati in selectarea uneia sau mai multor solutii optime intr-un sens precizat.

In cazul de fata poate interesa spre exemplu solutia cea mai favorabila pentru baieti, pentru fete, sau pentru toti.

In tabela din fig.5.b apare suma ordinelor tuturor fetelor alese din listele de preferinte ale perechilor lor baieti (ob)si suma ordinelor tuturor baietilor alesi din listele de preferinte ale pe fetelor (of) pentru fiecare solutie in parte.

Acestea sume se calculeaza conform relatiilor [5.l].

ob:= of:= [5.l]

Solutia cu cea mai mica valoare pentru ob se numeste solutia stabila optima pentru baieti iar solutia cu cea mai mica valoare pentru of solutia stabila optima pentru fete.

Datorita strategiei de lucru adoptate in algoritm este evident ca se obtine la inceput solutia optima pentru baieti, iar cea pentru fete la sfarsit. In acest sens algoritmul favorizeaza baietii.

Acest lucru poate fi insa usor evitat daca se schimba rolul baietilor si al fetelor respectiv se interschimba PrefFete cu PrefBaieti si OFB cu OBF.

Fig.5.b. Solutii ale programului RelatieStabila

6. Problema selectiei optime

Urmatorul exemplu de algoritm cu revenire reprezinta o extensie ale celor anterioare.

Astfel, intr-o prima etapa utilizand principiul revenirii s-a determinat o singura solutie pentru o anumita problema de tip (n,m) (turneul calului sau problema plasarii celor 8 regine).

In a doua etapa s-a abordat problema aflarii tuturor solutiilor unei probleme tip (n,m) (generalizarea plasarii celor 8 regine si relatia stabila).

In continuare se propune aflarea solutiei optime.

In acest scop este necesar sa fie generate toate solutiile posibile si pe parcursul procesului de generare sa fie retinuta cea optima intr-un anumit sens.

Presupunand ca optimul este definit in termenii unei functii cu valori pozitive f(s), algoritmul cautat deriva din modelul destinat aflarii tuturor solutiilor unei probleme de tip (n,m) [4.a] in care afirmatia *evidentiaza solutia se inlocuieste cu secventa [6.a].

IF f(solutie)>f(optim) THEN optim:= solutie [6.a]

Variabila optim inregistreaza cea mai buna solutie intalnita pana la momentul curent si ea trebuie initializata in mod corespunzator.

Pentru a nu fi recalculata de fiecare data, valoarea lui f(optim) se pastreaza de regula intr-o variabila auxiliara.

Un exemplu cu caracter general al aflarii solutiei optime este urmatorul:

Se cere sa se gaseasca maniera optima de selectie a unei multimi date de obiecte, supuse unor constrangeri.

Selectionarile care constituie solutii acceptabile, se construiesc in mod gradat, examinand obiectele individuale ale multimii de baza.

Procedura Incearca [6.b], descrie procesul de investigare al obiectelor multimii in vederea selectiei, potrivit solutiei.

Procedura se apeleaza recursiv (pentru a investiga obiectul urmator) pana la parcurgerea tuturor obiectelor.

Se precizeaza ca examinarea unui obiect (numit candidat) se poate termina in doua moduri:

Fie cu includerea obiectului investigat in solutia curenta,

Fie cu excluderea sa.

Din acest motiv utilizarea instructiunilor repetitive REPEAT sau FOR nu-si are sensul, cele doua situatii specificandu-se in mod explicit [6.b].

PROCEDURE Incearca(i: TipObiect);

BEGIN

IF *incluziunea este acceptabila THEN

BEGIN

*include cel de‑al i‑lea obiect;

IF i<n THEN

Incearca(i+1)

ELSE [6.b]

*verifica optimalitatea;

*elimina al i‑lea obiect

END;

IF *excluziunea este acceptabila THEN

IF i<n THEN

Incearca(i+1)

ELSE

*verifica optimalitatea

END;

Se presupune ca obiectele sunt numerotate cu 1,2,,n.

Pornind de la acest model se obtin 2ⁿ multimi selectate posibile.

Este necesar insa sa fie introduse criterii corespunzatoare care sa reduca in mod drastic numarul candidatilor investigati avand in vedere faptul ca se cauta selectia optima.

Pentru lamurirea acestor aspecte se va particulariza in continuare exemplul.

Specidicarea problemei:

Se considera un set de n obiecte A₁,A₂,,A_n , fiecare fiind caracterizat prin greutatea sa g si prin valoarea v.

Se cere sa se genereze setul optim de obiecte constand dintr-o selectie a celor n obiecte, selectie care este afectata de una sau mai multe constrangeri.

Se defineste drept set optim acel set care are cea mai mare suma a valorilor componentelor

Se precizeaza ca constrangerea se refera la limitarea sumei greutatilor componentelor.

Aceasta este bine cunoscuta problema a calatorilor (knapsack problem), care isi pregatesc bagajele selectand lucruri dintr-o multime n, astfel incat:

Valoarea lor (de intrebuintare) sa fie maxima

Iar greutatea lor totala sa nu depaseasca o anumita limita.

Rezolvarea problemei incepe cu etapa stabilirii structurilor de date [6.c].

TYPE TipIndice = 1..n;

TipObiect = RECORD

g,v: integer

END;

VAR obiecte: ARRAY[TipIndice] OF TipObiect; [6.c]

limg,vtot,vmax: integer;

s,sopt: SET OF TipIndice;

Variabilele limg si vtot precizeaza greutatea limita respectiv valoarea totala a celor n obiecte, ele fiind constante pe parcursul intregului proces de selectie.

Variabila s reprezinta selectia curenta a obiectelor, in care fiecare obiect este reprezentat prin numele sau (indice).

sopt este selectia optima iar vmax valoarea sa.

In continuare se vor preciza criteriile de acceptare ale unui obiect in selectia curenta.

(1) In ceea ce priveste includerea:

Un obiect este selectabil daca el se incadreaza in toleranta de greutate.

Daca nu se incadreaza, se poate opri cautarea altor obiecte pe ramura respectiva a arborelui de cautare.

(2) In ceea ce priveste excluderea:

Criteriul de acceptare al excluderii (cel care permite continuarea construirii selectiei curente), este acela conform caruia valoarea potentiala finala la care s-ar putea ajunge fara a include candidatul curent in selectie, nu este mai mica decat optimul intalnit pana in prezent.

Neincluderea candidatului curent reprezinta practic excluderea sa din selectie.

In cazul in care aceasta valoare e mai mica decat optimul curent, procesul de cautare poate conduce si la alte solutii, singur insa nu la una optima, deci cautarea in pasul curent nu este fructificabila, ca atare este abandonata.

In baza acestor doua conditii se precizeaza elementele relevante care urmeaza sa fie determinate in fiecare pas al procesului de selectie:

(1) Greutatea totala gt a selectiilor executate pana in prezent.

Variabila gt se initializeaza cu valoarea 0, careia i se adauga de fiecare data greutatea obiectului inclus in selectia curenta.

Conditia *incluziunea este acceptabila este ca noua greutate totala gt sa nu depaseasca limita de greutate limg [6.d].

(2) Valoarea potentiala vp care mai poate fi atinsa de catre selectia curenta s.

Initial vp ia valoarea maxima posibila vtot obtinuta prin insumarea valorilor tuturor celor n obiecte ale multimii.

La fiecare excludere din vp se scade valoarea obiectului exclus.

Conditia *excluziunea este acceptabila este adevarata daca noua valoare a lui vp ramane mai mare ca vmax unde vmax este valoarea corespunzatoare solutiei optime determinate pana in prezent [6.e].

Explicatia este urmatoarea: chiar eliminand din selectie obiectul curent, valoarea potentiala la care s-ar mai putea ajunge este mai mare decat cea a solutiei optime curente, adica selectia curenta poate conduce la o solutie optima.

Aceste entitati (gt,vp) sunt declarate ca parametri ai procedurii Incearca.

gt + obiecte[i].g <= limg [6.d]

vp - obiecte[i].v > vmax [6.e]

Spre a evita reevaluarea periodica a diferentei vp-obiecte[i].v, aceasta se noteaza cu vp1.

Verificarea optimalitatii si inregistrarea solutiei optime apare in secventa [6.f].

IF vp>vmax THEN

BEGIN

sopt:= s; vmax:= vp [6.f]

END;

Ultima secventa este bazata pe rationamentul ca valoarea potentiala devine valoare efectiva, de indata ce au fost tratate toate cele n obiecte.

Programul integral apare in [6.g]. Exprimarea simpla a incluziunii si excluziunii se datoreaza utilizarii operatorilor specifici ai tipului multime SET.

PROGRAM SelectieOptima;

CONST n=10;

TYPE TipIndice = 1..n;

TipObiect = RECORD

g,v: integer

END;

VAR i: TipIndice;

obiecte: ARRAY[TipIndice] OF TipObiect;

limg,vtot,vmax: integer;

g1,g2,ratia: integer;

s,sopt: SET OF TipIndice;

z: ARRAY[boolean] OF char; [6.g]

b: boolean;

PROCEDURE Incearca(i: TipIndice; gt,vp: integer);

VAR vp1: integer;

BEGIN

IF gt+obiect[i].g<=limg THEN

BEGIN

s:= s+[i];

IF i<n THEN

Incearca(i+1,gt+obiecte[i].g,vp)

ELSE

IF vp>vmax THEN

BEGIN

vmax:= vp;

sopt:= s

END;

s:= s‑[i]

END;

vp1:= vp‑obiecte[i].v;

IF vp1>vmax THEN

BEGIN

IF i<n THEN

Incearca(i+1,gt,vp1)

ELSE

BEGIN

vmax:= vp1;

sopt:= s

END

END

END;

BEGIN

vtot:= 0;

FOR i:=1 TO n DO

WITH obiecte[i] DO

BEGIN

Read(g,v);

vtot:= vtot+v

END;

Read(g1,g2,ratia);

z[true]:= '*';

z[false]:= ' ';

Write(' Greutate ');

FOR i:=1 TO n DO Write(' ' ,obiecte[i].g);

Writeln; Write(' Valoare ');

FOR i:=1 TO n DO Write(' ' ,obiecte[i].v);

Writeln;

REPEAT

limg:= g1;

vmax:= 0;

s:= [];

sopt:= [];

Incearca(1,0,vtot);

Write(' ',limg);

FOR i:=1 TO n DO

BEGIN

b:= i IN sopt;

Write(' ',z[b])

END;

Writeln;

g1:= g1+ratia

UNTIL g1>g2

END

In fig.6.c sunt listate rezultatele executiei programului cu limita de greutate cuprinsa in intervalul 10

Fig.6.c. Rezultatele executiei programului SelectieOptima

Algoritmii care se bazeaza pe tehnica revenirii si care utilizeaza un factor de limitare care restrange cresterea arborelui potential de cautare, se mai numesc si algoritmi de tip 'inlantuie si limiteaza' ('branch and bound algorithms').