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)
}
|
