Problema saptamanii - Minim local (Solutie)

Cosmin Negruseri
18 septembrie 2010

Aceasta problema are mai multe solutii intermediare. Ea s-ar potrivi destul de bine in un concurs sau chiar in un interviu de job. A fost rezolvata de cinci cititori.

Rezolvitori:
Andrei Dragus, Cosmin Balan, Andrei Damian, Serban Andrei Stan si Sturzu Antonio-Gabriel. Au mai fost altii: Mihai Calancea, Stefan Istrate, Marius Pungaru si Tabara Mihai dar ei au o scapare in solutie.

Solutie:
Un model mental al problemei este sa ne uitam la matrice ca la un relief cu inaltimi. Putem din fiecare celula ne uitam care e celula vecina cu inaltime minima. Daca mergem la fiecare pas in celula vecina minima, la un moment dat ne vom opri intr-un minim local. Aceasta strategie gaseste destul de repede un minim local pe un relief aleator, dar exista situatii in care algoritmul poate fi fortat sa foloseasca O(n^2) pasi. Un astfel de caz e bazat pe construirea reliefului ca o spirala sau un sarpe. Pe aceiasi idee merg algoritmii de hill climbing sau steepest descent. Ei isi gasesc aplicatii in multe domenii cum ar fi machine learning sau inteligenta artificiala.

Putem imbunatati solutia curenta prin folosirea catorva intrebari pentru a scurta lantul pe care ne deplasam. Astfel putem folosi n intrebari sa aflam valorile din n celule aleatoare. Apoi pornim din celula cu inaltimea cea mai joasa. In cazul in care relieful e un lant de lungime n^2 aceasta idee ne aduce la o distanta medie de n pozitii de capatul lantului, deci vom face cam 4n pasi.

In rezolvarea unei probleme 2d ne ajuta frecvent sa rezolvam varianta ei mai simpla unidimensionala. In cazul problemei curente pentru cazul unidimensional exista o rezolvare simpla si eficienta bazata pe o idee similara cu cautarea binara.

Astfel incercam sa facem acelasi lucru in cazul bidimensional si incercam sa eliminam jumatate din problema. Pentru asta intrebam toate valorile de pe linia din mijloc a matricei. Ne uitam la elementul minim de pe linie si la cele doua elemente vecine pe verticala cu el. Daca elementul e minim local ne oprim, daca are un vecin mai mic putem elimina jumatatea opusa vecinului. Putem face asta pentru ca exista un lant descrescator ce trece prin elementul minim al liniei si vecinul lui vertical mai mic care intra in jumatatea corespunzatoare vecinului si nu mai poate iesi din ea. Un pas ne ia n + 2 intrebari. Ca sa rezolvam problema complet trebuie sa injumatatim solutia de log n ori deci numarul total de intrebari va fi n log n + 2 log n. Putem insa la fiecare pas sa alternam injumatatirea dupa linie cu cea dupa coloana si astfel pentru a trece de la o problema de dimensiune nxn la una de n/2 x n/2 vom face n + 2 + n/2 + 2 pasi. In total aceasta solutie va folosi 3/2 (n + n/2 + ...) + 4 log n = 3n + 4 log n pasi.

Solutia asta are o mica scapare de care va spuneam la inceput. Incercati sa vedeti daca o gasiti inainte sa cititi mai departe. Daca ne uitam doar la minimul de pe coloana si minimul de pe linie e mai mic atunci s-ar putea sa alegem jumatatea gresita. Ce vrem e ca la fiecare pas toate elementele de pe margine a patratului in care continuam sa fie mai mari decat un element din interiorul lui. Daca ne uitam doar la coloana exista cazuri in care nu respectam aceasta proprietate. Solutia poate fi reparata usor: la fiecare pas alegem jumatatea in care se afla minimul elementelor cercetate pana acum.

Probleme inrudite:
Daca avem un arbore binar cu n noduri. Fiecare nod are o valoare in el. Care e numarul minim de intrebari in care puteti garanta ca gasiti un minim local?

Maxim (Lot 2005) Se da un sir circular A de n elemente distincte (n <= 1000000). Se cere sa determinati un maxim local in cel mult 25 de intrebari. O intrebare ask(i, j, k) ne spune ordinea lui A[i] fata de A[j] si ordinea lui A[j] fata de A[k].

Problema "Minim local" e din paperul "Local optimization on graphs" de Llewellyn, Donna Crystal, Tovey, Craig si Trick, Michael.