Metode de rezolvare a problemelor – căutarea în spațiul soluțiilor

GreedyBacktracking

? ??

?

Fie mulțimile , , o relație de ordine pe

spațiul soluțiilor

funcție de validare

mulțimea soluțiilor rezultat

funcții de validare parțială

▪ se poate adăuga un element cu .

Spațiul soluțiilor

Greedy – metoda optimului local

Metodă rapidă, de complexitate redusă, pentru obținerea unei soluții acceptabile (nu neapărat cea mai bună) La fiecare pas se alege cea mai bună cale în contextul local,

ignorînd contextul general Uneori soluția poate fi cea mai puțin dezirabilă

Este folosită atunci cînd găsirea celei mai bune soluții este prea costisitoare

Greedy – metoda optimului local

11

2233 44

55 6677

5

88

99

1111

1010

215

32 2647

9

12

41

5

20

18 21

1, 3, 6, 2, 5, 9, 11 -> 124

7

1, 4, 8, 11 -> 45

Greedy – metoda optimului local

Probleme rezolvate prin metoda Greedy

Problema poate fi imaginată ca o mulțime cu elemente

O soluție posibilă este o submulțime ( care îndeplinește o condiție dată ( este acceptabilă);

Pot exista mai multe submulțimi diferite acceptabile (soluții posibile), dintre care una este considerată soluție optimă, pe baza unui criteriu care trebuie maximizat (minimizat).

Greedy – metoda optimului local

Operații (nu sînt întotdeauna evidente)

Alegerea unui element candidat din mulțimea (

Verificarea acceptabilității elementului ales: adăugarea elementului la soluția parțială construită o menține acceptabilă sau o face inacceptabilă?

▪ este acceptabilă?

Adăugarea elementului ales la soluția parțială, dacă ea rămîne acceptabilă.

Greedy – metoda optimului local

Algoritm general

se primește mulțimea cu elemente

se inițializează soluția ca mulțime vidă

repetă de (maxim) ori

▪ alege un element candidat din mulțimea

▪ verifică dacă este soluție acceptabilă

▪ dacă da, adaugă la mulțimea :

se trimite mulțimea ca soluție

Cum se alege un element candidat?

Cum se verifică acceptabilitatea elementului candidat?

Variantă: prelucrare inițială a mulțimii A (sortare)

Greedy – metoda optimului local Exemple de probleme rezolvate prin algoritmi de tip Greedy:

Determinarea arborelui parțial de cost minim (soluția este întotdeauna optimă)

▪ Algoritmul lui Kruskal, algoritmul lui Prim

Problema rucsacului

▪ întreagă

▪ continuă

Interclasarea optimă a n vectori

Suma maximă dintr-o mulțime de numere

Plata unei sume (cu bancnotă unitate)

Problema paznicului

Determinarea unui produs de transpoziții

Algoritmul Dijkstra

Enunțuri complete în manual

Problema rucsacului (continuă)

// I: capacitate totala (q), nr. obiecte (n), capacitate ocupata (c),// cistig (v)// E: solutia xvoid Rucsac_c(float q, int n, float* c, float* x){ float qr; int i,j;

qr=q; for(i=0; i<n && qr>0; i++) if(qr>=c[i]) { x[i]=1; qr-=c[i]; //qr-=c[i]*x[i] } else { x[i]=qr/c[i]; qr=0; //qr-=c[i]*x[i] for(j=i+1;j<n;j++) x[j]=0; }}

Backtracking – căutare completă

Metodă lentă, costisitoare, complexitate mare Verificarea (aproape) tuturor elementelor spațiului soluțiilor

, ,

- condiții de continuare

se construiește element cu element primește o valoare din numai după toate elementele anterioare () se trece la elementul

▪ altfel se alege altă valoare pentru valoarea aleasă pentru e consumată mulțimea valorilor consumate

▪ dacă nu mai sînt valori disponibile se revine la elementul anterior nu garantează obținerea unei soluții rezultat

Reprezentare date

Configurație curentă

Configurație inițială

Configurație soluție

Configurație finală

Rezolvare problemă: Configurație inițială configurație soluție …configurație soluție configurație finală

Operații

Atribuie și avansează

Încercare eșuată

Revenire

Revenire după construirea unei soluții

Forma generală a algoritmului

inițializare //construire configurație inițială

cît timp //cît timp configurația nu e finală dacă //configurație de tip soluție?

▪ reține soluția ▪ //revenire după construirea unei soluții

altfel▪ dacă //mai sînt valori neconsumate

▪ alege o valoare

▪ dacă satisfac condițiile de continuare //atribuie și avansează

▪ altfel //revenire

Algoritm modificat

Particularități ale unor probleme

- progresii aritmetice cu valoarea inițială , rația și valoarea finală ▪ uneori ,

toate sînt identice cu mulțimea

Avantaje nu trebuie memorate explicit mulțimile și alegerea unui element neconsumat este ușoară

//primul element minus rația, de multe ori 0=1-1 cît timp

//variabila de impas cît timp și //alegerea unei noi valori pentru

▪ //următorul termen în progresie▪ posibil(,vb) //sînt îndeplinite condițiile de continuare

dacă //impas => revenire▪

altfel▪ dacă

▪ dacă condiții_finale(x) //configurație soluție? reține_soluția

▪ altfel //avans▪

Implementare recursivă

Metoda este de natură recursivă, deci ușor de implementat recursiv

Forma recursivă generală

backtracking(i) dacă i==n+1

retine_solutia(); altfel pentru fiecare element j din Si

x[i]=j; daca posibil(i) backtracking(i+1);

Implementare recursivă

Exemple de probleme care se rezolvă prin metoda backtracking:

Problema celor 8 (n) regine.

Problema cavalerilor mesei rotunde.

Plata unei sume (cu/fără bancnotă unitate).

Generarea tuturor permutărilor.

Generarea tuturor aranjamentelor.

Generarea tuturor combinărilor.

Problema colorării hărților.

Enunțuri complete în manual

Problema celor 8 regine

D D

DD

DD

DD

- coloana pe care se află regina de pe linia i

, ,

Condiție de continuare Regina plasată,

▪ nu e pe aceeași linie cu una plasată anterior▪ implicit, nu e nevoie de verificare

▪ nu e pe aceeași coloană cu una plasată anterior▪ pentru

▪ nu e pe aceeași diagonală cu una plasată anterior▪ pentru

Condiţie finală nu e necesară

Problema celor 8 regine

// Retine o configuratie (afisare)// I: nr. solutie (nr), nr dame (n), vector solutie// E: -void retine_solutia(int nr, int n, int* x){ int i,j;

printf("\n Solutia numarul %d\n",nr); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) printf("%c",j==x[i]?'D':'.'); printf("\n"); } if(r=='n') { printf("\n\nUrmatoarea (n) sau Ultima (l)?"); r=_getch(); }}

