Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 12: Backtracking
Traseu:
laboratoare:laborator-12

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune 		Versiuni anterioare
laboratoare:laborator-12 [2017/02/16 15:44]
sebastian.cancel 		laboratoare:laborator-12 [2017/05/18 22:41]
iulian.matesica
Linia 7: Linia 7:
 =====2 Backtracking===== =====2 Backtracking=====
 ====2.1 Definiție==== ====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ă. +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#+{{ :laboratoare:backtracking.png |}}
 \\  \\ 
  
Linia 29: Linia 29:
 Dată fiind o matrice 2D de caractere, să se verifice dacă există un cuvânt în matrice. Dacă da,să i se afișeze calea. Se permite mișcarea în toate cele 8 direcții. Dată fiind o matrice 2D de caractere, să se verifice dacă există un cuvânt în matrice. Dacă da,să i se afișeze calea. Se permite mișcarea în toate cele 8 direcții.
 \\  \\ 
-# poza matrice#+{{ :laboratoare:horizon.png?300 |}}
 \\  \\ 
 Procedeu:\\  Procedeu:\\ 
Linia 46: Linia 46:
 Se notează cu 0 celulele neutilizate.\\  Se notează cu 0 celulele neutilizate.\\ 
  
-#poza matrice 0 si 12345#+{{ :laboratoare:matrice0.png?300 |}}
  
 ===3.2 Problema spargerii cuvintelor=== ===3.2 Problema spargerii cuvintelor===
-Fiind dar un și de caractere și un dicționar de cuvinte, să se verifice dacă șirul poate fi spart în cuvinte din dicționar și ,dacă da, să se afișeze acestea cu spațiu între ele. +Fiind dar un și de caractere și un dicționar de cuvinte, să se verifice dacă șirul poate fi spart în cuvinte din dicționar și ,dacă da, să se afișeze acestea cu spațiu între ele.\\  
-#poza dictionar#+ 
 +{{ :laboratoare:word.png?600 |}}
  
 Procedeu naiv: Procedeu naiv:
Linia 59: Linia 60:
 *Dacă la un moment dat nu se mai pot găsi cuvinte, se dă înapoi și se elimină ultimul cuvânt din răspuns și se continuă adăugarea de caractere de la el înainte *Dacă la un moment dat nu se mai pot găsi cuvinte, se dă înapoi și se elimină ultimul cuvânt din răspuns și se continuă adăugarea de caractere de la el înainte
 *Dacă s-a ajuns la sfârșitul șirului de intrare și toate caracterele sunt intr-un cuvânt din răspuns, înseamnă că șirul a fost spart cu succes. *Dacă s-a ajuns la sfârșitul șirului de intrare și toate caracterele sunt intr-un cuvânt din răspuns, înseamnă că șirul a fost spart cu succes.
 +
 \\  \\ 
 Procedeu cu programare dinamică: Procedeu cu programare dinamică:
Linia 64: Linia 66:
 *De fiecare dată când un string construit nu poate fi descompus în cuvinte, il ținem minte pentru a nu-l mia verifica data viitoare. *De fiecare dată când un string construit nu poate fi descompus în cuvinte, il ținem minte pentru a nu-l mia verifica data viitoare.
 *Mai jos este un exemplu cu ce s-ar întâmpla fără programarea dinamică *Mai jos este un exemplu cu ce s-ar întâmpla fără programarea dinamică
 +
 +{{ :laboratoare:word2.png |}}
 +
 +====4 Exerciţii====
 +  - Generarea produsului cartezian A<sup>N</sup> (interpretare: toate numerele de N cifre, dar cu cifrele alese numai din mulțimea A). Exemplu: A = {1,2,3}, N = 6;
 +  - Generarea tuturor permutărilor de N;
 +  - Generarea tuturor combinărilor/aranjamentelor de N luate câte k;
 +  - Problema calului pe tabla de şah;
 +  -* Problema turelor pe tabla de şah;
 +  - Problema reginelor pe tabla de şah;
 +  - Găsirea unui lanţ Hamiltonian într-un graf;
 +  -* Găsirea unui ciclu Hamiltonian într-un graf;
 +  -** Problema comisului-voiajor;
 +
 +==== 5. Exerciţii de laborator (Linux) ====
 +Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab12_backtracking-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. 
 +
 +=== Linux===
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
 +
 +  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab12_backtracking-skel.zip%%''
 +  * ''%%unzip lab12_backtracking-skel.zip%%''
 +
 +Pentru compilare folositi comanda ''%%make%%''.
  
laboratoare/laborator-12.txt · Ultima modificare: 2017/05/18 22:41 de către iulian.matesica

Unelte pagină

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
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki