cap. 5-cti

66
V. Metode generale de proiectare a algoritmilor şi programelor Metoda Divide and Conquer(Tehnica divizării) Metoda Greedy Metoda Backtracking(Algoritmi cu revenire)

Upload: catalin-manole

Post on 24-Oct-2015

39 views

Category:

Documents


2 download

TRANSCRIPT

Page 1: Cap. 5-CTI

V. Metode generale de proiectare a

algoritmilor şi programelor

� Metoda Divide and Conquer(Tehnica

divizării)

� Metoda Greedy

� Metoda Backtracking(Algoritmi cu revenire)

Page 2: Cap. 5-CTI

Metode generale de proiectareIntroducere

� În teoria şi practica programării există un număr foarte mare de probleme pentru care trebuie găsite rezolvări. Din totalitatea acestor probleme se disting clase de probleme similare. Pentru problemele dintr-o asemenea clasă se poate aplica aceeaşi metodă generală de rezolvare, evident cu mici ajustări care depind de problema concretă.

� În timp s-au cristalizat mai multe metode generale de rezolvare a problemelor. Programatorii experimentaţi stăpânesc foarte bine aceste metode generale şi le aplică în mod automat atunci când au posibilitatea. Vom prezenta în continuare trei asemenea metode şi anume: Divide and Conquer, Greedy şi Backtracking. Se

recomandă studiul foarte atent al acestor metode, înţelegerea contextului în care ele se pot aplica şi însuşirea lor în asemenea mod încât aplicarea să poată deveni un automatism.

Page 3: Cap. 5-CTI

Metoda Divide and ConquerExplicarea numelui

� Numele acestei metode de rezolvare a problemelor de programareprovine din dictonul latindivide et impera. Semnificaţia esteurmătoarea: atunci când avem de rezolvat o problemă pe care, din diverse motive, o considerăm dificilă, o împărţim în mai multesubprobleme care să se poată rezolva mai uşor. După rezolvarea subproblemelor vom combina soluţiile lor pentru a obţine soluţia întregii probleme.� Metoda de rezolvareDivide and Conquerse poate aplica la acele probleme care se pot descompune în subprobleme de aceeaşinatură cu problema principală, dar de dimensiuni mai mici. � Se poate pune întrebarea : Cum rezolvăm subproblemele?. Răspunsul este: În acelaşi mod în care am rezolvat problema principală. => Metoda Divide and Conquer se pretează foarte bine la implementări recursive.

Page 4: Cap. 5-CTI

Metoda Divide and ConquerTehnica divizării - principii

� Este o metodă fundamentală de proiectare a algoritmilorcare poate să conducă la soluţii deosebit de eficiente. � Principiul de bază al acestei tehnici este acela de a descompune în mod repetat o problemă complexă în două sau mai multe subprobleme de acelaşi tip, urmată de combinarea soluţiilor acestor subprobleme pentru a obţine soluţia problemei iniţiale. � Întrucât subproblemele rezultate din descompunere sunt de acelaşi tip cu problema iniţială, metoda se exprimă în mod natural printr-o funcţie recursivă.� Apelul recursiv se continuă până în momentul în care subproblemele devin banale şi soluţiile lor evidente.

Page 5: Cap. 5-CTI

Metoda Divide and ConquerFuncţia recursivă - pseudocod

void Divide(* parametri care definesc o problema) {if (* problema este una triviala) {

* rezolva problema in mod direct;* returneaza rezultatele;}

else{* imparte problema in subprobleme;for( fiecare subproblema )

* apeleaza Divide(subproblema);* combina rezultatele subproblemelor;* returneaza rezultatele pentru problema;

}}

Page 6: Cap. 5-CTI

Metoda Divide and ConquerDeterminarea recursivă a elementelor min şi max

� Se dă un şir de n numere reale {x0, x1, ..., xn-1}. Să se determine valoareaminimă şi valoareamaximă din acestşir de numere. � Putem aplica tehnicaDivide and Conquer, împărţind şirul de numere în două părţi. Determinăm minimul şi maximul pentrufiecare din cele două părţi, iar pe urmă determinăm maximulglobal prin compararea celor două maxime parţiale şi minimulglobal prin compararea celor două minime parţiale. � Pentru implementare vom defini o funcţie recursivă care va căuta minimul şi maximul într-o secvenţă a şirului. Iniţial vom apela această funcţie pentru întregul şir. Funcţia se va apela pe ea însăşi recursiv, pentru jumătatea stângă şi pentru jumătatea dreaptă a secvenţei .

Page 7: Cap. 5-CTI

Metoda Divide and ConquerDeterminarea recursivă a elementelor min şi max

#include <stdio.h>

/* Declaram sirul de numere direct in cod. Alternativ, el poate fi citit de la tastatura sau din fisier. */

#define N 10int x[ ] = {10, 5, 23, -11, 4, 2, 0, -6, 66, 40};int comp = 0; /*Numara cate comparatii se fac in total. */

/* Functie care determina minimul si maximul dintr-osecventa a sirului de numere. Secventa este delimitata de indicii "st" si "dr". Valorile minima si maxima gasite vor fi returnate prin pointerii "min" si respectiv "max" primiti ca si parametri. */

Page 8: Cap. 5-CTI

Metoda Divide and ConquerDeterminarea recursivă a elementelor min şi max

void minmax(int st, int dr, int *min, int *max) {

int mijloc, min_st, max_st, min_dr, max_dr;printf("Caut in secventa [%d..%d].\n", st, dr);

if (st == dr) {/* Daca secventa contine un singur numar, atunci el este atat minim cat si maxim. */

*min = x[ st ];*max = x[ st ]; }

else if (st == dr - 1) {

/*Daca secventa contine doua numere, atunci facem o comparatie pentru a gasi minimul si maximul. */

Page 9: Cap. 5-CTI

Metoda Divide and ConquerDeterminarea recursivă a elementelor min şi max

comp++;if (x[ st ] < x[ dr ]){

*min = x[ st ]; *max = x[ dr ]; }else {

*min = x[ dr ]; *max = x[ st ]; } }else {

/* Daca avem mai multe numere, atunci divizamproblema in subprobleme. */mijloc = (st + dr) / 2;minmax(st, mijloc, &min_st, &max_st);minmax(mijloc+1, dr, &min_dr, &max_dr);

Page 10: Cap. 5-CTI

Metoda Divide and ConquerDeterminarea recursivă a elementelor min şi max

/* Combinarea rezultatelor partiale. Comparamminimele partiale si maximele partiale intre ele. */comp++;if (min_st < min_dr)

*min = min_st;else

*min = min_dr;comp++;if (max_st > max_dr)

*max = max_st;else

*max = max_dr; } }

Page 11: Cap. 5-CTI

Metoda Divide and ConquerDeterminarea recursivă a elementelor min şi max

int main(void) {int i, min, max; printf("Avem %d numere.\n", N);for (i=0; i<N; i++) /* Afisam sirul de numere. */

printf("%d ", x[ i ]);printf("\n\n");minmax(0, N-1, &min, &max);/* Apelam functia recursiva.*/printf("\nMinimul este %d.\n", min);printf("Maximul este %d.\n", max);printf("Comparatii facute: %d.\n", comp);return 0; }

Page 12: Cap. 5-CTI

Metoda Divide and ConquerProblema Turnurilor din Hanoi

� Se dau trei tije notate cu a, b, c. Pe tijaa sunt ordonate discuri în ordinecrescătoare. Să se realizeze programul C care mută toate cele n discuri de pe tijaa pe tijab folosind tijac ca auxiliară, astfel încât, în final,discurile să fie ordonate tot crescător. În timpul operaţiilor de mutare esteinterzisă plasarea unui disc mai mare peste unul mai mic.� Problema se poate codifica prin următorul cvartet : (n,a,b,c). Dacă am găsi o modalitate de a mutan-1discuri de pe tijaa pe tija intermediară c, atunci am putea să mutăm discul cel mai mare de pe tijaa pe tijab. Peurmă ar trebui să aducem celen-1discuri de pe tijac pe tijab şiproblema ar fi rezolvată. Pentru a mutan-1discuri de pe tijaa pe tijac, putem folosi ca tijă intermediară tija b. La fel, pentru a muta înapoi celen-1discuri de pe tijac pe tijab, putem folosi ca tijă intermediară, tija a. � Putem reformula cele de mai sus în felul următor: problema (n,a,b,c) se rezumă la problema (n-1,a,c,b), urmată de mutarea discului de diametrumaxim de pea peb, urmată de problema (n-1,c,b,a).

Page 13: Cap. 5-CTI

Metoda Divide and ConquerProblema Turnurilor din Hanoi

void hanoi (int n, char t_initial, char t_final, char t_intermediar) {if (n > 1) {

/* Daca avem mai mult de un disc de mutat, atunci descompunem problema in subprobleme. */hanoi(n-1, t_initial, t_intermediar, t_final);printf("%c -> %c\n", t_initial, t_final);hanoi(n-1, t_intermediar, t_final, t_initial); }

else {/* Daca avem un singur disc de mutat, atunci il mutam direct. La acest nivel problema are o rezolvare triviala*/printf("%c -> %c\n", t_initial, t_final); }}

Page 14: Cap. 5-CTI

GreedyExplicarea numelui

� În limba engleză cuvântulgreedyînseamnă lacom. Algoritmii de tip greedy sunt algoritmi “lacomi”: ei urmăresc să construiască într-un mod cât mai rapid soluţia problemei.

� Algoritmii de tip greedy se caracterizează prin luarea unordecizii rapide care duc la găsirea unei soluţii a problemei. Nu întotdeauna asemenea decizii rapide conduc la o soluţieoptimă, dar vom vedea că există anumite tipuri de problemeunde se pot obţine soluţii optime sau foarte apropiate de optim.

Page 15: Cap. 5-CTI

GreedyPrincipii

� Metoda Greedy se aplică la acele probleme la care, dându-se mulţimea A a datelor de intrare, se cere să se determine o submulţime B a sa, care trebuie să îndeplinească anumite condiţii pentru a fi acceptată ca soluţie posibilă. � În general, există mai multe soluţii posibile. Dintre acestea se pot selecta, conform unui anumit criteriu, nişte submulţimi B* care reprezintă soluţii optime ale problemei. Scopul este acela de a găsi una dintre mulţimile B*. Dacă acest lucru nu este posibil, atunci scopul este găsirea unei mulţimi B care să fie cât mai aproape de mulţimile B*, conform criteriului de optimalitate impus. Soluţiile posibile au următoarea proprietate:

