Tehnica Backtracking

Conf.dr. Luminiţa Duţă

Când se utilizează?

� Folosim această tehnică de programareatunci când nu dispunem de o altă metodă de rezolvare a unei probleme, iar soluţiileproblemei pot fi scrise sub forma unui şirrezultat din produsul cartezian al n mulţimi:

x1,x2,…,xn unde

x1€ A1

x2 € A2

……………..

xn € An

De ce Backtracking?

� Pentru că nu putem rezolva altfel problema

� Pentru că problema are mai multe soluţii care

sunt foarte greu de determinat

� Pentru că avem nevoie de TOATE soluţiileproblemei

� Pentru că ştim să programăm

� Pentru că nu ne grăbeşte nimeni

Probleme ce se rezolvă prin BKT

� Problema reginelor

� Problema labirintului

� Problema hărţilor

� Problema fotografiei

� Problema decupajului

� Problema comis-voiajorului

� Problema plăţii în bancnote

Problema reginelor

�Fiind dată o tablă de şah de dimensiune NxN se cer toateposibilităţile de aranjare a N regine, astfel încât acestea să nu se atacereciproc

Pentru 8 regine

� Pe o tablă de şah de 64 de pătrate sunt

4.426.165.368 moduri posibile de a aşeza 8

regine !!

� Dacă ţinem însă cont că reginele nu se pot

aşeza pe aceeaşi linie sau coloană, mai

rămân de verificat “doar” 40.320 (8!)

posibilităţi de aşezare, astfel încât reginele sănu se atace reciproc.

Soluţie

� Problema are mai multe soluţii!

� Iată una dintre ele:

Notaţii utilizate în scrierea BKT

� k – nivelul curent al stivei

� n – nr de nivele ale stivei (nr de regine)

� st – vectorul stivă

� as - variabila logica “exista succesor”

� back( ) – funcţia backtracking

� init( ) – funcţia de iniţializare a stivei

� succesor( ) – fct. de validare a succesorului

� valid( ) – fct de validare a conditiilor problemei

� solutie( ) – fct de validare a solutiei

� tipar( ) – fct pt afişarea soluţiei găsite

Şablonul tehnicii BKT

void back(){int as;k=1;init();while (k>0){do { } while ((as==succesor()) && !valid());if (as)if (solutie()) tipar();else {k++; init(); }

else k--;}}

Rezolvarea problemei reginelor

(funcţiile init şi succesor)

void init ( ){ st[k]=0; }

int succesor ( ){ if (st[k]<n)

{st[k]++;return 1;

}else return 0;}

Rezolvare (funcţia de validare)

int valid( )

{ for(int i=1; i<k; i++)

if ( (st[k]==st[i]) || (abs(st[k]-st[i])==abs(k-i)) )

return 0;

return 1;

}

Rezolvare (funcţia solutie şi tipar)

int solutie ( )

{return k==n;}

void tipar( )

{for (int i=1; i<=n; i++) cout<<st[i];

cout<<endl;

}

Rezolvare (funcţia BKT)

void back(){int as;k=1;init();while(k>0){do { } while ((as=succesor()) && !valid());if (as)if (solutie()) tipar();else {k++; init(); }

else k- -;}

}

Rezolvare (progr principal)

void main( )

{ cout<<"n="; cin>>n;

back( );

}

Problema colorării hărţilor

�Fiind dată o hartă cu n ţări, se certoate soluţiile de colorare a hărţii utilizând cel mult 4 culori, astfel încât două ţări cu frontiera comună să fie colorate diferit.

Problema comis-voiajorului

� Un comis – voiajor trebuie să viziteze un număr n de oraşe. Iniţial, acesta se aflăîntr-unul dintre ele, notat cu 1.

� Comis – voiajorul doreşte să nu treacă de două ori prin acelaşi oraş, iar la întoarceresă revină în oraşul 1. Cunoscând legăturileexistente între oraşe, se cere să se tipărească toate drumurile posibile pe care le poate efectua comis – voiajorul.

Problema labirintului

� Se dă un labirint sub formă de matrice cum linii şi n coloane. Fiecare element al matricei egal cu 0 reprezintă o cameră a labirintului. Elementele egale cu 1 reprzintă obstacole. Într-una din camere, de coordonate x şi y, se află un om. Se cere să se găsească toate ieşirile dinlabirint.

Problema fotografiei

� O fotografie alb – negru este prezentatăsub forma unei matrice binare. Ea înfăţisează unul sau mai multe obiecte. Porţiunile corespunzătoare obiectului în matrice au valoarea 1.

� Se cere să se determine dacă fotografiareprezintă unul sau mai multe obiecte.

Câte obiecte sunt în fiecare din cele două imagini?

=

1111

1111

1000

0011

A

=

0001

1110

1000

0110

A

Concluzii

� Tehnica backtracking este folosită în

problemele de optimizare.

� Programarea prin tehnica backtracking se

utilizează în programarea roboţilor autonomi,

viziune artificială, prelucrarea imaginilor,

controlul inteligent al traficului, realizarea

reţelelor de calculatoare, tehnici de brokeraj,

etc.