metoda backtracking

38
Metoda Backtracking Clasificarea metodelor de programare Definiţie Exemple de probleme Problema celor N dame Metoda Implementarea

Upload: emerald-roach

Post on 30-Dec-2015

198 views

Category:

Documents


12 download

DESCRIPTION

Metoda Backtracking. Clasificarea metodelor de programare Definiţie Exemple de probleme Problema celor N dame Metoda Implementarea. Clasificarea metodelor de programare. Algoritmi recursivi simpli Algoritmi Backtracking Algoritmi Divide et Impera Algoritmi de programare dinamică - PowerPoint PPT Presentation

TRANSCRIPT

Metoda Backtracking

Clasificarea metodelor de programareDefiniţieExemple de problemeProblema celor N dame

Metoda Implementarea

Clasificarea metodelor de programare

Algoritmi recursivi simpli Algoritmi Backtracking Algoritmi Divide et Impera Algoritmi de programare dinamică Algoritmi Greedy Algoritmi Branch and bound

Backtracking - definiţie

Să presupunem că trebuie să luaţi o serie de decizii, având mai multe variante de ales, unde Nu aveţi destule informaţii pentru a şti ce alegeţi Fiecare decizie ne conduce la un nou set de

variante posibile Unele succesiuni de variante (posibil mai multe

decât una) poate fi soluţia problemei taleBacktracking este o metodă ce încearcă

diferite succesiuni de decizii, înainte de a găsi una care “merge”

Rezolvarea unui labirint

Într-un labirint de dimensiune m*n, gasiţi o cale de a – l parcurge de la început la sfârşit

La fiecare intersecţie trebuie să decideţi între 3 sau mai multe variante: Să mergeţi înainte Să mergeţi la stânga Să mergeţi la dreapta

Nu aveţi destule informaţii pentru a alege corect

Fiecare alegere duce la un nou set de alegeri

Una sau mai multe secvenţe de variante poate (sau nu) să conducă la o soluţie

Multe tipuri de labirinturi se pot rezolva cu backtracking

Colorarea hărţii

Doriţi să coloraţi o hartă în 4 culori: Roşu, galben, albastru şi verde

Oricare 2 ţări vecine trebuie să fie colorate în culori diferite

Nu aveţi destule informaţii pentru a şti ce culori alegeţi

Fiecare decizie ne conduce la un nou set de variante posibile

Una sau mai multe secvenţe de variante poate (sau nu) să conducă la o soluţie

Multe tipuri de colorări de hărţi se pot rezolva cu backtracking

Rezolvarea unui puzzle

În acest puzzle toate găurile înafară de una sunt colorate cu aceaşi culoare

Poţi sări doar de pe o gaură pe alta

Găurile pe care sari se eliminăObiectul este de a elimina

toate găurile inafară de unaNu aveţi destule informaţii

pentru a sări corectFiecare decizie ne conduce la

un nou set de variante posibileUna sau mai multe secvenţe de

variante poate (sau nu) să conducă la o soluţie

Multe tipuri de puzzle-uri se pot rezolva cu backtracking

Utilizarea stivei

Acest capitol introduce tipul de dată stivă.

Multe exemple de lucru cu stiva sunt prezentate în acest capitol.

Această prezentare arată utilizarea stivei în algoritmul backtracking de rezolvare a problemei celor N-Dame.

Problema celor N-Dame

Presupune că ai 8 dame...

...şi o tablă de şah

Problema celor N-Dame

Se pot amplasa cele 8 dame pe tabla de şah astfel încât oricare 2 dame să nu se atace

??

Problema celor N-Dame

Două dame să nu fie amplasate pe acelaşi rând...

Problema celor N-Dame

Două dame să nu fie amplasate pe acelaşi rând sau pe aceiaşi coloană...

Problema celor N-Dame

Două dame să nu fie amplasate pe acelaşi rând sau pe aceiaşi coloană sau pe aceiaşi diagonală.

Problema celor N-Dame

Numărul damelor şi dimensiunea tablei de şah poate varia.

N dameN râ

ndur

i

N coloane

Problema celor N-Dame

Vom scrie un program care va încerca să găsească soluţia de a plasa N regine pe N*N tablă de şah

Dacă puteţi rularun ega orvga graphics, executaţidublu click pe icoană

Package

Cum lucrează programul

Programul utilizează o stivă pentru a reţine poziţia fiecărei regine.

Cum lucrează programul

De fiecare dată programul alege să aşeze o regină pe tablă, iar poziţia nouă este memorată într-o înregistrare care este aşezată în stivă

RÂND 1, COL 1

Cum lucrează programul

Deasemenea vom avea şi o variabilă care săreţină câte rânduri au fost utilizate

RÂND 1, COL 1

1OCUPATE

Cum lucrează programul

De fiecare dată când vom încerca să aşezăm o nouă regină în rândul următor, vom începe prin a amplasa regina în prima coloană....

RÂND 1, COL 1

1OCUPATE

RÂND 2, COL 1

Cum lucrează programul

...dacă este un conflict cu o altă regină atunci aşezăm noua regină pe coloana următoare

RÂND 1, COL 1

1OCUPATE

RÂND 2, COL 2

Cum lucrează programul

Dacă apare un nou conflict atunci regina va fi mutată pe următoarea poziţie la dreapta

