Unelte utilizator
Bara de navigare
laboratoare:laborator-12
Aceasta e o versiune anterioară a paginii.
Cuprins
Laborator 12: Backtracking
1 Obiectivele laboratorului
- Înțelegerea noțiunii de backtracking
- Implementarea metodei backtracking in rezolvarea problemelor
2 Backtracking
2.1 Definiție
Noțiunea de backtracking se referă la utilizarea unui algoritm recursiv pentru soluționarea unei probleme ce admite soluții parțiale. Se începe cu una din bucățile de soluție disponibile și se avansează până la construirea soluției complete. Dacă una din rutele de construcție disponibile nu duce nicăieri, se merge înapoi (backtrack) și se încearcă altă cale. Dacă niciuna din rute nu dă o soluție, atunci problema nu este rezolvabilă.
- poza backtracking#
2.2 Algoritm
Algoritmul generat este următorul:
- Se alege un punct de start
- Cât timp problema nu este rezolvată:
- Pentru fiecare cale(parte din soluție disponibilă) de la punctul de start:
- Se verifică dacă ruta aleasă este bună (nu invalidează condiția de rezolvare)
- Daca da, se adaugă la soluția în construcție și se apelează recursiv algoritmul pentru restul problemei
- Dacă apelul recursiv reușește să găsească o soluție completă,algoritmul se încheie. Dacă nu, ruta aleasă se elimină din soluție și se alege alta.
- Daca niciuna din căile disponibile nu este bună, nu există soluție (pentru punctul de start ales).
asda
laboratoare/laborator-12.1487249999.txt.gz · Ultima modificare: 2017/02/16 14:59 de către sebastian.cancel
Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
