infoarena

Aici puteţi discuta despre problema Adapost 2 (http://infoarena.ro/problema/adapost2).

Am luat 80-90 de puncte cu o solutie in care incerc sa restrang intervalul de cautare pana obtin o zona suficient de mica pentru a putea aproxima rezultatul. Insa asa nu se obtine intotdeauna rezultatul optim. Ar trebui sa mai imbunatatesc un pic cautarea sau exista vreun algoritm sigur in O(N*logN) sau ceva de genul...?

Am si eu o nelamurire...dak aleg punctul ca centru de greutate suma distantelor de la centru la pctele din exemplu este mai mica decat suma distantelor de la pct ales corect si pctele din exemplu....am gresit eu la calcul sau e adevarat ce spun?  :-k

Pt. Andrei: este gasit rezultatul optim ( se numeste Simulated Annealing metoda, nici eu nu o stiam inainte ) intotdeauna ( nici eu nu prea imi explic de ce e asa pe toate cazurile posibile - nu am reusit inca sa demonstrez ). Eu am luat 100 si am lasat sa imi afiseze la a 4a zecimala, adica distanta intre care caut sa ajunga mai mica de 0.0001.



Cred k ai calculat gresit pt. ca si mie mi-a dat raspunsul din exemplu... Si vezi la ce zecimala e greseala aia, sa nu fie nesemnificativa eroarea...

Am calculat centrul de greutate pt testul din exemplu si mi-a dat punctu de coordonate 4.30(6) si 3.507...
Am folosit formula de la problema Zaharel..
Unde am gresit?

Ai gresit un singur lucru: centrul de greutate nu este raspunsul corect... De ce nu faci o functie care sa calculeze suma distantelor de la un punct la toate punctele din input, si de ce n-o testezi pe raspunsul gasit de tine si pe raspunsul din exemplu ?

Convinge-te singur. :-)

ma poate lamuri si pe mine cineva DE CE NU este centrul de greutate acel punct....multi oameni mi-au spus ca este....printre ei se numara si olimpici la mate....!!!  :eyebrow: ...as dori o demonstratie dak se poate , in caz ca nu este....ori poate are problema o chichita...poate distanta nu se masoara normal....nu mai stiu ce sa zic... :cry:  ](*,)

Mocke, ai calculat sa vezi pe exemplu cu distanta euclediana, sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))?
Nu merge sa intrebi de ce nu e corect centrul de greutate decat pentru ca e alegerea cea mai logica, aparent.
Trebuie sa demonstrezi de ce trebuie sa fie centrul de greutate si nu alt punct mai bine.

Exact. Cand vii cu o anumita ipoteza trebuie sa ne convingi tu pe noi de ce e asa... O demonstratie ca NU e centrul de greutate se poate da foarte usor printr-un singur contraexemplu.

Nu mai insista pe ideea asta, raspunsul nu este centrul de greutate nici macar pt. N = 3, in acest caz raspunsul este punctul lui Toricelli.

http://mathworld.wolfram.com/FermatPoints.html

Sunt curios... ce intelegi prin "olimpici la mate". Au trecut de faza locala ? Sau pur si simplu au participat. Din punctul multora de vedere, esti olimpic daca ai ajuns "macar" la nationala si nu ai luat 0.

Am citit cate ceva despre Simulated Annealing...dar nu am gasit decat despre problema comis-voiajorului. Poate cineva sa mi zica in cateva cuvinte care e ideea aici ?  Se pleaca de la un punct aleator...sau cum ?  :?

La prima vedere, aceasta problema te duce cu gandul la o formula matematica. Insa nu cred ca asta este ideea.
Momentan am rezolvat problema pentru 80 pct. In problema se cer coordonatele punctului cu 4 zecimale. Deci, initial xp=0, yp=0. Apoi, la fiecare pas, incerci sa muti punctul la stanga, la dreapta, sus, jos, pana obtii o solutie mai buna. Mai intai incerci sa-l muti cu o unitate, apoi cu 0.1, apoi 0.01, tot asa, pana obtii punctul exact cu 4 zecimale. Pe ultimele 2 teste iau TLE, cu toate ca in final l-am optimizat, plecand nu de la (0, 0), ci de la coordonatele centrului de greutate.

Mersi de idee ! Acuma intervine o mica problema... La implementare ai folosit criteriul Metropolis ? Adica cand muti punctul intotdeauna accepti o stare care iti micsoreaza distanta....dar exista si cazuri in care trebuie sa accepti si mariri mici ale distantei pentru ca nu cumva sa te blochezi intr-un minim local...nush..just asking... :?

 // Done ! Nu trebuie Metropolis .. 10X again

Cel mai bine pleci de la centrul de greutate pentru ca e apropiat de punctul cautat dar merge si din orice alt punct daca ai facut cum trebuie.
Ideea e sa pornesti la inceput cu un pas destul de mare (cam 100) pe care il tot injumatatesti. E un fel de cautare binara mai ciudata.
Initial imi era frica ca pot sa raman blocat intr-un minim local daca fac asa dar se pare ca nu sunt teste de genul asta.
De fapt, ma intreb daca se pot genera asemenea teste.
Oricum, rezolvarea e mai logica si am facut-o fara sa stiu de Simulated Annealing.

Vladcyb1, cum ai optimizat pentru 100 pct? Mie-mi iese din timp la ultimele 4.

edit: Gata, am rezolvat! Nu stiam ca functia "pow" mananca atata timp.  :?

vlad: Cred ca se poate demonstra cu matematica superioara ca o functie de genul asta are un minim global si nici un minim local. Poti sa iti faci un desen pentru configuratii cu puncte in care cu cat distanta e mai mica pentru un punct cu atat punctul e mai intens colorat. Pentru mai multe configuratii random de puncte am vazut aceiasi structura fara vre-un minim local diferit de cel global. Deci in principiu poti schimba punctul curent de fiecare data cand nimeresti pe un punct cu distanta mai mica, pentru ca mergi in directia buna.

Eu m-am inspirat in rezolvarea problemei Adapost2 de aici http://en.wikipedia.org/wiki/Geometric_median . E un proces iterativ de determinare a punctului cautat pe care il stopez cand distanta intre doua punte obtinute prin iteratie devine suficient de mica. A mai rezolvat cineva folosind ideea asta? Nu vreau sa fie gresit inteles dar timpii pe care ii obtin sunt foarte buni ( dupa cate am verificat eu ar fi cei mai buni ). E algoritmul asta atat de puternic sau evaluarea s-a facut pe un calculator mai puternic ?

Evaluatorul crapa pe urmatoarea sursa: http://infoarena.ro/job_detail/337699