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.
|
