Metoda Backtracking

Descrierea Metodei

Metoda BackTracking se aplica in probleme de cautare. Metoda este adecvata problemelor in care solutia se poate exprima ca un n-uplu (x₁ x₂ x_n) , x_i S_i - finita , i = 1,n . Solutia trebuie sa satisfaca sau sa minimizeze / maximizeze o functie criteriu P(x₁ x₂ x_n). Uneori se solicita toate solutiile.Daca |S₁| = m₁ , |S₂| = m₂ . . . |S_n| = m_n , atunci numarul total de n-uple este m=m₁ m₂ m_n. Metoda nu asigura ca nu se vor incerca toate cele m posibilitati , dar practic reduce mult numarul de n-uple care se incearca prin folosirea functiei criteriu. Ideea este de a folosi o forma partiala a functiei criteriu P_i(x₁ x₂ x_i) care elimina familii intregi de n-uple. Daca de exemplu solutia partiala (x₁ x₂ x_i) nu are nici o sansa de a conduce la o solutie completa , toate cele m_i+1 m_i+2 m_n n-uple cu (x₁ x₂ x_i) pe primele i pozitii se abandoneaza.

Spatiul solutiilor. Restrictii.

S₁ S₂ S_n se numeste spatiul solutiilor problemei, iar restrictiile de forma (x₁,x₂,,x_n) S₁ S₂ S_n se numesc restrictii explicite ; restrictiile (x₁, x₂ ,,x_n) satisfacind P se numesc restrictii implicite

Exemplu 1: Problema celor 8 dame pe tabla de sah : Data fiind S==multimea celor 8 dame si o tabla de sah ( 8 linii si 8 coloane) sa se plaseze cele 8 dame asfel incit sa nu existe doua dame pe aceeasi linie, coloana sau diagonala.

O solutie poate fi exprimata printr-un 8-uplu X=(x₁,x₂,.x₈) unde x_i = coloana pe care se plaseaza dama I ( linia pe care se plaseaza dama I este i )

- Deoarece S_i = S, i=1,.,8 rezulta ca spatiul de solutii S S S S are 8⁸ 8-uple;

de 8ori

- Restrictia explicita: 1 x_i 8 , i=1,.,8

- Restrictii implicite -o singura dama pe o coloana : x_i x_j , ( ) i j, i,j=1,.,8

-o singura dama pe o diagonala : |i-j| |x_i-x_j| , ( ) i j, i,j=1,.,8

Exemplu 2: Suma fixa de submultimi : Date fiind S=, w_i i n si M-o valoare M > 0, sa se determine toate submultimile S' S, S`= cu proprietatea x₁+x₂++x_k=M

Cazul n=4 : S= M=31 S=(11,13,24,7); solutii : X₁=(11,13,7), X₂=(24,7) sau exprimate prin indicii i ai elementelor w_i I S, X₁=(1,2,4), X₂=(3,4)

Pentru cazul exprimarii solutiilor prin indicii i ai elementelor w_i I S restrictiile sint urmatoarele:

- Restrictii explicite 1 x_i n, , i=1,.,n

- Restrictii implicite: x_i x_j si =M

x_i<x_i+1 pentru a evita generarea aceleasi multimi

ex.:=

O alta abordare: X=(x₁,x₂,..x_n), x_i = 0 sau 1; = M

Spatiul solutiilor este de dimensiune 2ⁿ.

Organizarea sub forma de arbore a spatiului solutiilor

Metoda backtracking rezolva o problema prin cautarea sistematica a solutiei in spatiul solutiilor. Conceptual , aceasta cautare foloseste o organizare a spatiului solutiilor sub forma unui arbore.

Exemplul 1 : Problema celor n-dame

folosim n=4

In acest arbore arcele de la nivel i la i+1 sint etichetate cu valori x_i.

Spatiul solutiilor = secventele de etichete de la radacina la nodurile frunza.Nodurile sint etichetate in

sensul parcurgerii depth-first.

Exemplul 2: Suma de submultimi (11,13,24,7) M=31

- traversare breadth-first.

Notiuni :

-starea problemei - fiecare nod intr-un arbore defineste o stare a problemei;

-spatiul starilor - toate drumurile de la radacina la noduri;

-stari solutie - acele stari (noduri) pentru care drum de la radacina la nod etichetat cu un n-uplu;

-stari raspuns - stari care satisfac conditiile implicite P;

-arborele spatiului starilor - spatiul starilor problemei organizat sub forma de arbore.

Arborii construiti astfel sint arbori statici si nu depind de instanta problemei. Exista arbori dinamici care depind de problema. Un exemplu ar fi cazul in care functie de valoarea lui x₁ se decide daca la primul nivel este x₁ sau x₂ s.a.m.d.