RÂND 1, COL 1

1OCUPATE

RÂND 2, COL 3

Cum lucrează programul

Atunci când nu mai există conflicte programul se opreşte şi adăugăm o valoare la variabila care reţine nr. rândurilor

RÂND 1, COL 1

2OCUPATE

RÂND 2, COL 3

Cum lucrează programul

Să privim rândul nr. 3. Pe prima poziţie pe care o încercăm este conflict.....

R ÂND 1, COL 1

2 OCUPATE

R ÂND 2, COL 3

RÂND 3, COL 1

Cum lucrează programul

... Atunci trecem pe coloana 2, dar şi aici este un conflict......

RÂND 1, COL 1

2 OCUPATE

R ÂND 2, COL 3

RÂND 3, COL 2

Cum lucrează programul

...şi vom trece pe pe a treia coloană unde este un nou conflict...

RÂND 1, COL 1

2OCUPATE

RÂND 2, COL 3

RÂND 3, COL 3

Cum lucrează programul

...se trece atunci în coloana 4, unde din cauza unui nou conflict, vom încerca să trecem într-o coloană la stânga...

RÂND 1, COL 1

2 OCUPATE

RÂND 2, COL 3

RÂND 3, COL 4

Cum lucrează programul

...dar aici nu avem cum să ne ducem.

RÂND 1, COL 1

2 OCUPATE

RÂND 2, COL 3

RÂND 3, COL 4

Cum lucrează programul

Când ieşim de pe tablă pe rândul respectiv:

Coborâm în stivă,

Reducem rândul cu 1

Şi continuăm să lucrăm în acest rând

RÂND 1, COL 1

1OCUPATE

RÂND 2, COL 3

Cum lucrează programul

Acum continuăm să lucrăm pe rândul 2 deplasând regina la dreapta.

RÂND 1, COL 1

1OCUPATE

RÂND 2, COL 4

Cum lucrează programul

Aici nu avem conflicte şi atunci incrementăm variabila cu 1 şi trecem la rândul 3.

RÂND 1, COL 1

2OCUPATE

RÂND 2, COL 4

Cum lucrează programul

În acest rând începem cu prima coloană.

RÂND 1, COL 1

2 OCUPATE

RÂND 2, COL 4

RÂND 3, COL 1

Descrierea metodei

Transformările care pot fi aplicate unei configuraţii sunt: Atribuie şi avansează

mai există valori neconsumate, valoarea aleasă respectă condiţiile de continuitate valoarea se atribuie vectorului soluţie se avansează la următoarea componenta xk+1

Încercare eşuată mai există valori neconsumate valoarea aleasă nu respectă condiţiile de continuitate valoarea se consumă nu se avansează la următoarea componenta

Revenire toate valorile au fost consumate se revine la componenta anterioară xk-1 se încearcă atribuirea unei noi valori acestei componente pentru componenta xk se încearcă din nou toate valorile posibile

Revenire după construirea unei soluţii toate componentele vectorului au primit valori care satisfac condiţille interne (s-a găsit o soluţie) se revine la ultima componentă xn se atribuie acesteia o nouă valoare caz particular al revenirii

Terminarea algoritmului are loc atunci când: toate valorile pentru prima componentă s-au consumat se încearcă o revenire, lucru care este imposibil (k=0) nici una din cele 4 transformări nu mai poate fi apicată încercarea de trecere pe poziţia (k=0) este utilizată ca şi condiţie de terminare a algoritmului

procedure Retsol; // listează soluţia determinată pentru i=1, n scrie x[i]

function Cont(k): boolean; //verifică dacă s-au determinat toate elementele din mulţime ce constituie vectorul soluţieCont←True // iniţializare optimistă pentru i=1, k-1 // se alege k-1 pentru a evita situaţia de a ajunge la n+1 daca x[i]=x[k] sau abs(k-i)=abs(x[k]-x[i])atunci // condiţiile interne (de continuitate) Cont←False

procedure back;k←1pentru i=1, n // se construieşte configuraţia iniţială x[i] ← 0cât timp k>0 // k=0 înseamnă terminarea căutării dacă k=n+1 atunci // configuraţia este de tip soluţie

Retsol; // reţine soluţia k←k-1; // revenire după soluţie (T4) alltfel dacă x[k]<n atunci // mai există valori neconsumate x[k] ←x[k]+1 // se alege o nouă valoare din mulţime, valoarea fiind considerată astfel consumată dacă Cont(k) atunci // se verifică condiţiile de continuitate

k←k+1 // atribuie şi avansează (T1) altfel// nu face nimic // încercare eşuată (T2) altfel // revenire (T3) x[k] ←0; k←k-1;

Programul principal:start

citeşte n //citeşte nr. de elemente al mulţimii Apentru i=1, n //citeşte elementele mulţimii A citeşte a[i]back;

stop

Watching the program work

Puteţi da dublu clik pe icoana de mai jos pentru a vedea din nou programul cum funcţionează:

Package

Recapitulare

Aplicaţia pe care am văzut-o este backtracking.

Cheia după care funcţionează backtracking –ul este: fiecare posibilitate se memorează pe stivă

Când s-au consumat toate posibilităţile pentru soluţia respectivă, se coboară în stivă şi se aleg alte posibilităţi pentru acestă soluţie.