•domino
|
|
« : Martie 02, 2006, 01:19:25 » |
|
Aici puteţi discuta despre problema Adapost 2.
|
|
|
Memorat
|
|
|
|
andreit1
Vizitator
|
|
« Răspunde #1 : Martie 08, 2006, 23:47:09 » |
|
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...?
|
|
|
Memorat
|
|
|
|
•mocke
Strain
Karma: 0
Deconectat
Mesaje: 19
|
|
« Răspunde #2 : Martie 09, 2006, 00:37:19 » |
|
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?
|
|
|
Memorat
|
oricine greseste...nu oricine invatza
|
|
|
•filipb
|
|
« Răspunde #3 : Martie 09, 2006, 15:53:38 » |
|
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. 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? 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...
|
|
|
Memorat
|
|
|
|
•realboss
Strain
Karma: -1
Deconectat
Mesaje: 5
|
|
« Răspunde #4 : Martie 10, 2006, 13:52:27 » |
|
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?
|
|
|
Memorat
|
Totul sau nimic!
|
|
|
•greco
|
|
« Răspunde #5 : Martie 10, 2006, 14:10:46 » |
|
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.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•mocke
Strain
Karma: 0
Deconectat
Mesaje: 19
|
|
« Răspunde #6 : Martie 10, 2006, 23:01:43 » |
|
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....!!! ...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:
|
|
|
Memorat
|
oricine greseste...nu oricine invatza
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #7 : Martie 10, 2006, 23:23:04 » |
|
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.
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #8 : Martie 11, 2006, 09:04:39 » |
|
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.htmlSunt 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.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•vladcyb1
|
|
« Răspunde #9 : Martie 11, 2006, 11:05:42 » |
|
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 ?
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
ag3nt_junior
Vizitator
|
|
« Răspunde #10 : Martie 11, 2006, 12:34:08 » |
|
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.
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #11 : Martie 11, 2006, 13:16:34 » |
|
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
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #12 : Martie 11, 2006, 13:19:28 » |
|
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.
|
|
|
Memorat
|
|
|
|
ag3nt_junior
Vizitator
|
|
« Răspunde #13 : Martie 11, 2006, 13:52:10 » |
|
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.
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #14 : Martie 11, 2006, 14:39:05 » |
|
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.
|
|
|
Memorat
|
|
|
|
•anna_bozianu
|
|
« Răspunde #15 : Decembrie 03, 2008, 22:48:22 » |
|
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 ?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #16 : Noiembrie 26, 2010, 15:37:17 » |
|
Evaluatorul crapa pe urmatoarea sursa: http://infoarena.ro/job_detail/337699
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|