Cautarea cu revenire (backtracking)

Tehnica cunoscuta sub numele de backtracking (cautare cu revenire) a fost deja folosita de noi la parcurgerea (traversarea) in adancime a arborilor si la explorarea in adancime a grafurilor. Intr-un cadru mai larg, aceasta tehnica se foloseste la rezolvarea unor probleme de decizie si este, de asemenea, larg folosita in inteligenta artificiala.

Fie problema P, care poate fi rezolvata, in principiu, pe mai multe cai. Fie P1, P2, ..., Pn subproblemele corespunzatoare fiecareia din aceste cai. Important este ca, pentru a obtine solutia problemei P este suficient sa se rezolve numai una din subproblemele P1, P2, ..., Pn, dar nu se stie dinainte care din ele.
Trebuie, deci, sa se ia o decizie, pe care din aceste cai sa se mearga, fara ca in momentul luarii deciziei sa existe informatia necesara in acest scop. In consecinta, problema este nedeterminista.
 
Cazul determinist este cel al structurii de decizie 
    if <conditie> 
    then <actiune 1>
    else <actiune 2>
in care se considera ca expresia <conditie> poate fi evaluata inainte de a se executa actiunea 1 sau 2.

In cazul nedeterminist discutat aici, se considera ca la luarea deciziei nu exista informatia necesara pentru a determina cu siguranta pe ce cale trebuie sa se continuie executarea programului.

Aplicand tehnica backtracking, rezolvarea problemei P mentionate mai sus se face astfel:

Daca si subproblemele P1, P2, ..., Pn sunt tot nedeterministe, pentru rezolvarea lor se procedeaza in acelasi mod, astfel ca rezolvarea devine recursiva. In consecinta, pentru realizarea cautarii in adancime cu revenire se foloseste o stiva. Inainte de a se trece la un succesor, se pune in stiva starea curenta, care este restaurata la revenirea dinspre succesorul respectiv, la fel ca la parcurgerea in adancime a arborilor.
 
In fisierul Backtracking.java este definita clasa abstracta Backtracking, care ofera o implementare a algoritmului cu acelasi nume descris mai sus. Ca stiva se foloseste o instanta a clasei ArrayList. Ca varf al stivei se foloseste ultimul element al listei. Avantajul folosirii drept stiva a unei liste este ca aceasta poate fi examinata la validarea succesorilor. Elementele stivei sunt instante ale clasei interioare ElemStiva si contin doua campuri:
    Object element - contine elementul de informatie (succesorul elementului precedent din stiva) pus in varful stivei;
    Object ultimSuccesorVizitat - contine o referinta la ultimul succesor al acestui element care a fost deja vizitat. Cand elementul se pune prima data in stiva, aceasta referinta este nula.

Algoritmul foloseste urmatoarele metode abstracte:
  protected abstract Object succesor() - intoarce un succesor al elementului curent (al elementului situat in varful stivei), care urmeaza dupa ultimul succesor vizitat; daca nu exista succesor, intoarce null; metoda actioneaza, deci, ca un iterator de succesori ai elementului din varful stivei.
  protected abstract boolean esteValid(Object succesor) - intoarce true daca succesorul este valid;
  protected abstract Object solutie() - daca continutul stivei permite sa se determine o solutie, intoarce aceasta solutie; altfel intoarce null.

Aceste metode abstracte trebuie definite in clasele derivate, corespunzator cu problema rezolvata. Algoritmul de backtracking este realizat aici prin doua metode:

  protected Object succesorValid() - cauta un succesor valid al elementului din varful stivei, care sa urmeze ultimului succesor deja vizitat, si intoarce acest succesor, aplicand algoritmul de backtracking. Daca nu exista succesor valid al elementului din varful stivei, acest element este eliminat din stiva si se continua cautarea succesorului pentru elementul precedent al stivei; cautarea se opreste cand se gaseste un succesor valid, sau cand stiva devine goala. In ultimul caz, metoda intoarce null. Aceasta metoda foloseste metodele succesor si esteValid pentru a obtine un nou succesor al starii curente si pentru a verifica daca acest succesor este valid. Remarcam ca metoda succesorValid actioneaza ca un iterator: la fiecare invocare ea intoarce un nou succesor valid, care poate fi pus in stiva. Este folosita numai in subclase.

  public Object solutiaUrmatoare() - itereaza succesorii valizi pana cand se ajunge in situatia ca stiva contine o solutie si intoarce aceasta solutie. Pentru a verifica daca stiva contine o solutie si a construi aceasta solutie se foloseste metoda solutie. Metoda actioneaza, deci, ca un iterator de solutii. Este singurul iterator public.

Pentru a elabora o clasa care rezolva o problema concreta prin metoda backtracking, programatorul creeaza o clasa derivata din cea descrisa aici, in care:

   * exista un constructor care initializeaza stiva folosita in clasa abstracta Backtracking; in constructor se pot initializa si eventuale campuri de date specifice continute in clasa derivata;
   * se definesc cele trei metode abstracte ale clasei Backtracking, corespunzator problemei rezolvate in subclasa.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati