Vstupom je n vektorov x1,...,xn v m-rozmernom Euklidovskom priestore. Cieľom je zistiť Euklidovskú vzdialenosť dvoch najbližších bodov, t.j. vypočítať hodnotu
Otázkou je, či je možné skonštruovať asymptoticky rýchlejší algoritmus, než výpočet vzdialeností medzi všetkými n(n-1)/2 dvojicami rôznych bodov.
Poznámka: Sám neviem na tento problém odpovedať v plnej všeobecnosti (vlastne len pre m=1), takže neviem ani odhadnúť, aký je vo všeobecnosti náročný. Naviac, som si takmer istý, že tomuto jednoducho formulovanému problému sa už ľudia venovali, takže vyriešený už asi je. To nám však nebráni, aby sme sa nad ním zamysleli.
19 komentárov:
Pokiaľ si dobre spomínam, tak sme brali nejaký rýchly algoritmus na nájdenie minimálneho prvku množiny zrovnateľných prvkov, kde jediná povolená operácia je porovnanie dvoch prvkov. Ak chceš, môžem sa ti na to pozrieť.
Tak som sa na to pozrel. Existuje lineárny algoritmus vzhľadom k počtu prvkov postupnosti, a navyše dokáže zistiť v lineárnom čase i-ty (teda nie len najmenší) prvok postupnosti. Btw, Qsort a ostatné sorty pracujú s n.log(n), takže by nemal byť problém urobiť algoritmus minimálne s touto zložitosťou.
Tak sa ospravedlňujem, doplietol som to... Ide o to, že množina, z ktorej tu fakticky vychádzame, má veľkosť n(n-1)/2, čiže by som si to musel ešte premyslieť. Také jednoduché to zasa nie je, ako som si myslel.
v 1D existuje linearny algoritmus: najdeme minimum, maximum a interval medzi nimi rozdelime na n casti (rovnako velkych podintervalov) a pre kazdy si zistime minimum a maximum; potom uz staci prejst po vsetkych castiach a pozerat minima maxima a ratat vzdialenosti...
v 2D existuje divide&conquer algoritmus beziaci v O(nlog n)
do vyssich dimenzii moje vedomosti velmi nesiahaju
kuko: Rozmýšľal som nad tým 1D algoritmom; vyzerá to byť veľmi zaujímavý trik, ale, bohužiaľ, nepochopil som ho. Nemohol by si ho opísať trochu presnejšie, alebo dať nejaký link? (Prípadne mi ho môže vysvetliť aj niekto iný, kto to pochopil :-)
Ja sám neviem skonštruovať v 1D na daný problém O(n) algoritmus, ale O(nlog(n)) je veľmi jednoduchý: stačí tie čísla usporiadať napríklad heapsortom, ktorý je O(nlog(n)) a potom už len porovnávať susedné prvky, čo je len O(n).
mmmm... ok, popleta... to co som popisal funguje pre hladanie maximalnej vzdialenosti... pre minimalnu nepoznam nic rychlejsie ako O(nlog n)
btw co sa tyka maximalnej vzdialenosti v 2d, to ide tiez v O(nlog n) -spravime konvexny obal a tocime sa po obvode...
K tomu 1D algoritmu:
ja ho poznam pre najdenie najvacsej vzdialenosti dvoch susednych bodov, neviem ako ho zmenit pre najmensiu vzdialenost, ale pre inspiraciu ta najvacsia je takto:
Ked viem ze medzi najlavejsim a najpravejsim bodom je vzdialenost x, tak rozdelenim na n intervalov dostanem kazdy interval velkosti x/n. A staci si potom uz len uvedomit ze najmensia najvacsia vzdialenost bude vacsia ako x/n, cize taky par bodov bude v roznych intervaloch .. a tak mi uz staci vzdy porovnat maximum predosleho itnervalu z minimum svojho intervalu.
Ta dynamika pre najmensiu a pre 2D je na:
http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html
A pre zaujimavost, ako najst najvzdialenejsie dva body v manhatanovskej metrike? To bolo davnejsie na TopCoderovi ako najtazsia uloha: http://www.topcoder.com/stat?c=problem_statement&pm=6149&rd=9999&rm=249700&cr=13396848
presnejsie: v 1d islo o problem najst maximalne vzdialene 2 susedne body... slubujem ze si rozmyslim kym daco napisem
nakoniec, nasiel som riesenie v O(nlog n):
www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
co je optimalne; prijemne citanie...
demiurge, kuko, rasto: Vyborne; tym sa to vsetko uz vyjasnilo. Nakoniec sa ukazalo, ze je to naozaj algoritmicky celkom zaujimavy problem.
Ja len dodam, ze s takouto ulohou sa da stretnut (z oblasti toho, comu sa trochu venujem) napriklad pri testovani generatorov nahodnych cisiel, alebo pri konstrukcii dendrogramu v hierarchickej analyze zhlukov.
Inak k tym popleteniam: Kazdy sa obcas dopletie, alebo pomyli; v tom sa ludia nelisia. Lisia sa vsak v tom, ci si to dokazu priznat, alebo nie.
Naviac, chyb sa neda vyvarovat, ak chce clovek prist na nieco nove. Je lepsie riskovat chybu ako nepovedat nic. Napada ma nasledovny citat od Einsteina: “Anyone who has never made a mistake has never tried anything new.”
Len samozrejme ide o to, aby sa človek nemýlil príliš veľa, lebo potom zamestnáva ostatných "výsledkami", ktoré nie sú správne. Ja som to písal z práce a fakt som nad tým nerozmýšľal. Nabudúce si nájdem aspoň 15 minút času. Za túto dobu sa človeku všeličo vyjasní.
U väčšiny týchto geometrických vecí funguje tzv. "curse of dimensionality" -- síce sa dajú nájsť algoritmy, ktorých asymptotická zložitosť je dobrá (ak sa dívame na dimenziu ako na konštantu), no v praxi majú pre veľkú dimenziu tie algoritmy taký veľký overhead, že je praktickejšie použiť naivný algoritmus, ktorý prezrie všetky možnosti.
Neviem presne, ako je to v tomto konkrétnom prípade, ten algoritmus, na ktorý dal kuko linku ešte vyzerá celkom nádejne...
Problém najbližšieho páru sa dá optimálne v 2D riešiť aj pomocou Voronoiovho diagramu. Najbližší pár generuje hranu v tomto diagrame a je ich lineárne veľa (lebo je rovinný). Na zostrojenie diagramu treba O(n log n) operácií.
pavel: Myslím, že v 2D funguje aj tento postup: Stačí nájsť Delaunayovu trianguláciu, na čo existuje O(nlog(n)) algoritmus a tá myslím musí obsahovať spojnicu dvoch najbližších bodov. Mám ale tušenie, že ten Tvoj návrh a tento môj sú veľmi príbuzné.
Hej. Delaunayova triangulacia je ako rovinný graf duálom ku Voronoiovmu diagramu. Pričom duálnu transformáciu vieme zabezpečiť v čase O(n), takže nič nestratíme ani nezískame.
pavel, misof: zdá sa, že tento problém je dosť bohatý a keď sa k tomu pridajú príbuzné témy ako Voronoiove diagramy a Delaunayova triangulácia, tak by z toho mohla byť vhodná téma na bakalársku prácu. Alebo, ako hlavnú tému by ste mohli vypísať buď Delaunayovu trianguláciu, alebo Voronoiove diagramy a toto tu by bola jedna z aplikácií.
A čo takto nasledovný problém:
Notácia:
x, d sú vektory v R^n.
(d,x) = d_1*x_1+...+d_n*x_n
Úloha:
Spomedzi všetkých bodov x takých že (d,x) = 1, nájdi ten ktorý minimalizuje hodnotu max_i |x_i|.
Inak: Nájdi bod x v nadrovine danej rovnicou (d,x) = 1 s najmenšou L_infty normou.
Peter: Ja by som použil klasický LP algoritmus (metoda VuŽaVeS). Ale ako Ťa poznám, Ty máš na to určite premyslenú nejakú oveľa efektívnejšiu metódu :)
Cez LP by to šlo, ale je to tak trošku overkill :-)
Som zvedavý na rôzne zaujímavé riešenia/prístupy. Tak mi napadlo že by som tento problémik mohol šupnúť na svoju stránku.... Trošku popracujem... a šúps... už sa aj stalo! Je to tu: http://predbarakom.wordpress.com
Čakám na zaujímavé postrehy!
PS: Rado, ako lákadlo Ti prezradím že tento problém má skryte niečo spoločné so štatistikou :-)
Peter: Už to riešenie tuším. Napíšem koment k Tvojmu postu na wordpresse.
Zverejnenie komentára