Algoritmi de cãutare cu revenire ("Backtracking")
Prezentarea metodei Backtracking
Problemele rezolvate prin metoda Backtracking sunt fie probleme de optimizare, fie probleme de enumerare, fie probleme de decizie.
Exemple de probleme de enumerare:
- Afisarea tuturor drumurilor posibile dintre douã noduri dintr-un graf.
- Problema sortãrii topologice a nodurilor unui graf astfel încât fiecare nod sã fie afisat dupã nodurile precedente. Se cer toate posibilitãtile de ordonare topologicã. Vectorul solutie contine
numerele nodurilor vizitate, în ordine topologicã.
Exemplu de probleme de decizie :
- Sã se decidã dacã un graf dat este sau nu aciclic, deci dacã contine sau nu cel putin un ciclu. Vectorul solutie contine numerele nodurilor din graf pe unde trece ciclul gãsit, dacã el existã.
- Sã se decidã dacã un graf G1 contine ca subgraf un graf G2.
- Sã se decidã dacã existã o combinatie de valori logice care sã "satisfacã" o expresie logicã datã, deci care sã producã o iesire cu valoarea "adevãrat".
Putem deosebi probleme la care vectorul solutie are acelasi numãr de componente pentru orice combinatie de date la intrare si probleme cu vector solutie de lungime variabilã.
Exemple de probleme cu vector solutie de lungime variabilã:
- Problema drumului minim dintre douã noduri dintr-un graf ponderat. Vectorul solutie contine numerele nodurilor de pe drumul minim gãsit.
- Problema selectiei optime (a rucsacului) : selectarea acelor obiecte dintr-o multime datã care au o greutate totalã mai micã sau egalã cu capacitatea rucsacului si o valoarea totalã maximã.
- Problema acoperirii tuturor arcelor dintr-un graf cu un numãr minim de noduri.
Metoda backtracking se poate aplica unui mare numãr de probleme enumerative sau de optimizare cu solutie vectorialã pentru cã asigurã obtinerea tuturor solutiilor posibile pentru problema datã. Totusi, din cauza complexitãtii exponentiale, ea se recomandã numai problemelor pentru care nu se cunoaste 333x2311d un algoritm mai eficient sau problemelor de dimensiuni mici.
Un algoritm backtracking este un algoritm de cãutare sistematicã si exhaustivã a tuturor solutiilor, dintre care se poate alege apoi solutia optimã.
Cãutarea exhaustivã în arborele de solutii este un proces de încercare si revenire ( de cãutare cu revenire). Acest proces seamãnã cu cãutarea drumului cãtre o anumitã tintã (sau cãtre mai multe tinte ) pe o retea de drumuri cu multe ramificatii (dar fãrã indicatoare) de cãtre o persoanã care se aflã pentru prima datã în regiunea respectivã si nu cunoaste dinainte traseul cãtre tinta propusã. La fiecare ramificatie de drumuri omul alege un drum oarecare, dar dacã acest drum se dovedeste ulterior gresit (sau dacã existã mai multe tinte), atunci drumetul trebuie sã revinã la ultima bifurcatie si sã încerce un alt drum.
Solutiile multor probleme au forma unor vectori X cu componentele (x[1],x[2],...x[n]), astfel încât componentele x[i] satisfac anumite conditii specifice problemei (conditii interne).
Sã considerãm pentru început cã x[1]...x[n] pot avea ca valori doar numere naturale dintr-o multime finitã V=, ceea ce este adevãrat pentru multe probleme reale.
Metoda de cãutare cu revenire construieste progresiv un vector solutie, începând cu x[1] si continuând cu x[2],x[3],... pânã la x[n]. Pentru fiecare componentã a vectorului solutie X se încearcã toate valorile posibile 1,2...m. Numãrul combinatiilor posibile este m*m*..m deci m**n.
O metodã backtracking generalã poate fi privitã ca solutie a a urmãtoarei probleme: Sã se genereze toti vectorii X cu n componente, fiecare având valori în multimea , astfel ca aceste componente sã respecte anumite conditii, specifice problemei de rezolvat.
Sã considerãm câteva cazuri numerice simple.
Pentru n=2 si m=2 , vectorii candidati, dintre care se alege solutia sunt:
x[1]= 1 1 2 2
x[2]= 1 2 1 2
Pentru n=3 si m=2 sunt 2**3=8 vectori candidati:
x[1]= 1 1 1 1 2 2 2 2
x[2]= 1 1 2 2 1 1 2 2
x[3]= 1 2 1 2 1 2 1 2
Fiecare vector generat trebuie verificat dacã poate constitui sau nu o solutie a problemei. Se observã cã numãrul de candidati creste foarte repede pe mãsurã ce n si m cresc.
Ideea metodei backtracking este de a folosi un singur vector în care se modificã sistematic valorile componentelor pentru a genera succesiv toti vectorii candidati. Conditia este verificatã
la adãugarea fiecãrei componente si nu dupã generarea completã a unui vector candidat.
De exemplu, în problema generãrii permutãrilor de n obiecte, conditia este ca fiecare vector solutie sã continã valori (obiecte) distincte, deci sã nu se repete aceeasi valoare. Pentru n=3 vectorii candidati (1,1,1), (1,2,1), (3,1,1), etc. sunt inacceptabili ca solutii ale problemei permutãrilor.
Metoda backtracking pentru generare permutãri începe cu x[1]=1, dupã care va respinge valorile x[2]=1 sau x[3]=1. La atribuirea de valori pentru x[k] vor fi acceptate doar valorile diferite de valorile componentelor anterioare x[1], x[2],...x[k-1].
Multimea vectorilor candidati poate fi privitã ca un arbore a cãrui înãltime este n, adicã numãrul maxim de componente din vectorul solutie. Fiecare ramurã (cale) de la rãdãcinã la o frunzã reprezintã un vector candidat. Dacã solutiile problemei sunt vectori cu n componente, atunci arborele de cãutare are toate frunzele pe acelasi nivel. Exemplu pentru n=m=2.
x[1]=1_______|______ x[1]=2
| |
___|____ ___|___
| | | |
x[2]=1 x[2]=2 x[2]=1 x[2]=2
Metoda backtracking face o cãutare în adâncime în acest arbore , dar existã si metode de cãutare în lãtime, mai dificil de programat si cu un consum de memorie mai mare.
In procesul de cãutare a solutiei, atunci când se ajunge la determinarea valorii lui x[k], se cunosc anumite valori x[1],...,x[k-1] care respectã conditiile problemei, dar de care nu putem fi siguri cã fac parte din solutia cãutatã.
Pentru a determina valoarea lui x[k] se încearcã pe rând toate valorile posibile 1,2...,m si pentru fiecare din ele se verificã respectarea conditiilor impuse. Pot apare douã situatii:
- Existã o valoare pentru x[k], care împreunã cu valorile gãsite pentru x[1],...x[k-1], satisface conditiile impuse; în acest caz se continuã cu determinarea componentei urmãtoare x[k+1];
- Nu existã nici o valoare (dintre 1...m) pentru x[k], care sã respecte conditiile impuse împreunã cu x[1],...x[k-1]; în acest caz se revine la componenta anterioarã x[k-1] si se încearcã o nouã valoare pentru x[k-1] (dacã mai existã valori neluate în considerare) care sã poatã reprezenta, alãturi de x[1],.. o parte a solutiei cãutate.
Conditiile ce trebuie respectate la fiecare pas din procesul de cãutare cu revenire se numesc si conditii de continuare sau de acceptare a unui nou candidat pentru componenta x[k].
Schema generalã a metodei backtracking
Programele care implementeazã algoritmi de cãutare cu revenire au forme destul de diverse în literatura de specialitate, desi esenta metodei este aceeasi. Schema care urmeazã are avantajul cã pleacã de la o formã minimalã (dar suficientã pentru multe probleme) si poate fi apoi extinsã pentru a fi aplicabilã si altor probleme.
Strategia de generare a vectorilor candidati si de selectare a vectorilor solutie poate fi codificatã sub forma unei proceduri generale, utilizabilã fãrã modificãri în rezolvarea multor probleme. Functia, numitã în continuare "cautSol", poate fi exprimatã recursiv (mai compact) sau iterativ (mai eficient si mai explicit).
Functia booleanã "posibil" verificã satisfacerea conditiilor de continuare de cãtre valorile x[1],...x[k] si este dependentã de problema specificã rezolvatã.
Functia "prelSol" este apelatã de fiecare datã când s-a obtinut o solutie; ea afiseazã solutia dacã este o problemã de enumerare, sau comparã solutia gãsitã cu o solutie optimã partialã si retine solutia optimã, dacã este o problemã de optimizare.
Vectorul solutie "x" si dimensiunea lui vor fi definite ca variabile globale (externe), pentru cã sunt utilizate de mai multe functii, dintre care una poate fi recursivã.
Functie pentru forma nerecursivã a unui algoritm general de cãutare cu revenire :
void cautSol (int ki)
else
if (x[k] < m)
else
Vectorul x este folosit pentru memorarea unei solutii partiale, iar în cazul k=n+1 vectorul x contine o solutie finalã.
Uneori vectorul 'x' este privit ca o stivã, deoarece modificãrile în acest vector au loc numai la ultima componentã x[k], iar indicele k creste sau scade numai cu 1, ceea ce corespunde cresterii sau reducerii dimensiunii stivei.
Rezolvarea unei probleme concrete folosind acest algoritm necesitã:
- Identificarea vectorului solutie x : ce semnificatie au componentele sale si ce valori pot avea.
- Identificarea conditiilor de continuare sau, mai exact, alegerea conditiilor de continuare astfel încât numãrul de candidati respinsi de functia "posibil" sã fie cât mai mare.
In continuare vom prefera functia recursivã de cãutare, care este mai usor de modificat si de extins pentru alte situatii neluate acum în considerare.
Functie recursivã de cãutare cu revenire
Varianta recursivã a functiei generale de cãutare cu revenire are nevoie de un parametru întreg k, care reprezintã numãrul componentei care urmeazã a fi determinatã în apelul respectiv.
// cauta o valoare acceptabila pentru x[k]
void cautSol ( int k)
Pentru functionarea corectã a functiei recursive este esential ca variabila "i" sã fie variabilã localã si nu globalã deoarece la fiecare întrerupere a executiei functiei printr-un apel recursiv se salveazã automat în stivã valorile lui "k" si lui "i". La revenirea din functie se reia ciclul pentru pasul k cu urmãtoarea valoare a lui i fatã de valoarea la care s-a produs întreruperea.
Procedura recursivã poate fi scrisã si astfel încât sã înceapã prin a verifica dacã s-a obtinut o solutie completã (un vector cu n componente acceptabile). In acest caz functia este apelatã si pentru valoarea k=n+1, dar se iese imediat dupã prima instructiune "if".
void cautSol ( int k)
Apelul recursiv întrerupe ciclul "for", dar acest ciclu este reluat (continuat) la iesirea din functia "cautSol". La fiecare apel se memoreazã în stiva folositã automat de compilator valorile variabilelor k si i, iar la reluarea ciclului (la iesirea din cautSol) se continuã cu acelasi x[k] si cu urmãtoarea valoare a lui i. Dacã vectorul solutie poate contine si valori zero, atunci se modificã instructiunea "for" pentru a include valoarea zero.
Functia "cautSol" se apeleazã de obicei în programul principal cu parametrul k=1, ceea ce corespunde faptului cã procesul de aflare a unei solutii începe cu cãutarea unei valori pentru x[1]. Este posibil ca parametrul procedurii "cautSol" sã fie diferit de 1 (de exemplu, 2) sau sã primeascã valori într-un ciclu din programul principal.
Problema generãrii permutãrilor
Generarea permutãrilor (ca si generarea combinãrilor) este o problemã de enumerare la care se afiseazã toate solutiile obtinute. Pentru aceastã problemã n=m deci lungimea vectorului solutie este egalã cu numãrul de valori posibile pentru fiecare componentã a acestui vector.
Pentru fiecare componentã x[k] se încearcã pe rând valorile 1,2,3. Conditia de acceptare a unei valori pentru x[k] este ca aceastã valoare sã fie diferitã de toate valorile x[1],...x[k-1]. Functia "posibil" trebuie sã verifice aceastã conditie.
// conditia de acceptare x[k] ptr. permutari
int posibil (int k)
In cazul n=3 solutiile, în ordinea generãrii de cãtre functia "cautSol", sunt urmãtoarele:
x[1] 1 1 2 2 3 3
x[2] 2 3 1 3 1 2
x[3] 3 2 3 1 2 1
Pentru a urmãri evolutia algoritmului putem insera o afisare la începutul functiei "cautSol".
Pentru m=3 în problema permutãrilor se genereazã 15 candidati dintre care functia "posibil" retine numai 6 solutii, afisate de functia "prelSol".
// afisare vector solutie ptr permutari
void prelSol ()
Programul principal citeste o valoare pentru "m" si face apelul cautSol(1).
O problemã asemãnãtoare este afisarea tuturor combinãrilor de n numere luate câte m folosind un algoritm backtracking. In acest caz vrem sã afisãm numai solutiile distincte, nu si cele obtinute prin permutarea celor m numere selectate dintre cele n. Exemplu: n=4, m=2.
Solutii: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4). Nu se afiseazã (2,1), (3,1), etc.
Existã si alte probleme în care vrem sã afisãm doar solutiile distincte, iar aceastã reducere a numãrului de solutii afisate se poate face prin alegerea corespunzãtoare a conditiei de acceptare din functia "posibil". Pentru problema combinãrilor conditia de acceptare a unei valori pentru x[k] este ca aceastã valoare sã fie mai mare ca x[k-1] ( si deci automat mai mare ca x[k-2] si ca cele cu indici mai mici). Exceptie face x[1], pentru care se acceptã orice valoare.
// test de acceptare ptr afisare combinari
int posibil( int k)
Algoritm backtracking extins cu listã de candidati
Vom numi aici "candidati" valorile din care putem alege pentru fiecare componentã x[k] a vectorului solutie. In abordarea anterioarã am considerat cã aceastã listã este unicã pentru toate componentele x[k] si contine numere întregi între 1 (sau 0) si un numãr dat m.
Notând cu c[k] multimea de candidati pentru x[k] putem observa cã multimea c[k-1] are mai multe elemente ca c[k] deoarece alegerea unei valori pentru x[k-1] restrânge posibilitãtile de alegere pentru x[k]. De exemplu, în problema generãrii permutãrilor de 3 obiecte avem c[1]=, c[2]=c[1]-, c[3]= c[2]-.
Candidatii care nu mai pot reprezenta valori posibile pentru un x[k] sunt respinsi de functia "posibil", dar ei sunt totusi transmisi si verificati de aceastã functie cu rol de filtru.
Din aceastã observatie apare ideea de a reduce numãrul de încercãri din functia "cautSol" prin generarea unei noi liste de candidati la fiecare pas (la fiecare apel al functiei).
Pentru multe probleme cu grafuri vectorul solutie este un vector de noduri, iar cele douã posibilitãti capãtã forma urmãtoare:
- Fie se cautã pentru un x[k] valoarea sa printre toate nodurile din graf, iar functia "posibil" respinge acele noduri care nu sunt succesori ai lui x[k-1];
- Fie se genereazã în pasul k lista de succesori ai nodului x[k-1] si se verificã care dintre ei satisfac si celelalte conditii.
Trebuie observat cã lista de candidati si dimensiunea ei trebuie sã fie variabile locale procedurii "cautSol", pentru a fi salvate automat în stivã la fiecare apel recursiv.
Varianta functiei "cautSol" cu generarea unei noi liste de candidati la fiecare pas aratã astfel:
void cautSol (int k)
Functia "succesor" are ca rezultat urmãtorul candidat din lista de candidati sau -1 dacã nu mai existã candidati. In acest scop este necesarã mentinerea unui indice în lista de candidati.
Numãrul de candidati "nc" poate fi diferit la fiecare pas si rezultã din functia "genCand".
In realitate, aceastã variantã nu este mai bunã decât varianta initialã (este mai mare si mai ineficientã) deoarece necesitã timp pentru generarea listei de candidati la fiecare apel si încarcã
mai mult stiva cu lista de candidati .
O solutie practicã pentru modificarea listei de candidati la fiecare pas poate folosi o multime a valorilor deja incluse în solutia partialã si care nu mai trebuie încercate. O implementare simplã a acestei multimi ( în orice limbaj de programare) este un vector "v", în care componenta v[j] este 0 dacã valoarea j nu a fost inclusã încã în solutia partialã si v[j]=1 dacã valoarea j a fost inclusã (dacã existã un x[i]=j cu i < k, la apelul "cautSol(k)" ). Vectorul "v" va fi tot o variabilã globalã, pentru cã este folosit de mai multe functii.
La acceptarea unei valori "i" pentru x[k] trebuie sã facem v[i]=1, iar la revenirea pentru încercarea unei noi valori pentru x[k] vom face v[i]=0 (pentru cã valoarea "i" nu mai face parte din solutia partialã).
Vom relua problema generãrii permutãrilor de "m" numere în aceastã abordare, mai eficientã, cu mai putine apeluri ale functiei "posibil".
// afisare permutari de m obiecte
// var. externe, globale
int x [10], // vector solutie
v [10] ; // vector de valori incluse in solutie
int m ; // nr. de obiecte
// daca x[k] aceptabil
int posibil ( int k)
// backtracking recursiv
void cautSol (int k)
}
Functia "posibil" poate lipsi deoarece are mereu rezultat 1 (x[k] este acceptat întotdeauna).
Forma anterioarã a functiei "cautSol" poate fi generalizatã pentru orice operatii asociate alegerii unei valori pentru x[k] si respectiv pentru anularea acestor operatii la renuntarea acestei alegeri:
void cautSol ( int k)
}
|
