Metoda Backtracking

Front

Ce este metoda backtracking?

Back

O tehnică de programare aplicabilă algoritmilor care oferă mai multe soluții și ca rezultat obținerea tuturor soluțiilor problemei.

Front

Cum se memorează fiecare soluție în metoda backtracking?

Back

Fiecare soluție se memorează într-o structură de date implementată cu ajutorul unui vector.

Front

Ce se completează în algoritmul backtracking?

Back

Vectorul pas cu pas, trecând astfel prin soluții parțiale.

Front

Ce sunt condițiile de validare în metoda backtracking?

Back

Condiții pe care o soluție trebuie să le îndeplinească pentru a fi considerată validă.

Front

Ce reprezintă o soluție validă în contextul backtracking-ului?

Back

O soluție care îndeplinește toate condițiile de validare.

Front

Ce este produsul cartezian S1xS2x...Sn?

Back

Se numește spațiul soluțiilor posibile.

Front

Care este motivul principal pentru care metoda backtracking nu este întotdeauna utilă?

Back

Numărul foarte mare de soluții posibile.

Front

Care sunt pașii generali în algoritmul backtracking?

Back

1. Pornim de la o soluție parțială. 2. Căutăm un nou element. 3. Verificăm condițiile de continuare. 4. Adăugăm elementul soluției parțiale. 5. Verificăm dacă am obținut o soluție completă. 6. Repetăm algoritmul dacă nu sunt respectate condițiile.

Front

Ce face funcția de validare în metoda backtracking?

Back

Verifică dacă soluția construită până la un pas reprezintă o soluție parțială validă.

Front

Ce se întâmplă dacă nu mai există elemente neselectate în mulțimea Sk?

Back

Se închide vectorul și se revine pe poziția k-1 a vectorului.