Mic tutorial Backtracking - part 2: Bkt a la poli

Continuand tutorialul de aici, cu backtracking frumos si clar, it's time to fuck it up gandind mai complex si mai abstract si mai nepractic.

NOTA IMPORTANTA: asta e cam ce am inteles eu citind in graba laboratorul nostru de PA. Ofc I might be wrong. In plus, asta e doar ideea in mare, si nu doar gandire abstracta si pseudocod, ci si solutii de implementare practica. Daca aveti prea mult timp liber, exista carti intregi despre backtracking ;)

Ideea e ca acum nu mai vedem o lista de valori posibile pe care le permutam, ci avem un fel de graf astfel incat:

• nodurile sunt liste cu valori posibile
• un arc intre 2 noduri reprezinta o restrictie intre 2 noduri, spre exemplu avem 2 noduri n1 si n2 cu arcul <, adica trebuie ca n1 < n2
• o solutie finala este o valoare data pentru noduri astfel incat toate restrictiile din arce sa fie respectate
  

Deci spre deosebire de bkt-u din postul anterior, vom avea o matrice cu valorile posibile pentru fiecare nod, o vom numi tot pos, unde pos[p] e practic o lista cu toate valorile ce pot fi puse in nodul p, iar n_pos este un vector cu numarul de valori pentru fiecare nod. Deci va arata ceva de genul:

void bkt(int p)

{
for (int i=0;i < n_pos[p];i++)

{
st[p]=pos[p][i];

if (verif(p)) //verificam la fiecare pas, nu la sfarsit

if (p==nr_cautat) //adica fiecare nod are o valoare
afiseaza(p)
else bkt(p+1);

}
}

Sa luam ca exemplu un sudoku. Cred ca toata lumea stie jocul, la cat pierdem timpul la cursuri cu el ;) (daca nu, cititi aici ). Vom reprezenta tabela de 9x9 ca o stiva de 81 de elemente, ce vor reprezenta practic nodurile alese de noi. In pos[p] vom baga toate numerele de la 1 la 9, iar nr_pos[i]=9 pt oricare i de la 1 la 81. Un bkt de genul asta va genera toate tabelele posibile. Ca sa rezolvam o tabela cu cateva valori predefinite, facem in asa fel incat pe pozitia p sa putem avea doar valoarea x data. Acum, ajungem in final la optimizari. Toate astea practic reduc din elementele din pos[p]. Practic inainte sa intram in backtracking, mai avem o functie care sa prelucreze matricea respectiva dupa niste reguli clare. Avem asa:

• NC - node consistency

Elimina elementele din pos[p] care incalca regulile din arce. In exemplul nostru cu sudoku, daca avem in o casuta un 1, atunci scoatem din pos-urile nodurilor de pe linia si coloana respectiva elementul 1, ramanand sa mai poata lua doar valorile 2..9.

• AC1 - arc consistency 1

Sa zicem ca avem un arc intre 2 noduri n1 si n2. Daca o valoare pusa in n1 face in asa fel incat sa nu mai mearga nici o valoare pusa in n2, atunci se elimina. Adica un fel de NC pe invers. Ca exemplu, sa zicem ca avem un alt joc, sa completam ceva cu cifre de la 1 la 9 intr-o relatie de ordine, si avem ceva gen n1 < n2 . Daca punem 9 in n1, atunci nu mai putem pune nimic in n2. Deci eliminam 9 din n1. Ah si chestia asta trebuie repetata de mai multe ori pentru fiecare nod in parte, terminandu-se cand nu se mai elimina nimic. De ce? Pai spre exemplu daca avem un n1 < n2 < n3 , atunci la primul loop elimina 9 din n1, si 9 din n2. La al 2lea loop elimina si 8 din n1.

• AC3 - arc consistency 3
  

E in esenta ca AC1, doar ca tinem cont sa nu repetam asta pe arce pe care nu mai e nevoie. Adica avem o coada Q cu toate arcele, si scoatem un arc, vedem daca putem elimina ceva, daca da il punem la loc in coada impreuna cu toate arcele nodului respectiv care nu sunt deja acolo, daca nu il lasam afara.

Mai pe romaneste, avem un nod n1, care are arc catre n2 si n2 are arc catre n3 (adica exista restrictii pentru n2 in functie de cum alegem n1, si pentru n3 in functie de cum alegem n2). In coada Q avem initial (n1,n2) si (n2,n3). Cautam daca e ceva de eliminat in n1, si nu e. In Q ramane (n2,n3). Cautam sa vedem daca e ceva de eliminat in n2, si gasim. Prin urmare, readaugam in Q (n1,n2) si (n2,n3).


Cam atata in mare despre backtracking. O singura recomandare pentru voi, programatori dragi. Cititi, face-ti-va o idee cu ce se mananca, faceti temele cu restrictiile lor idioate impuse, then think outside the box! Be creative and never follow the rules, even when it comes to programming. Un programator bun stie toti algoritmii astia, cand sa-i foloseasca si cum. Un programator foarte bun intelege algoritmii astia, si si-i formeaza pe ai lui si stilul lui de programare.

Intrebari? M-am exprimat aiurea pe undeva? Postati un comment si va voi lamuri cat de bine pot.