Căutarea cu revenire (backtracking)

Tehnica cunoscută sub numele de backtracking (căutare cu revenire) a fost deja folosită de noi la parcurgerea (traversarea) în adâncime a arborilor și la explorarea în adâncime a grafurilor. Într-un cadru mai larg, această tehnică se folosește la rezolvarea unor probleme de decizie și este, de asemenea, larg folosită în inteligența artificială.

Fie problema P, care poate fi rezolvată, în principiu, pe mai multe căi. Fie P1, P2, ..., Pn subproblemele corespunzătoare fiecăreia din aceste căi. Important este că, pentru a obține soluția problemei P este suficient să se rezolve numai una din subproblemele P1, P2, ..., Pn, dar nu se știe dinainte care din ele.
Trebuie, deci, să se ia o decizie, pe care din aceste căi să se meargă, fără ca în momentul luării deciziei să existe informația necesară în acest scop. În consecință, problema este nedeterministă.
 
Cazul determinist este cel al structurii de decizie 
    if <condiție> 
    then <acțiune 1>
    else <acțiune 2>
în care se consideră ca expresia <condiție> poate fi evaluată înainte de a se executa acțiunea 1 sau 2.

În cazul nedeterminist discutat aici, se consideră că la luarea deciziei nu există informația necesară pentru a determina cu siguranță pe ce cale trebuie să se continuie executarea programului. 

Remarcăm că, în cazul problemelor deterministe soluția este unică, în timp ce problemele nedeterministe pot avea mai multe soluții, sau niciuna.

Aplicând tehnica backtracking, rezolvarea problemei P menționate mai sus se face astfel:

Dacă și subproblemele P1, P2, ..., Pn sunt tot nedeterministe, pentru rezolvarea lor se procedează în același mod, astfel că rezolvarea devine recursivă.

Tehnica backtracking poate fi privită și ca o tehnică de căutare în spațiul stărilor. Numim stare a sistemului ansamblul valorilor tuturor variabilelor sistemului la un moment dat. La efectuarea fiecărei operații are loc o modificare a stării sistemului. În consecință, putem să ne imaginam un graf orientat al stărilor, în care fiecare vârf este o stare, iar fiecare arc este o operație.
 
Este evident că acest graf nu este el însuși o structură de date din memoria calculatorului, ci doar o reprezentare abstractă. În majoritatea cazurilor, la executarea programului nu se vor parcurge toate vârfurile acestui graf (toate stările posibile), ci numai unele dintre ele. La executarea programului se parcurge numai o singură cale în acest graf al stărilor, depinzând de datele de intrare.

La aplicarea tehnicii backtracking, se consideră că problema care se rezolvă este de așa natură, încât nu este posibil să se ajungă în aceeași stare pe două căi diferite. Se consideră, deci, că spațiul stărilor are o structură arborescentă (întrucât nici un nod al arborelui nu poate avea doi părinți). Implicit, aceasta înseamnă că la executarea programului nu pot exista cicluri. În plus, se consideră că înălțimea acestui arbore al stărilor este finită. Aceasta înseamnă că, la parcurgerea în adâncime, după un anumit număr de pași (posibil mare), se va ajunge la o stare fără succesor (la o "frunză" a arborelui stărilor), ceeace face posibil ca, dacă nu s-a găsit soluția, să se revină la o stare anterioară și să se continue căutarea pe altă cale. Dacă înălțimea arborelui ar fi infinită, s-ar merge mereu în adâncime pe o singură cale, iar revenirea nu ar mai fi posibilă.

Având în vedere cele expuse mai sus, la fel ca la parcurgerea arborilor în adâncime, pentru realizarea căutării cu revenire (backtracking) se folosește o stivă. În fiecare punct de ramificație (din care pornesc mai multe căi posibile), starea curentă se pune în stivă pentru a se putea reveni la ea ulterior, dacă pe calea aleasă nu s-a gasit soluția sau dacă se caută și alte soluții.
 
În fișierul Backtracking.java este definită clasa abstractă Backtracking, care oferă o implementare a algoritmului cu același nume descris mai sus. Ca stivă se folosește o instanță a clasei ArrayList. Ca vârf al stivei se folosește ultimul element al listei. Avantajul folosirii drept stivă a unei liste este că aceasta poate fi examinată la validarea succesorilor. Elementele stivei sunt instanțe ale clasei interioare ElemStiva și conțin două câmpuri:
    Object element - conține elementul de informație (succesorul elementului precedent din stivă) pus în vârful stivei;
    Object ultimSuccesorVizitat - conține o referință la ultimul succesor al acestui element care a fost deja vizitat. Când elementul se pune prima data în stivă, aceasta referință este nulă.

Algoritmul folosește următoarele metode abstracte:
  protected abstract Object succesor() - întoarce un succesor al elementului curent (al elementului situat în vârful stivei), care urmează după ultimul succesor vizitat; dacă nu există succesor, întoarce null; metoda actionează, deci, ca un iterator de succesori ai elementului din vârful stivei.
  protected abstract boolean esteValid(Object succesor) - întoarce true dacă succesorul este valid;
  protected abstract Object solutie() - dacă conținutul stivei permite să se determine o soluție, întoarce această soluție; altfel întoarce null.

Aceste metode abstracte trebuie definite în clasele derivate, corespunzător cu problema rezolvată. Algoritmul de backtracking este realizat aici prin următoarele două metode:
  protected Object succesorValid() - caută un succesor valid al elementului din vârful stivei, care să urmeze ultimului succesor deja vizitat, și întoarce acest succesor, aplicând algoritmul de backtracking. Dacă nu există succesor valid al elementului din vârful stivei, acest element este eliminat din stivă și se continuă căutarea succesorului pentru elementul precedent al stivei; căutarea se oprește când se găsește un succesor valid, sau când stiva devine vidă. În ultimul caz, metoda întoarce null. Această metodă folosește metodele succesor și esteValid ale clasei abstracte Backtracking pentru a obține un nou succesor al stării curente și pentru a verifica dacă acest succesor este valid. Remarcăm că metoda succesorValid acționează ca un iterator: la fiecare invocare ea întoarce un nou succesor valid, care poate fi pus în stivă. Este folosită numai în subclase.

  public Object solutiaUrmatoare() - iterează succesorii valizi pană când se ajunge în situaîia ca stiva conține o soluție și întoarce această soluție. Pentru a verifica dacă stiva conține o soluție și a construi această soluție, se folosește metoda solutie. Metoda actionează, deci, ca un iterator de soluții. Este singurul iterator public.

Pentru a elabora o clasă care rezolvă o problemă concretă prin metoda backtracking, programatorul creeaza o clasă derivată din cea descrisa aici, în care:

   * există un constructor care inițializeaza stiva folosită în clasa abstractă Backtracking; în constructor se pot inițializa și eventuale câmpuri de date specifice conținute în clasa derivată;
   * se definesc cele trei metode abstracte ale clasei Backtracking, corespunzător problemei rezolvate în subclasă.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați