Backtracking - lecție practică | Paul Colța

  
  • Backtracking

    Backtracking-ul este o tehnică utilizată pentru rezolvarea problemelor unde:



    • Soluția lor poate fi pusa sub forma unui vector;
    • Mulțimile a1, a2, ..., an sunt multimi finite iar elementele lor se considera a fi intr-o relatie de ordine bine stabilită;
    • Nu se dispune de o alta metoda de rezolvare mai rapida a problemei;


    Pe scurt, metoda backtracking are ca rezultat obtinerea unei singure soluții. Se poate forța oprirea atunci când solutia a fost gasită.

    ! Observație: fiecare din elementele s1, s2, ..., sn pot fi la randul lor vectori. Deoarece intr-un algoritm backtracking ne intereseaza toate solutiile unei probleme vom proceda astfel:

    - Pentru a obtine fiecare solutie finala vom trece printr-un vector stiva completandu-l pas cu pas, nivel cu nivel trecand astfel prin niste solutii partiale

    - Atât soluțiile finale, cât și cele partiale pentru a putea fi luate in considerare trebuie sa indeplineasca anumite conditii specifice fiecarei probleme numite conditii de validare sau de continuare. O solutie ce indeplineste aceste conditii devine astfel solutie valida.


    Esența metodei constă în generarea succesiunilor care sunt valide. O soluție partial validă este păstrată în timp ce una nevalida este respinsă renunțându-se la construirea pe ea a solutiei finale. Deci metoda backtracking consta in renuntarea cat mai devreme cu putință la generarea unor succesiuni sortite esecului. Datorita modului de implementare, metoda backtracking este o mare consumatoare de timp.


    Vezi mai multe detalii în videoul lui Paul, apasă aici!


    InfoNow.ro - meditații online la informatică. Invață programare cu profesori meditatori.

Articolul anterior Meet The Team | Echipa InfoNow.ro
Articolul urmator Învață programare de la zero (primul pas)
Back
x
Acest website utilizează cookie-uri pentru a creea o experiență cât mai plăcută. Învață mai multe Acceptă