• dacă B este o soluţie posibilă atunci orice submulţime a sa, inclusiv mulţimea vidă este, de asemenea, soluţie posibilă.

Page 16: Cap. 5-CTI

GreedyPrincipii

� Din proprietatea de mai sus rezultă și modul practic, de construire, al mulţimii B: Iniţial se porneşte cu mulţimea vidă (B = Φ). Urmează un şir de decizii. Fiecare decizieconstă în alegerea unui element din mulţimeaA, analiza lui şi eventual introducerea lui în mulţimeaB. În funcţie de modul în care se iau aceste decizii, mulţimeaB se va apropia mai mult sau mai puţin de soluţia optimă B*. Încazul ideal vom aveaB = B*.

� La fiecare pas se analizează câte un element din mulţimeaA şi se decide dacă să fie sau nu inclus în mulţimeaB care se construieşte. Astfel se progresează de la Φ cu un sir de mulţimi intermediare (Φ, B0, B1, B2, ...), până când se obţine o soluţie finală B.

Page 17: Cap. 5-CTI

GreedyStrategii

� Metoda Greedy nu urmăreşte să determine toate soluţiile posibile ca să aleagă apoi pe cea optimă, conform criteriului de optimizare dat. O astfel de metodă, care ar face căutare exhaustivă în spaţiul soluţiilor și care ar determina, cu exactitate, soluția optimă necesită, de regulă, un efort de calcul foarte mare. Metoda Greedy, în schimb, nu necesită nici timp de calcul, nici spaţiu de memorie mare, comparativ cu metodele exacte. � Pe baza proprietăţii enunţate anterior, la fiecare pas al metodei există o soluţie posibilă care se va îmbogăţi cu un nou element, ales astfel încât şirul soluţiilor posibile să conveargă spre soluţia optimă. Noua soluţie "înghite" elementul cel mai "promiţător".

Page 18: Cap. 5-CTI

GreedyStrategia 1

Există mai multe strategii prin care se poate implementa metoda Greedy. În continuare se prezintă două astfel de strategii care diferă prin ordinea de efectuare a unor operaţii.

� Se consideră că mulţimea datelor de intrare, A, are iniţial nelemente. B reprezintă, în orice moment, soluţia posibilă. Funcţia logică posibil are valoarea true dacă elementul selectat, transmis ca parametru, formează împreună cu mulţimea B o nouă soluţie posibilă. Verificările efectuate în această funcţie trebuie să rezulte din enunţul problemei.

Iniţial, B este mulţimea vidă. La fiecare pas al algoritmului se alege, într-un anumit fel, un element din A neales la paşii precedenţi (funcţia alege). Se adaugă acest nou element la soluţia posibilă anterioară, dacă prin această adăugare se obţine tot o soluţie posibilă.

Page 19: Cap. 5-CTI

GreedyStrategia 1

B = multimea vida;for (i=0; i<n; i++) {

x = alege( A);if (posibil( B ,x))

* adauga elementul x la multimea B;}Dificultatea la această primă variantă constă în scrierea funcţiei alege. Dacă funcţia alege este bine concepută, atunci putem fi siguri că soluţia B găsită este o soluţie foarte bună, apropiată de cea optimă sau chiar optimă. Dacă funcţia alege nu este foarte bine concepută, atunci soluţia B găsită va fi doar o soluţie posibilă şi nu va fi optimă. => Criteriul de selecţie implementat în funcţia alege,o poate apropia mai mult sau mai puţin de soluţia optimă B*.

Page 20: Cap. 5-CTI

GreedyStrategia 2

În anumite cazuri, ordinea în care trebuie considerate elementele din mulţimea A se poate stabili de la început (funcţia prelucreaza), obţinându-se, pe baza mulţimii A, un vector V cu n componente :

B = multimea vida;prelucreaza(A,V);for (i=0; i<n; i++) {

x = V[i];if (posibil(B,x))

* adauga elementul x la multimea B; }

La a doua variantă, dificultatea funcţiei alege nu a dispărut, ci s-a transferat funcţiei prelucreaza. Dacă prelucrarea mulţimii A este bine făcută, atunci se poate ajunge la o soluţie optimă. Altfel se va obţine doar o soluţie posibilă, mai mult sau mai puţin apropiată de optim.

Page 21: Cap. 5-CTI

GreedyProbleme de optimizare

� Un exemplu tipic de aplicare al metodei Greedy îl reprezintă problemele de optimizare. În acest tip de probleme, de

regulă, se cere să se selecteze din datele de intrare acele elemente care maximizează o funcţie de cost.

� Ideea generală a metodei este de a alege la fiecare pas acel

element care determină cea mai mare creştere a acestei funcţii.

Neanalizând influenţa corelaţiei dintre elemente asupra funcţiei de cost, metoda nu poate garanta că aceste maximizări locale, succesive, conduc întotdeauna la maximul globalaşteptat. Aceasta înseamnă că sunt situaţii în care metoda Greedy nu generează soluţia optimă, deşi aceasta există.

Page 22: Cap. 5-CTI

GreedyProbleme de optimizare - exemplu

� Se dă o mulţime X = {x0, ..., xn-1} cu elemente reale. Se cere să se determine o submulţime Y a sa astfel încât să fie maximă.

Se observă că o soluţie posibilă este orice submulţime a lui X având numai elemente pozitive, iar soluţia optimă este cea mai cuprinzătoare dintre aceste submulţimi, adică aceea care include toate elementele pozitive din X.

Se optează pentru strategia 2a metodei Greedy. Organizând de la bun început X şi Y ca vectori, funcţia prelucreaza nu mai este necesară în acest caz. Iniţializarea lui B pe Φ se reduce la atribuirea k = 0. Funcţia posibil este reprezentată prin condiţiax[i] > 0 iar operaţia de obţinere a unei noi soluţii posibile, prin adăugarea unui element din intrare este dată de operaţiile y[k] = x_ales şi k++.

∑∈

=Yy

yf

Page 23: Cap. 5-CTI

GreedyProbleme de optimizare - exemplu

k = 0;

suma = 0;for (i=0; i<N; i++) {

x_ales = x[i];if (x_ales >0) {

y[k] = x_ales;k++;

suma += x_ales;}

}

Page 24: Cap. 5-CTI

GreedyInterclasarea optimală a mai multor şiruri

� Se dau n şiruri S1, S2, ..., Sn de lungimi l1, l2, ..., ln. În cadrul fiecărui şir elementele sunt ordonate crescător. Se cere să se obţină un şir Scu l1+l 2+...+l n elemente, ordonate de asemenea crescător, conţinând elementele cumulate ale celor n şiruri iniţiale. Se dispune de o funcţie capabilă să interclaseze două şiruri ordonate care i se transmit ca parametri.

Se cere, de asemenea, ca programul realizat să fie optim din punct de vedere al timpului total necesar pentru interclasare.

Optimizarea cerută se va reflecta la nivelul programului principal şi constă în determinarea ordinii optime în care trebuie efectuate interclasările astfel încât timpul total să fie minim.

Page 25: Cap. 5-CTI

GreedyInterclasarea optimală a mai multor şiruri

Din teoria legată de interclasarea şirurilor se cunoaşte faptul că timpul necesar pentru interclasarea a două şiruri ordonate, A şi B, de lungimi a şi resp. b, este proporţional cu a+b { Ø(a+b)}, rezultat din faptul că sunt necesare a+b deplasări de elemente.

Exemplu :

L = (90, 70, 40, 10)

t1 = (90+70) +(160+40) +(200+10) = 570 depl.

t2 = (10+40) +(50+70) +(120+90) = 380 depl.

Soluţie Greedy: se interclasează cele mai scurte două şiruri, rezultând n-1 şiruri; se interclasează apoi cele mai scurte două şiruri dintre cele rămase ş. a. m. d.

Page 26: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

TSP - Traveling Salesman Problem � Se consideră n puncte distincte. Se furnizează ca date de intrare distanţele dintre aceste puncte. Se cere să se determine un drum care să pornească dintr-un punct oarecare, să treacă o singură dată prin toate celelalte şi să se întoarcă în punctul iniţial, astfel încât lungimea drumului să fie minimă.� Toţi algoritmii care conduc la soluţia optimă în această problemă necesită timp de calcul exponenţial {Ø(2n)}.

Un algoritm care utilizează metoda Greedy (neoptimal) necesită pentru determinarea soluţiei un timp polinomial {Ø(n2)}. � Ideea pentru Greedy: se adaugă întotdeauna la drum acel punct pentru care distanţa faţă de punctul adăugat anterior este minimă şi nu este încă legat. După ce s-au cuprins în drum toate punctele se face legătura între ultimul punct şi primul.

Page 27: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

Exemplu :

3

1

4 25

1

1 4

27

Page 28: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

nod de plecare : 1

lungime drum = 13

3

1

4 25

1

1 4

27

Page 29: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

3

1

4 25

1

1 4

27

nod de plecare : 3

lungime drum = 9

Page 30: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

Distanţele între oraşe le memorăm într-un tabloubidimensionald. Distanţa între oraşele (i,j) va fi reprezentată de elementuldi,j al matricii.

În termeni Greedy, mulţimea iniţială A este mulţimea tuturor perechilor de oraşe. Mulţimea B care trebuie găsită va

conţine o parte din aceste perechi de oraşe, şi anume acele perechi care, înlănţuite, să formeze un drum ce trece prin toate

oraşele.

Page 31: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

În implementare nu vom lucra cu mulţimea A sub

această formă explicită de perechi de oraşe, ci vom folosi matricea distanţelor d. De asemenea, drumul comis-voiajorului nu îl vom păstra sub formă de perechi de oraşe, ci sub forma unui șir al oraşelor, numitdrumcare va conţine indicii oraşelor parcurse, în ordinea parcurgerii.

Pentru a şti care oraşe au fost parcurse, facem o

marcare logică a oraşelor folosind un tablou unidimensional vizitat. Elementele din acest tablou care au valoarea 1 reprezintă oraşe vizitate.

Page 32: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

#include <stdio.h>#define N_MAX 30 /* Numarul maxim de orase. */#define MINIM 10000 /* Constanta care se foloseste

ca valoare de initializare la cautarea minimului. */

int n; /* Numarul de orase. */int d[N_MAX][N_MAX]; /* Matricea distantelor dintre

orase. */int drum[N_MAX]; /* Drumul comis voiajorului. Contine

indicii oraselor in ordinea in care sunt ele parcurse. */

int vizitat[N_MAX]; /* Vector care memoreaza ce oraseau fost vizitate. */

Page 33: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

/*Functia alege urmatorul urmatorul oras care sa fie vizitat. */void alege(int ultimul, int *min, int *j_min) {

int j; /* Cautam drumul minim pana la orasele neparcurse inca. */

*min = MINIM; *j_min = -1;for (j=0; j<n; j++)

if (!vizitat[ j ]) {if (d[ ultimul ][ j ] < *min) {

*min = d[ ultimul ][ j ];*j_min = j;} }

}

Page 34: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

int main(void) {FILE *fin; int i, j, count, cost, min, j_min;

fin = fopen("comis.in", "rt"); if (!fin) {printf("Eroare: nu pot deschide fisierul.\n");

return -1; }fscanf(fin, "%d", &n); /* Citim datele din fisier. */

for (i=0; i<n; i++)for (j=0; j<n; j++)

fscanf( fin, "%d", &(d[ i ][ j ]));

Page 35: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

printf("Avem %d orase.\n", n);printf("Distantele dintre orase sunt:\n");for (i=0; i<n; i++) {

for (j=0; j<n; j++)printf("%d ", d[ i ][ j ]);

printf("\n"); }printf("\n");for (i=0; i<n; i++)

vizitat[i] = 0; /* Initial nici un oras nu este vizitat. *//* Primul oras vizitat este cel cu numarul "0". */drum[0] = 0; vizitat[0] = 1;count = 1; cost = 0;

Page 36: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

/* Parcurgem restul de n-1 orase. */

for (i=0; i<n-1; i++) {/* Alegem urmatorul oras care sa fie vizitat. */

alege(drum[count-1], &min, &j_min);printf("Am ales drumul (%d, %d) de cost %d.\n",

drum[count-1], j_min, min);drum[count] = j_min;

vizitat [j_min ] = 1;count++;

cost += min; }

Page 37: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

/* Parcurgem drumul de la ultimul oras vizitatcatre primul oras si actualizam costul total. */cost += d[drum[n-1]][0]; /* Afisam drumul parcurs. */printf("\nDrumul are costul %d si este:\n", cost);for (i=0; i<n; i++)

printf("%d ", drum[i]);printf("0\n");return 0;

}

Page 38: Cap. 5-CTI

GreedyProblema comis-voiajorului (TSP)

� Rezolvarea problemei comis-voiajorului, prin metoda prezentată, poate fi îmbunătăţită dacă se repetă algoritmul dat şi pentru alte puncte iniţiale (eventual pentru toate n), reţinându-se varianta de drum cu lungime minimă. Mai mult, dacă pentru un anumit punct iniţial se ajunge în situaţia ca lungimea drumului să depăşească lungimea minimă de până atunci, se poate abandona tratarea acelui lanţ, trecându-se la alt punct iniţial. Astfel, timpul cerut de această nouă variantă este cel mult Ø(n3).� Metoda prezentată pentru rezolvarea problemei comis-voiajorului se încadrează în categoria algoritmilor euristici .

Un algoritm este euristic dacă furnizează soluţii suficient de bune, dar nu neapărat optime, într-un timp rezonabil, mai mic decât cel necesar oricărui algoritm exact, cunoscut.

Page 39: Cap. 5-CTI

GreedyProblema conectării oraşelor cu cost minim

� Se dau un număr de n oraşe. Pentru diferite perechi de oraşe (i, j) i=1, 2, ... n şi j=1, 2, ... n, nu neapărat pentru toate perechile posibile, se furnizează, ca date de intrare, costurile legării lor directe (lungimea drumului, lungimea sau costul liniei telefonice de legătură, durata drumului dintre cele două oraşe etc.). Se cere să se construiască o reţea prin care fiecare oraş să fie legat cu toate celelalte direct sau indirect, astfel încât costul legăturilor să fie minim.� Se poate demonstra că soluţia cerută este un arbore (eliminând ciclurile se păstrează condiţiile problemei şi costul este, evident, mai mic).� Problema se mai numeşte şi problema arborelui parţial de cost minim (Minimum Spanning Tree) şi are un grad mare de generalitate : orice problemă în care soluţia este un arbore şi funcţia de cost este ataşată tranziţiilor (muchiilor) în arbore.

Page 40: Cap. 5-CTI

GreedyProblema conectării oraşelor cu cost minim

� O soluţie pentru construirea arborelui parţial de cost minim, care se bazează pe metoda Greedy, este algoritmul lui Prim .

Ideea algoritmului lui Prim : se porneşte dintr-un oraş

oarecare sau de la muchia de cost minim care leagă, de exemplu, cele mai apropiate două oraşe. Apoi, se adaugă în mod repetat, muchia de cost minim dintre cele rămase (nealese anterior) şi care nu formează cu precedentele un ciclu, adică se adaugă la reţea acel oraş, dintre cele nelegate, situat la cea mai mică distanţă faţă de unul (oarecare) dintre oraşele legate anterior.

� Se poate demonstra că arborele construit prin această strategie este într-adevăr de cost minim.

Page 41: Cap. 5-CTI

GreedyProblema conectării oraşelor cu cost minim

Să considerăm spre exemplu o reţea de 7 oraşe numerotate de la 0 la 6. Costurile de conectare a oraşelor sunt redate în figură.

Arborele minim este redat cu linii îngroşate. El a fost construit pas cu pas, conform procedeului descris mai sus. Iniţial arborele a fost vid. La primul pas s-a adăugat un nod arbitrar, şi anume nodul 0.

Page 42: Cap. 5-CTI

Metoda BacktrackingAlgoritmi cu revenire – explicarea numelui

� Pentru a înţelege semnificaţia cuvântului backtrackingvom reda definiţia din Cambridge Online Dictionary,http://dictionary.cambridge.org/:

to go back along a path you have just followed

� Ideea de bază este aceea de revenire pe calea parcursă. Algoritmii de tip backtracking încep să exploreze spaţiulsoluţiilor în mod exhaustiv, pe toate căile posibile. Atuncicând pe calea curentă de explorare se constată că nu mai suntşanse să se ajungă la o soluţie validă, se revine cu un pas înapoişi se abordează o altă cale de explorare.

� În concluzie, metoda Backtracking constă în efectuarea unor încercări repetate, în vederea găsirii soluţiilor, cu posibilitatea revenirii în caz de eşec.

Page 43: Cap. 5-CTI

Metoda BacktrackingAlgoritmi cu revenire - principii

� Soluţia se poate reprezenta sub forma unui vector X=(x0,x1, …, xn-1), X∈ S = S0 xS1x …x Sn-1, unde mulţimile S0 , …, Sn-1

sunt mulţimi finite. Pentru fiecare problemă concretă sunt date anumite relaţii între componentele x0,x1, …, xn-1 ale vectorului X, numite condiţii interne. Mulţimea S reprezintă spaţiul soluţiilor posibile. Soluţiile posibile care satisfac condiţiile interne se numesc soluţii rezultat .

În continuare, exprimăm condiţiile care trebuie satisfăcute sub forma unei funcţii logice notată:Solutie(x0,x1,...,xn-1). Un element X=(x0, x1, ..., xn-1) ∈ Seste soluţie a problemei dacă funcţia Solutie aplicată

componentelor lui X va returna valoarea true.

Page 44: Cap. 5-CTI

Metoda BacktrackingAlgoritmi cu revenire - principii

� Scopul algoritmului concret poate să fie determinarea

unei soluţii rezultat sau a tuturor soluţiilor rezultat, fie în scopul afişării lor, fie pentru a alege una optimă din

punctul de vedere al unor criterii de optimizare (minimizare sau maximizare).

� O metodă simplă de selectare a soluţiilor rezultat este aceea de a genera toate soluţiile posibile şi de a verifica satisfacerea condiţiilor interne (căutare exhaustivă în întreg spațiul soluțiilor posibile). Această metodă

necesită însă un timp de execuţie foarte mare şi nu se aplică decât rar în practică.

Page 45: Cap. 5-CTI

Metoda BacktrackingAlgoritmi cu revenire - principii

� Un algoritm backtracking performant, ca şi în cazul Greedy de altfel, evită generarea tuturor soluţiilor posibile. În acest scop, elementele vectorului X primesc, pe rând şi în ordine, valori. După asocierea unei valori lui xk se verifică îndeplinirea unor condiţii de continuarepentru secvenţa (x0, …, xk) şi numai apoi se trece la încercarea de asociere a unei valori pentru xk+1: funcţia Continuare(x0, x1, ..., xk) .

� Neîndeplinirea acestor condiţii ne arată, încă din această fază, că soluţia finală nu poate fi o soluţie rezultat. În cazul unui eşec la această verificare, se alege o altă valoare pentru xk∈ Sk sau, dacă Sk a fost epuizat, se micşorează k cu o unitate şi procesul de alegere se repetă.

Page 46: Cap. 5-CTI

Metoda BacktrackingProcedura generală - pseudocod

k = 0;while (k >= 0){

do {* alege urmatorul x[k] din multimea S[k];* evalueaza Continuare(x[0], x[1], ..., x[k]); }

while ( !Continuare(x[0], x[1], ..., x[k]) && (* mai sunt elemente de ales din multimea S[k]) );

if (Continuare(x[0], x[1], ..., x[k])) {if (k == n-1) {

if (Solutie(x[0], x[1], ..., x[n-1])) * afiseaza solutie; }else { k = k + 1; } }

else { k = k – 1; } }

Page 47: Cap. 5-CTI

Metoda BacktrackingAlgoritmi cu revenire - caracteristici

În concluzie:� Numele metodei (algoritmi cu revenire) provine de la revenirile care se efectuează în caz de eşec.

� Condiţiile de continuare derivă din condiţiile interneale problemei.

� Alegerea optimă a condiţiilor de continuare poate determina reducerea numărului de calcule (încercări) care urmează să fie efectuate (viteza programului).

