top of page

Colegiul NaÈ›ional “Petru RareÈ™” Suceava

                                                          Introducere

     Din când în când suntem puÈ™i în situaÈ›ia de a găsi o soluÈ›ie optimă la o problemă, cu toate că nu există nici o teorie aplicabilă pentru rezolvarea acesteia, cu excepÈ›ia verificării tuturor soluÈ›iilor. Acest tip de probleme care necesită generarea tuturor soluÈ›iilor È™i, eventual, alegerea unei soluÈ›ii optime se rezolvă cu ajutorul metodei backtracking.

     Backtracking este o metodă de parcurgere sistematică a spaÅ£iului soluÅ£iilor posibile ale unei probleme. Este o metodă generală de programare, ÅŸi poate fi adaptată pentru orice problemă pentru care dorim să obÅ£inem toate soluÅ£iile posibile, sau să selectăm o soluÅ£ie optimă, din mulÅ£imea soluÅ£iilor posibile. Backtracking este însă ÅŸi cea mai costisitoare metodă din punct de vedere al timpului de execuÅ£ie.

În Informatică s-au impus în domeniul tehnicilor de programare metode definite ÅŸi elaborate de Artificial Intelligence: metoda backtracking (metoda „revenirii” implementată sub diverse forme); Metoda face legătura dintre programarea procedurală È™i programarea declarativă.

Tehnica backtracking se poate aplica doar pentru probleme ce admit conceptul de „candidat parÈ›ial de soluÈ›ie” È™i oferă un test relativ rapid asupra posibilității ca un astfel de candidat să fie completat către o soluÈ›ie validă. Când se poate aplica, însă, backtracking-ul este adesea mult mai rapid decât căutarea prin metoda forÈ›ei brute prin toÈ›i candidaÈ›ii, întrucât este capabilă să elimine dintr-un singur test, un mare număr de candidaÈ›i.

Termenul „backtrack” a fost inventat de matematicianul american D. H. Lehmer în anii 1950.

Metoda Backtracking = metoda „revenirii”, definită ÅŸi elaborată de AI; este rezultatul unei istorii din 1852, când studentul englez Francis Guthrie a enunÅ£at problema celor 4 culori: „sunt suficiente 4 culori pentru a colora o hartă ce reprezintă diverse ţări, cu condiÅ£ia ca oricare două ţări vecine (cu frontiera comună) să fie  colorate cu culori diferite”.

                                                               Istorie

                              Forma generală a unei funcÅ£ii backtracking

     Implementarea recursivă a algoritmului furnizat de metoda backtracking, este mai naturală ÅŸi deci mai uÅŸoară. Segmentul de stivă pus la dispoziÅ£ie prin apelul funcÅ£iei este gestionat în mod automat de sistem. Revenirea la pasul precedent se realizează în mod natural prin închiderea nivelului de stivă.

void BK(int k)                                               //k-poziÅ£ia din vector care se completează

{

 int i;

 for (i=1; i<=nr_elemente_Sk; i++)          //parcurge elementele mulÅ£imii Sk

         {

         v[k]=i;                                             //selectează un element din mulÅ£ime

         if (validare(k)==1)                             //validează condiÅ£iile de continuare ale problemei

             {

              if (solutie(k)==1)                                   //verifică dacă s-a obÅ£inut o soluÅ£ie

              afisare(k);                                           //afiÅŸează soluÅ£ia

              else

              BK(k+1);                                         //reapelează functia pentru poziÅ£ia k+1

              }

          }                                           //dacă nu mai există nici un element neselectat în mulÅ£imea Sk,

 }                                     //se închide nivelul de stivă ÅŸi astfel se revine pe poziÅ£ia k-1 a vectorului                                                                      

                                   //execuÅ£ia funcÅ£iei se încheie.

     -după ce s-au închis toate nivelurile stivei, înseamnă că în vectorul v nu mai poate fi selectat nici un elemente din multimile Sk.

                                               Problema celor n dame

     Fiind dată o tablă de ÅŸah de dimensiune nxn, se cere să se aranjeze cele n dame în toate modurile posibile pe tabla de ÅŸah, astfel încât să nu se afle pe aceeaÅŸi linie, coloană, sau diagonală (damele să nu se atace).

​

Exemplu pentru n=4 se obţin două soluţii:

Soluţie:

  • pe linia k nu trebuie să mai fie o altă damă: această condiÅ£ie este satisfăcută datorită modului de reprezentare a soluÅ£iei;

  • pe coloana corespunzătoare, care este S[k] nu trebuie să mai fie o altă damă: S[k]≠S[i], pentru iÎ[1,k-1];

  • oricare dintre damele aÅŸezate nu trebuie să se afle pe o acceiaÅŸi diagonală cu dama de pe linia k: pentru iÎ[1,k-1] damele aflate pe poziÅ£iile (i,S[i]) respectiv (k,S[k]) nu sunt pe acceaÅŸi diagonală dacă |i-k|≠|S[i]-S[k]|.

Programul C++

