Algoritmi backtracking (III)
Problema acoperirii optime cu multimi
Se dă o multime scop S si n multimi candidat C astfel că orice element din S apartine cel putin unei multimi din C; să se determine numărul minim de multimi din C care acoperă complet pe S (deci reuniunea acestor multimi contine toate elementele lui S).
Solutia problemei este o colectie de multimi, dar ea poate fi pusă sub forma unui vector de indici într-un vector de multimi ce reprezintă familia dată.
Exemplu de date si rezultate :
S = , n=4
C[1]= , C[2] =, C[3] = , C[4] =
Solutia optimă este :
deci x[1]=2, x[2]=4
Putem generaliza din acest exemplu si să privim vectorul solutie ca o colectie de indici pentru selectarea de componente dintr-un alt 454y249e vector, cu componente de orice tip (eventual tot vectori).
O altă posibilitate de interpretare a vectorului solutie în această problemă este aceea în care x[k] poate fi unu sau zero după cum multimea C[k] a fost sau nu inclusă în solutie. Pentru exemplul anterior solutia optima va fi:
x[1]=0, x[2]=1, x[3]=0, x[4]=1
#include <stdio.h>
#include <stdlib.h>
#define MM 32 // nr. maxim de multimi din familie
#define M 32 // nr maxim de elemente intr-o multime
// operatii cu multimi de max 32 de numere intregi
typedef long* Set;
Set initS ()
void addS( Set m,int el)
void removeS (Set m,int el)
void retainAll (Set m1, Set m2)
void addAll (Set m1, Set m2)
void removeAll (Set m1, Set m2)
int containS (Set m,int el)
int equalS (Set a, Set b)
void printS( Set m) \n");
int sizeS ( Set x)
// variabile comune
Set cand [MM];
Set scop, aux;
int x[MM], xopt[MM] ; // x[k]=numar multime candidat folosita
int n, nopt, ns ; // n= nr. de multimi candidat
// citire multime
Set readS ( char *txt) while (i> 0);
return set;
}
//
void citDate ()
}
// prelucrare solutie
void prelSol (int k)
int posibil (int k )
// daca solutie in pasul k
int solutie (int k)
// backtracking
void cautSol (int k)
void main ()
nopt=n;
cautSol(1);
printf (" Multimi necesare: %d \n",nopt);
for (i=1;i<=nopt;i++)
printS (cand[xopt[i]]);
Reducerea numărului de încercări
Dezavantajul principal al unui algoritm de căutare cu revenire este numărul foarte mare de încercări efectuate pentru găsirea solutiilor, deci numărul de noduri din arborele de căutare.
In problemele de optimizare, numai o mică parte din vectorii candidati au sanse reale de a constitui solutia optimă, iar costul unor candidati este foarte departe de costul solutiei optime.
De exemplu, în problema restului, există solutii care folosesc multe monede de valori mici, dar ele nu pot candida la solutia optimă.
Ideea ar fi deci de a respinge o parte din candidatii, altfel acceptabili, prin impunerea unor conditii suplimentare în functia "posibil". Conditia rezultă fie din compararea costului estimat al
solutiei în curs de obtinere cu costul optim determinat până atunci, fie cu un cost optim de referintă, calculat separat.
Optimizările sunt relativ simple în problemele care caută un minim, dar mai dificile în problemele care caută un maxim.
Putem distinge următoarele situatii:
- In fiecare pas k se calculează costul solutiei partiale (cu primele k componente determinate) si se compară cu costul optim al solutiilor anterioare.
- In fiecare pas k se calculează costul solutiei partiale (cu primele k componente determinate) si se compară cu costul optim al solutiei greedy.
- In fiecare pas k se calculează costul solutiei partiale, se adună cu un cost estimat al părtii din solutie ce urmează a fi determinată si se compară cu un cost optim de referintă.
Toate variantele pot beneficia de o abordare "greedy" pentru:
- Determinarea unui cost optim de referintă, care este costul solutiei greedy.
- Stabilirea ordinii de examinare a candidatilor, pentru ca solutiile cu cost mai bun să fie calculate la început.
- Estimarea costului componentelor care nu au fost determinate încă.
Să exemplificăm cu problema restului în cazul concret:
Rest= 15, Valori monede: c[1]= 11, c[2]=5, c[3]=1
Dacă se foloseste lista de candidati în această ordine, atunci prima solutie găsită este cea cu 3 monede de valoare 5 (x[1]=0, x[2]=3), dar dacă se foloseste în ordine inversă (1,5,11), atunci
prima solutie găsită are costul 15 (x[1]=0,x[2]=0,x[3]=15).
Pentru a compara costul solutiei partiale cu costul optim al solutiilor complete anterioare vom modifica functia "posibil" astfel:
// eliminarea solutiilor partiale 'slabe'
int posibil (int k)
Multe probleme de optimizare pot fi rezolvate si printr-un algoritm greedy, care conduce la o solutie bună dacă nu chiar optimă. Ideea este de a folosi solutia greedy ca valoare de referintă pentru algoritmul backtracking.
In problema restului cu referintă greedy, functia "posibil" arată la fel ca cea de mai sus, dar valoare 'min' este numărul minim de monede calculat prin algoritmul greedy. Pentru cazul concret luat, min=5, deci vor fi respinse solutiile partiale cu mai mult de 5 monede.
De observat că, în acest ultim caz, reducerea numărului de încercări poate fi foarte drastică si că ordinea candidatilor nu mai contează. Timpul cerut de ciclul greedy este întotdeauna inferior timpului necesar algoritmului de căutare cu revenire si nu contribuie mărirea complexitătii algoritmului backtracking.
Se pot da multe exemple de probleme pentru care este posibilă utilizarea solutiei greedy ca valoare de referintă pentru respingerea solutiilor fără sanse de a fi minime din algoritmul backtracking: problema acoperirii cu număr minim de vârfuri a tuturor muchiilor dintr-un graf, problema arborelui de acoperire de cost minim, problema acoperirii cu număr minim de multimi a tuturor elementelor unei multimi scop, s.a.
Pentru problemele de optimizare care caută o valoare maximă este mai greu de respins variantele nepromitătoare, deoarece nu putem trage nici o concluzie din compararea costului partial al unei solutii cu costul maxim dat de solutia greedy.
Backtracking optimizat pentru problema rucsacului
Problema rucsacului, sau problema selectiei optime, este una din problemele clasice de optimizare. Fiind date n obiecte, fiecare cu greutatea g[i] si valoarea v[i] si un rucsac cu capacitatea totală gt, să se determine ce obiecte trebuie selectate pentru a fi luate în rucsac astfel încât greutatea lor totală să nu depăsească gt si valoarea lor să fie maximă. O solutie posibilă este o grupare de obiecte a căror greutate totală nu depăseste capacitatea rucsacului gt.
In varianta 0/1 vectorul solutie are n componente si fiecare x[k] poate fi 1 sau 0 după cum obiectul k a fost sau nu selectat.
Exemplu concret de date:
obiect 1 2 3 4 5
g[i] 15 35 25 5 10
v[i] 27 56 33 5 8
v[i]/g[i] 1.8 1.6 1.4 1.0 0.8
Solutia optimă este cea care ia obiectele 2 si 4, cu valoarea totală 61 si greutatea totală 40.
Vectorul solutie în varianta 0/1 :
x[1]=0, x[2]=1, x[3]=0, x[4]=1, x[5]=0
Ca vector solutie, de lungime variabilă, putem considera si un vector care contine în pozitia k numărul obiectului selectat în pasul k. Pentru datele de mai sus, vectorul solutie va fi:
x[1]=2, x[2]=4
Conditia de obtinere a unei solutii este ca nici unul din obiectele rămase să nu mai încapă în sac. Programul care urmează interpretează pe x[k] ca fiind decizia de selectie a obiectului k.
Conditia de acceptare a unui obiect x[k]=1 este ca greutatea obiectului k (g[x[k]]) să nu depăsească diferenta dintre capacitatea totală gt si greutatea obiectelor deja selectate (gp).
Functia "prelSol" va compara valoarea totală a unei solutii cu valoarea maximă dintre toate solutiile găsite până la un moment dat (vmax) si va retine în 'vmax' pe cea mai mare.
// problema rucsacului - x[k] =0/1 daca obiectul k neinclus/inclus
#define M 30 // nr. maxim de obiecte
int x[M], xopt[M]; // vectori solutie : obiecte selectate
int g[M], v[M]; // greutati si valori obiecte
int n,gt,gp,vp,vmax ;
// daca obiectul k poate fi inclus in sac
int posibil (int k)
// retine solutie optima in xopt
void scrieSol ( )
}
// modificare sac la includerea ob. k
void include (int k)
}
// modificare sac la excluderea ob. k
void exclude ( int k)
}
// backtracking recursiv
void cautSol (int k)
}
}
// citire date si afisare solutie optima
void main ()
Varianta următoare foloseste cealaltă interpretare a vectorului solutie: x[k] este numărul obiectului selectat în pasul k. Variabila 'sac' tine evidenta obiectelor selectate până la un moment dat ( ca tip de date abstract este o multime).
// problema rucsacului - backtracking neoptimizat
#define M 30 // nr. maxim de obiecte
int x[M], xopt[M]; // vectori solutie : obiecte selectate
int g[M], v[M]; // greutati si valori obiecte
int sac[M]; // continut rucsac
int n,nopt,gt,gp,vp,vmax,val ;
// daca poate fi ales obiectul x[k]
int posibil (int k)
// retine selectia de valoare maxima
void scrieSol(int k)
}
// daca solutie completa
int solutie(int k)
// actiuni la selectarea obiectului x[k]
void include (int k)
// elimina obiectul x[k] din selectie
void exclude (int k)
// backtracking recursiv
void cautSol (int k)
}
}
// citire date si afisare solutie optima
void main ()
Pentru exemplul numeric dat (cu 5 obiecte) programul anterior face 35 de apeluri (recursive) ale procedurii "cautSol" si compară 15 solutii posibile pentru a determina solutia optimă (cu valoare totală maximă a obiectelor din rucsac).
Dacă afisăm toate solutiile generate de acest program vom observa multe solutii "slabe", cu un obiect sau cu două obiecte usoare, ba chiar si solutia cu zero obiecte. Este deci normal să
ne punem problema reducerii numărului de solutii generate, din care se alege solutia optimă.
Spre deosebire de problema restului, care era o problemă de minim, în problema rucsacului nu este foarte simplu să reducem numărul de încercări, deoarece este o problemă de maxim.
Metoda, folosită în continuare, numită si "branch and bound", estimează, la fiecare pas, costul solutiei totale si compară acest cost cu un cost maxim partial realizat. Solutiile care nu promit
un cost total mai bun ca maximul partial realizat sunt respinse.
Intr-o formulare mai precisă, se asociază fiecărui nod din arborele de căutare o functie de cost f cu două componente : f1 este costul exact al solutiei partiale obtinute (costul drumului de la rădăcină la nodul curent), iar f2 este este costul maxim estimat al oricărei alegeri pentru celelalte componente ale solutiei (costul drumului maxim de la nodul curent la orice frunză din subarborele de sub nodul curent). f=f1+f2.
Comparând valoarea lui f pentru un nod cu valoarea maximă obtinută pentru nodurile analizate anterior, se poate decide dacă are rost să se continue completarea solutiei partiale sau se elimină din căutare tot subarborele ce are ca rădăcină nodul curent. Cu cât mai devreme putem face aceste estimări, cu atât reducem mai mult numărul de încercări.
Functia f2 se numeste si 'euristică' deoarece se bazează pe observatii specifice problemei rezolvate si mai mult 'ghiceste' un mod de calcul a limitei pentru solutia optimă, decât se bazează pe un algoritm riguros pentru calculul acestei limite.
Reducerea numărului de încercări (de solutii posibile) se poate face prin calcularea unui prag minim pe care trebuie să-l depăsească valoarea unei solutii pentru a candida la solutia optimă. Vor fi respinse acele solutii care nu 'promit', deci care nu au sanse de a fi solutii optime.
La fiecare pas k (la determinarea lui x[k]) se estimează valoarea solutiilor care încep cu x[1],...x[k] înainte de a se genera complet solutia si se compară cu pragul stabilit până atunci; dacă valoarea estimată este sub acest prag atunci se resping toti vectorii cu 'prefixul' x[1]...x[k] ( se 'taie' subarborele ce are ca rădăcină acea valoare a lui x[k] ).
Vom considera că o selectie care începe cu o valoare x[1] nu poate fi mai bună decât solutia greedy pentru selectia obiectelor 2,..n si de aceea valoarea estimată este valoarea calculată pentru solutia greedy.
Functia 'limSup' calculează valoarea estimată a unei solutii totale din costul exact al solutiei partiale 'vp', la care se adună valoarea obiectelor ce mai pot fi luate în sac, în ordinea 'greedy'.
// calc. limita super. a valorii solutiei
int limSup (int k)
return vc;
}
Functia "posibil" se modifică prin adăugarea unei conditii noi: selectia partială din pasul 'k' să promită o valoare totală superioară valorii maxime din selectiile anterioare (din variabila 'val').
// daca solutie posibila sau care promite
int posibil (int k)
Pentru exemplul dat se apelează de două ori functia "prelSol" cu următoarele rezultate:
x[1]=1 (g[1]=15,v[1]=27) selectia greedy este x[2]=3,v[3]=33
f1=27, f2=33, val=60 > 0 , se acceptă
x[1]=2 (g[2]=35,v[2]=56) selectia greedy este x[2]=4,v[4]=5
f1=56, f2=5, val=61 > 60 , se acceptă
Celelalte solutii partiale sunt respinse de functia "posibil" deoarece vor avea o valoare estimată mai mică sau egală cu 61.
|