� Acest proces de încercări repetate şi revenire în caz de eşec (cu reluarea altei valori şi continuare) se exprimă în mod natural şi în manieră recursivă.

Page 48: Cap. 5-CTI

Metoda BacktrackingSoluţia recursivă

� Se consideră că numărul elementelor care se pot examina la fiecare apel (cardinalitatea mulțimilor Sk) în vederea adăugării lor la soluţie, este fix (m), iar numărul componentelor soluţiei este de asemenea fix (n) :

void Incearca (int k) {int i;for(i=0; i<m; i++) {

* selectează elementul nr. i;if (* este acceptabil) {* înregistreaza elementul selectat;if (k<n-1)

Incearca (k+1);else * tipareşte soluţie;* şterge înregistrarea;} } }

Page 49: Cap. 5-CTI

Metoda BacktrackingProblema celor 8 regine (Eight Queens)

� Se cere să se realizeze programul care să plaseze opt regine pe o tablă de şah, astfel încât nici una dintre ele să nu le ameninţe pe celelalte. La jocul de şah, o regină “ameninţă” pe linii, coloane şi diagonale, pe orice distanţă.

Această problemă a fost investigată de Carl Friedrich Gauss în 1850 (care însă nu a rezolvat-o complet). Nici până în prezent problema nu are o soluţie analitică satisfăcătoare. În schimb ea poate fi rezolvată prin încercări, necesitând o mare cantitate de muncă, răbdare şi acurateţe (condiţii în care calculatorul se descurcă excelent).

Problema are 92 de soluţii din care, din motive de simetrie, doar 12 sunt diferite.

Problema poate fi uşor extinsă pentru n regine plasate pe o tablă pătrată cu n linii şi n coloane.

Page 50: Cap. 5-CTI

Metoda Backtracking8 regine – rezolvare

� Pe fiecare linie sau coloană de pe tablă se va afla o singură regină. Se va parcurge tabla de şah linie cu linie (k=0..7), iar în cadrul unei linii coloană cu coloană (i=0..7) şi se vor plasa reginele în acele pătrate care nu sunt în “priza reginelor” plasate anterior. Pentru parcurgerea tablei se va utiliza tehnica backtracking.� Deoarece pe fiecare linie a tablei de şah se poate găsi exact o regină, o soluţie rezultat se poate reprezenta sub forma unui vector C = (c0,..., c7) unde ck reprezintă coloana pe care se află regina de pe linia k (ck∈{0, …,7}).� Spaţiul soluţiilor posibile este produsul cartezian

S = C × C × C × C × C × C × C × C � Condiţiile interne, rezultă din regulile şahului şi sunt reprezentate de faptul că două dame nu se pot afla pe o aceeaşi coloană sau o aceeaşi diagonală.

Page 51: Cap. 5-CTI

Metoda Backtracking8 regine – organizarea tablei de şah

Tabla de şah:

7

6

5

4

3

2

1

0

76543210

k

i

Page 52: Cap. 5-CTI

Metoda Backtracking8 regine – condiţiile interne

Funcţia Solutie trebuie să verifice dacă nu existăregine care se află pe aceeaşi coloană sau dacă nucumva există regine care se atacă pe diagonală. Verificarea este simplă. Trebuie să verificăm că între elementele (c0, c1, c2, c3, c4, c5, c6, c7) nu există două care au aceeaşi valoare. Aceasta ar însemna că avem două regine pe aceeaşi coloană. Apoi mai trebuie să verificăm că ∀i,k ∈{0, 1, 2, 3, 4, 5, 6, 7}, |i-k| ≠ |ci-ck|. Aceasta este condiţia ca să nu existe două regine care se atacă pe diagonală. Verificări similare vor fi efectuate pe parcurs de funcţia Continuare.

Page 53: Cap. 5-CTI

8 RegineImplementarea programului

#include <stdio.h>

#include <stdlib.h>

#define N 8

#define INVALID -1

int main(void) {

int c[N];

int k, i;

int continuare, ataca;

int count = 0; // Numaram cate solutii sunt gasite

for (i=0; i<N; i++)

c[i] = INVALID; //Initializam toate elem. din vectorul c

Page 54: Cap. 5-CTI

8 RegineImplementarea programului

k = 0;while (k >= 0) {

/* Ne vom opri atunci cand am epuizat elem. din multimea C[k] sau atunci cand intalnim un element pentru care functia Continuare returneaza true. */

do {if (c[k] == INVALID)

// nu s-a incercat plasarea reginei de pe linia kc[k] = 0; // plasam regina de pe linia "k" pe coloana 0

else // incercam sa plasam regina pe urmatoarea col. c[k]++;

/* Daca nu am depasit numarul de coloane de pe linie, atunci trecem la evaluarea functiei Continuare. */

Page 55: Cap. 5-CTI

8 RegineImplementarea programului

if (c[ k ] < N) {/* Ne asiguram ca regina pe care vrem sa o plasam pe

linia "k" si coloana "c[k]" nu ataca nici una din reginele deja plasate*/

ataca = 0;for (i=0; !ataca && (i<k); i++) {

/* Verificam daca mai exista o regina pe aceeasi coloana*/if (c[ i ] == c[ k ])

ataca = 1;/*Verificam daca noua regina ataca alta, pe diagonala*/

else if (abs(i-k) == abs(c[ i ]-c[ k ]))ataca = 1; }

Page 56: Cap. 5-CTI

8 RegineImplementarea programului

/* Daca noua regina nu ataca nici una din reginele plasate anterior, atunci functia Continuare returneaza true(1), altfel returneaza false (0) */

if (!ataca)continuare = 1;

elsecontinuare = 0;

}/* Daca s-a depasit numarul coloanelor de pe o linie,

functia Continuare returneaza automat false. */else

continuare = 0; } while (!continuare && (c[k] < N));

Page 57: Cap. 5-CTI

8 RegineImplementarea programului

/* Daca am obtinut true (1), din functia Continuare, atunci consideram regina plasata si continuam algoritmul */

if (continuare) {/* Daca am plasat toate N reginele, atunci afisam solutia gasita. */

if (k == N-1) {

for (i=0; i<N; i++)printf("%d ", c[ i ]);

printf("\n"); count++; }

else k++; }

Page 58: Cap. 5-CTI

8 RegineImplementarea programului

/* S-au epuizat toate variantele de plasare a reginei de pe linia k. Marcam cu INVALID elementul c[ k ] sirevenim cu un pas inapoi pe calea de cautare, la reginak-1. */

else {c[ k ] = INVALID;k--; }

}printf("%d solutii\n", count); return 0;

}

Page 59: Cap. 5-CTI

Metoda Backtracking8 regine – algoritmul recursiv

void Incearca(int k){int i= -1;do {

i++;Succes =regina poate fi pusa in pozitia (k,i)if (Succes){

Ocupa; /*pune regina*/C[k] = i; /*memoreaza coloana*/if (k<7) Incearca(k+1);

else Tipareste;

Elibereaza; /*ia regina*/ }}while (i<7); }

Page 60: Cap. 5-CTI

Metoda BacktrackingCircuitului calului (Knight’s Tour)

� Fiind dată o tablă pătrată cu n X n elemente, se cere să se realizeze programul C pentru găsirea traseului care trece prin toate elementele tablei, începând cu cel de coordonate (i,j), utilizând săritura calului dată de regulile şahului. Prin fiecare element se va trece o singură dată.

Operaţia esenţială pe care o are de rezolvat algoritmul este executarea unei mişcări următoare sau constatarea că nu mai este posibilă o astfel de mişcare şi revenirea la mişcarea anterioară.

Caracteristica esenţială a acestui algoritm este aceea că înaintează spre soluţia finală pas cu pas, încercând şi înregistrând drumul parcurs. Dacă la un moment dat se observă că drumul ales nu conduce la soluţia dorită şi se blochează, se revine ştergând înregistrările paşilor până la proximul punct care permite o nouă alternativă de drum.

Page 61: Cap. 5-CTI

Metoda BacktrackingCircuitului calului – structurile de date

� Pentru o tablă de dimensiuneN vom memora

soluţiile într-un vector, c, de lungimeN*N.

� Fiecare element din vector va fi la rândul lui un vector cu două elemente, primul element va memora linia de pe tablă, iar al doilea element va memora coloana de pe tablă, corespunzătoare poziției respective:

int c [N*N][2];

� count –numărul de soluţii găsite

Page 62: Cap. 5-CTI

Metoda BacktrackingCircuitului calului – săritura

Noile coordonate, pentru o săritură, se calculează din cele curente adunând nişte valori fixe ±1, ±2, înregistrate în tablourile dx şi dy, şi care definesc cele opt mişcări viitoare (k=0..7)posibile dintr-un punct oarecare (x,y) :

21

30

C

47

56

x

y

u = x + dx [k]

v = y + dy [k]

Page 63: Cap. 5-CTI

Metoda BacktrackingCircuitului calului – programul

#include <stdio.h>

#define N 5

int dx [8] = {-1, -2, -2, -1, 1, 2, 2, 1};int dy [8] = {-2, -1, 1, 2, 2, 1, -1, -2};

int c[N*N][2];int count = 0;

Page 64: Cap. 5-CTI

Metoda BacktrackingCircuitului calului – programul

void Incearca(int pas) {int i, j, continuare;

if (pas == N*N) {for (i=0; i<pas; i++)

printf("(%d,%d) ", c[i][0], c[i][1]);printf("\n");count++; }

Page 65: Cap. 5-CTI

Metoda BacktrackingCircuitului calului – programul

elsefor (i=0; i<8; i++) {

c[pas][0] = c[pas-1][0] + dy [i];

c[pas][1] = c[pas-1][1] + dx [i];if ((c[pas][0]>=0) && (c[pas][0]<N) &&

(c[pas][1]>=0) && (c[pas][1]<N)) {

continuare = 1;for (j=0; continuare && (j<pas); j++)

if ((c[j][0]== c[pas][0]) && (c[j][1] == c[pas][1])) continuare = 0;

if (continuare) Incearca(pas+1); } } }

Page 66: Cap. 5-CTI

Metoda BacktrackingCircuitului calului – programul

int main(void){int i,j;for (i=0; i<N; i++)

for (j=0; j<N; j++){

c[0][0] = i;c[0][1] = j;Incearca(1);

}printf("%d solutii\n", count);return 0;

}