Introducere
Istorie
Prezentare generala
Descrierea metodei
Forma generala

                                                  Descrierea metodei

     În general vom modela soluÅ£ia problemei ca un vector v=(v1,v2,v3,...,vn) în care fiecare element vk aparÅ£ine unei mulÅ£imi finite ÅŸi ordonate Sk, cu k=1,n. În anumite cazuri particulare, mulÅ£imile S1 ,S2, S3,...,Sn pot fi identice . Procedăm astfel:

     1. La fiecare pas k pornim de la o soluÅ£ie parÅ£ială v=( v1,v2,v3,...,vk-1) determinată până în acel moment ÅŸi încercăm să extindem această soluÅ£ie adăugând un nou element la sfârÅŸitul vectorului.

     2. Căutăm în mulÅ£imea Sk , un nou element.

     3. Dacă există un element neselectat încă, verificăm dacă acest element îndeplineÅŸte condiÅ£iile impuse de problemă, numite condiÅ£ii de continuare.

     4. Dacă sunt respectate condiÅ£iile de continuare, adăugăm elementul soluÅ£iei parÅ£iale.

     5. Verificăm dacă am obÅ£inut o soluÅ£ie completă. 

     - dacă am obÅ£inut o soluÅ£ie completă o afişăm ÅŸi se reia algoritmul de la pasul 1.

     - dacă nu am obÅ£inut o soluÅ£ie, k <----- k+1 si se reia algoritmul de la pasul 1.

     6. Dacă nu sunt respectate condiÅ£iile de continuare se reia algoritmul de la pasul 2.

     7. Dacă nu mai există nici un element neverificat în mulÅ£imea Sk înseamnă că nu mai avem nici o posibilitate din acest moment, să construim soluÅ£ia finală aÅŸa că trebuie să modificăm alegerile făcute în prealabil, astfel k <----- k-1 ÅŸi se reia problema de la pasul 1.

     Revenirea în caz de insucces sau pentru generarea tuturor soluÅ£iilor problemei, a condus la denumirea de ”backtracking” a metodei, traducerea aproximativă ar fi “revenire în urmă”.

       Proiect de atestat

             Metoda de programare backtracking

   Îndrumător:                    

       Prof. Ududec Marius

Elev:

    SăvuÈ› Daniel-Serafim

     Rezolvarea unei probleme poate conduce la obÅ£inerea unui număr foarte mare de soluÅ£ii posibile. Nu întotdeauna ne interesează toate soluÅ£iile, ci numai o parte dintre ele, care îndeplinesc anumite condiÅ£ii.  In astfel de cazuri este indicată folosirea metodei Backtracking (BKT).

     Problemele care se rezolvă prin metoda BKT generează soluÅ£ii care îndeplinesc anumite condiÅ£ii specifice problemei, denumite condiÅ£ii de validare (condiÅ£ii interne).

SoluÅ£iile posibile care îndeplinesc condiÅ£iile de validare sunt numite soluÅ£ii rezultat (soluÅ£ii finale).

     Unele probleme impun obÅ£inerea unei singure soluÅ£ii, numită soluÅ£ia optimă.

ImaginaÅ£i-vă că astăzi este ziua vostră ÅŸi aveÅ£i invitaÅ£i. AranjaÅ£i o masă frumoasă, apoi vă gândiÅ£i cum să vă aÅŸezaÅ£i invitaÅ£ii la masă. AÅ£i vrea să ÅŸtiÅ£i toate posibilităţile de aÅŸezare a invitaÅ£ilor la masă, dar realizaÅ£i în acelaÅŸi timp că trebuie să Å£ineÅ£i seama ÅŸi de preferinÅ£ele lor. Printre invitaÅ£i există anumite simpatii dar ÅŸi unele antipatii, de care doriÅ£i neapărat să Å£ineÅ£i seama, pentru ca petrecerea să fie o bucurie pentru toÅ£i.

     Să ne gândim cum procedaÅ£i pentru a identifica toate posibilităţile de a plasa invitaÅ£ii la masă. ÎncepeÅ£i prin a scrie niÅŸte cartonaÅŸe cu numele invitaÅ£ilor.

     AlegeÅ£i un invitat. Pentru a-l alege pe al doilea, selectaÅ£i din mulÅ£imea cartonaÅŸelor rămase un alt invitat. Dacă ÅŸtiÅ£i că cele două persoane nu se agreează, renuntaÅ£i la cartonaÅŸul lui ÅŸi alegeÅ£i altul ÅŸi aÅŸa mai departe. Se poate întâmpla ca la un moment dat, când vreÅ£i să alegeÅ£i cartonaÅŸul unui invitat să constataÅ£i că nici unul dintre invitaÅ£ii rămaÅŸi nu se potriveÅŸte cu ultima persoană slectată până acum. Cum procedaÅ£i? SchimbaÅ£i ultimul invitat plasat cu un invitat dintre cei rămaÅŸi ÅŸi încercaÅ£i din nou, dacă nici aÅŸa nu reuÅŸiti, schimbaÅ£i penultimul invitat cu alcineva ÅŸi încercaÅ£i din nou ÅŸi aÅŸa mai departe până când reuÅŸiÅ£i să plasati toÅ£i invitaÅ£ii.           Înseamnă că aÅ£i obÅ£inut o soluÅ£ie. Pentru a obÅ£ine toate celelalte soluÅ£ii, nu vă rămâne decât să o luaÅ£i de la început. AveÅ£i cam mult de muncit, iar dacă numărul invitaÅ£ilor este mare...operaÅ£iunea devine foarte anevoioasă. Iată de ce aveÅ£i nevoie de un calculator ÅŸi cunoÅŸtinÅ£e de programare.

                                                   Prezentare generală

Mai 2017

Suceava

bottom of page