Problema celor 8 regine

// Conditia de continuare// I: solutia partiala (x), numarul de elemente (i)// E: 1 daca e acceptabila, 0 daca nu e acceptabilaint posibil(int *x, int i){ int j, p; p=1; for( j=1; j<i; j++) if( x[i]==x[j] || abs(i-j)==abs(x[i]-x[j]) ) p=0; return p;}

Problema celor 8 regine

// I: nr dame/dimensiune tabla (n) // E: nr solutiiint regine(int n){ int nr, *x, i, am; x=new int[n+1]; //vectorul solutie nr=0; //numar solutii i=1; x[1]=0; //prima valoare minus ratia while(i>0) //cit timp nu am ajuns la conf. finala { am=0; while( x[i]<n && !am) //alege urm. val. acceptabila pentru x[i] { x[i]++; //urmatoarea valoare pentru x[i] am=posibil(x,i); //este acceptabila? } if(!am) i--; //impas, revenire else if( i==n ) //configuratie solutie retine_solutia(++nr,n,x); else x[++i]=0; //prima valoare minus ratia } delete x; return nr;}

Problema celor 8 dame

// I: numar dame (n), element curent (i), vector solutie (x), numar solutii (nr)// E: numar solutiiint regine_r(int n, int i, int* x, int nr){ int j;

if( i==n+1) retine_solutia(++nr,n,x); else for(j=1; j<=n; j++ ) { x[i]=j; if( posibil(x,i) ) nr=dame_r(n,i+1,x,nr); } return nr;}

Spor la învățat!