Metoda Backtracking
-
Upload
emerald-roach -
Category
Documents
-
view
198 -
download
12
description
Transcript of Metoda Backtracking
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
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 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
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