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++
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