Greedy

Consideram urmatorul scenariu: esti cu prietenii si ati pus bani sa luati de baut. Va ajunge de o sticla de whiskey. Evident, o luati pe aia, desi probabil v-ati simti mai bine pentru mai mult timp cu o lada de bere si ceva chipsuri :P

Cam asta e treaba si cu algoritmul Greedy. El ofera solutia care, la pasul curent, pare cea mai buna, fara a se gandi la viitor (pasii urmatori). Pentru anumite categorii de probleme, ne ofera solutia optima intr-un timp foarte bun, pentru altele insa ne ofera o solutie mai putin optima.

Exemplul tipic este problema rucsacului. Avem un rucsac in care putem duce cel mult o masa mmax. Avem o serie de obiecte avand o masa masa[i] si o valoare val[i]. Pentru a lua doar obiectele cele mai importante, facem un raport valoare/masa, il sortam si luam pe rand obiectele cu raportul maxim.

Sunt doua tipuri de probleme: cea continua si cea discreta. La cea continua, putem lua si fragmente. Adica daca un obiect are masa 5kg, putem lua doar 2kg din obiectul respectiv. Asta merge cu greedy. Daca avem problema discreta, aka putem lua doar obiecte intregi, asta NU merge.

Sa vedem deci care e ideea de algoritm:

1. sortam obiectele dupa raportul val/masa - O (n log n)
2. parcurgem vectorul si cat timp nu s-a ajuns la o masa >mmax, mai adaugam un obiect (sau o parte dintr-un obiect) - O (n).

Complexitate: O(n log n).

Aveti aici o implementare mai simpla de greedy, care calculeaza la fiecare pas minimul dintre valorile ramase (complexitate O(n^2)) pentru a va face o idee generala cam cum merge.

Divide et impera

Incep cu un algoritm destul de simplu, care se face in liceu. Celebrul Divide et Impera... dezbina si cucereste. Think of it this way... esti la un party cu mult alcool. Daca combini toate bauturile si le dai pe gat, va fi foarte greu sa ramai treaz dupa, dar daca le imparti in paharele mici si le bei incet pe rand, atunci e mult mai usor si mai placut :)

Asa e si cu divide et impera... avem o problema grea, pe care o impartim in mai multe probleme mai mici, pana ajungem la o problema elementara care nu ne creeaza dificultati. Impartirea se face recursiv.

Sa luam ca exemplu MergeSort... un algoritm foarte dragalas de sortare a numerelor dintr-un vector... Care e ideea de baza? Pai tot impartim vectorul in jumate pana cand ajungem la 1 element.. care e sortat... dupa unim 2 jumatati de cate 1 element si le sortam, dupa unim 2 jumatati de 2 elemente etc.

Aici avem o implementare in C a algoritmului. Algoritmul standard este enuntat in carti ca incepand de la 1, noi il vom incepe aici de la 0.

Programul il puteti downloada si de aici.

#include <stdio.h>

#define MAXINT 32767;



void MERGE(int vector[],int start,int mijloc,int sfarsit)

{
int lungime1=mijloc-start;
int lungime2=sfarsit-mijloc;

int inceput_vector[lungime1+1];
int sfarsit_vector[lungime2+1];

int i,j,k;
for (i=0;i<lungime1;i++){

inceput_vector[i]=vector[start+i];
}

for (j=0;j<lungime2;j++){

sfarsit_vector[j]=vector[mijloc+j];
}

inceput_vector[lungime1]=MAXINT;
sfarsit_vector[lungime2]=MAXINT;

i=0;
j=0;
for (k=start;k<sfarsit;k++){

if(inceput_vector[i]<sfarsit_vector[j]){
vector[k]=inceput_vector[i];

i++;
}else{
vector[k]=sfarsit_vector[j];

j++;
}
}
}


void MERGEsort(int vector[],int start,int sfarsit)

{
int mijloc;
if (start<sfarsit-1) {

mijloc=(start+sfarsit)/2;
MERGEsort(vector,start,mijloc);

MERGEsort(vector,mijloc,sfarsit);
MERGE(vector,start,mijloc,sfarsit);

}
}

int main()
{
int vector[5]={2,5,1,4,3};

MERGEsort(vector,0,5);
int i;

for (i=0;i<5;i++)
printf("%i ",vector[i]);

return 0;
}

Programul asta va rula in mare parte conform imaginii urmatoare:


Deci, ideea de baza: impartim vectorul in bucati mai mici, iar apoi unim bucatile respective in ordine...

Urmeaza intrebarea: cat este complexitatea algoritmului? Pai O(n log n), mult mai bine decat bubblesort si sortarea cu 2 foruri, care au O(n^2).


Un alt algoritm foarte folosit este Binary Search-ul. Este un algoritm care cauta un element intr-un vector sortat, avand o complexitate O(log n). Cum ajunge la complexitatea asta? Pai face asa. Vede daca elementul este la mijloc. Daca nu e, atunci... daca e mai mic decat mijlocul, cauta in jumatatea inferioara, iar daca e mai mare, in jumatarea superioara.

Programul este cam asa (fisier txt) :

#include <stdio.h>

int BinarySearch(int vector[],int start,int sfarsit,int element)

{
if (start==sfarsit) return -1;//sau -start pentru a obtine pozitia pe care ar trebui sa se afle;

int mijloc = (start+sfarsit)/2;
if (vector[mijloc]==element) return mijloc;

if (vector[mijloc]<element) return BinarySearch(vector,start,mijloc,element);

if (vector[mijloc]>element) return BinarySearch(vector,mijloc+1,sfarsit,element);

}

int main()
{
int vector[5]={1,2,3,4,6};

printf("%i\n",BinarySearch(vector,0,5,3));

printf("%i\n",BinarySearch(vector,0,5,5));

return 0;
}

Evident, sunt mult mai multe aplicatii ale acestui algoritm, dar cam asta e conceptul de baza. Si tineti minte... Daca aveti mai multi amici care se cearta, intai ii separati, dupa discutati cu fiecare in parte, dupa ii readuceti la un loc si ii puneti sa discute intre ei. ;)

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.

Mic tutorial Backtracking - part 1: Blind bkt

Backtracking cred ca este unul din algoritmii mei preferati. E like the father of all algorythms. He pwns everything. Greedy? Dinamica? Le face. Mai incet, dar le face (bine, mult mai incet, are complexitatea O(2^n)). Daca mi se permite aceasta metafora, e like ai 2 tipe, una vine la tine si zice ca stie sa iti dea un blowjob rapid, si alta care vine si zice ca stie si blowjobul si toate pozitiile din Kama Sutra si le face incet dar bine, pe care ai alege? (raspuns irelevant: the one with the bigger boobs :P )

Anyways inapoi la treaba serioasa. Backtracking. Care e ideea? Ai un vector de valori posibile, sa ii zicem pos[], si o stiva st[] in care bagam toate permutarile intre o parte din elementele din pos (sau toate, dupa caz) si verificam daca solutia este corecta.

Varianta recursiva e cea mai scurta si dragalasa:

void bkt(int p)

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

{
st[p]=pos[i];
if(p==nr_cautat)
if (verif(p)) afis(p);
else bkt(p+1);

}
}

THE END. Astea sunt cele 5 randuri pt care trebuie sa intelegeti principiul.
Ca exemplu de rulare, sa zicem ca avem pos[]={1,2,3} si nr_cautat =2. Practic adauga in stiva 1, si apeleaza bkt pentru a 2a pozitie din stiva. Va baga in stiva {1, 1} si verifica daca solutia este corecta. Dupa, vom avea in stiva {1, 2} si verifica. Dupa, {1,3}. {2, 1} etc. Functia verif() depinde de problema, evident. O idee ar fi sa salvam in st[] doar indicii pentru pos[], adica st[p]=i; ca sa verificam mai usor in verif(p) daca elementele sunt distincte. Alteori, e mai eficient sa facem verificarea imediat cum adaugam un element nou, si dupa sa vedem daca am ajuns la numarul de elemente cautat.

Asta este principiul de baza. In rest, conteaza creativitatea programatorului pentru a-l optimiza. Dar, desigur, ppl like telling you how to think, asa ca avem un fel de grade de optimizare, AC1, AC2, blabla. Voi scrie intr-un post urmator cu ce se mananca fiecare.