Metoda Backtracking ( Reluării )

Definiție :

Metoda backtracking se aplică problemelor în care soluţia poate fi reprezentată sub forma unui vector – x = (x1, x2, x3, …xk,… xn) € S, unde S este mulţimea soluţiilor problemei şi S = S1 x S2 x… x Sn, şi Si sunt mulţimi finite având s elemente si xi € si , (¥)i = 1..n.

Particularități :

  • Pentru fiecare problemă se dau relaţii între componentele vectorului x, care sunt numite condiţii interne; soluţiile posibile care satisfac condiţiile interne se numesc soluţii rezultat. Metoda de generare a tuturor soluţiilor posibile si apoi de determinare a soluţiilor rezultat prin verificarea îndeplinirii condiţiilor interne necesită foarte mult timp.

            Metoda backtracking evită această generare şi este mai eficientă. Elementele vectorului x, primesc pe rând valori în ordinea crescătoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica îndeplinirea unor condiţii de continuare referitoare la x1…x[k-1]. Daca aceste condiţii nu sunt îndeplinite, la pasul k, acest lucru înseamnă ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o soluţie rezultat.

  • Metoda backtracking construieşte un vector soluţie în mod progresiv începând cu prima componentă a vectorului şi mergând spre ultima cu eventuale reveniri asupra atribuirilor anterioare.

  • Problemele rezolvate prin această metodă necesită timp mare de execuţie, de aceea este indicat sa se folosească metoda numai daca nu avem alt algoritm de rezolvare.

Domeniu de utilizare :

  • Această tehnică poate fi utilizată pentru rezolvarea problemelor de căutare, putînd fi folosită pentru generarea tuturor soluțiilor posibile.

  • Metoda poate fi folosită la rezolvarea următoarelor probleme : ​

  • generarea permutărilor unei mulțimi.

  • generarea aranjamentelor unei mulțimi.

  • generarea submulțimilor unei mulțimi.

  • generarea produsului cartezian a n mulțimi

  • culoarea țărilor de pe o hartă astfel încît oricare două țări vecine să aibă culori diferite.

  • aranjarea a n regine pe o tablă de șah de dimensiune n fără ca ele să se atace.

  • MBtracking Schema

 

 Verifica Cunostinele  Test

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s