/ / Szybki sposób obliczania minimalnej odległości dwóch zestawów wektorów k-wymiarowych - algorytm, geometria obliczeniowa

Szybki sposób obliczania minimalnej odległości dwóch zestawów wektorów k-wymiarowych - algorytm, geometria obliczeniowa

I dwa zestawy wektorów k-wymiarowych, gdzie k jestokoło 500, a liczba wektorów jest zwykle mniejsza. Chcę obliczyć (dowolnie zdefiniowaną) minimalną odległość między dwoma zestawami. Naiwne podejście byłoby takie:

(loop for a in set1
for b in set2
minimizing (distance a b))

Wymaga to jednak obliczeń O (n² * distance). Czy istnieje szybszy sposób robienia tego?

Odpowiedzi:

1 dla odpowiedzi № 1

Nie sądzę, że możesz zrobić lepiej niż O (n ^ 2) kiedyodległość jest dowolna (musisz zbadać każdą z możliwych odległości!). Dla danej funkcji odległości możemy być w stanie wykorzystać właściwości funkcji, ale nie będzie żadnego generał algorytm, który działa z każdą funkcją odległości większą niż O (n ^ 2) (tj. o (n ^ 2): zanotuj smallOh).

Jeśli twoje dane są dynamiczne i musisz je zachowaćotrzymując najbliższą parę punktów w różnym czasie, dla arbitralnej funkcji odległości, prawdopodobnie pomocne będą następujące prace Eppsteina (które mają specjalne operacje aktualizacji w celu szybkiego znalezienia najbliższej pary punktów):

Będziesz w stanie dostosować powyższe algorytmy zestawu do algorytmu z dwoma zestawami (na przykład, definiując odległość między punktami tego samego zestawu jako nieskończoność).

Dla odległości typu Euklidesa (L ^ p) znane są algorytmy czasu O (nlogn), które działają z danym zbiorem punktów (tzn. Nie trzeba mieć żadnych specjalnych algorytmów aktualizacji):

Oczywiście L ^ p jest dla jednego zestawu, ale możesz go dostosować do dwóch zestawów.

Jeśli podasz swoją funkcję odległości, to moc łatwiej nam pomóc.

Mam nadzieję, że to pomoże. Powodzenia!


0 dla odpowiedzi nr 2

Jeśli składnikami twoich wektorów są skalary Izgaduje, że w przypadku umiarkowanego k = 500 podejście O (n²) jest prawdopodobnie tak szybkie, jak tylko możesz. Możesz uprościć obliczenia, minimalizując odległość². Odległość (A_i, B_i) = odległość (B_i, A_i), więc upewnij się, że porównasz je tylko raz (masz tylko 500! / (500-2)! Par, a nie 500²).

Jeśli komponenty są zamiast tego wektorami M-wymiarowymi A i B, można przechowywać komponenty wektora A w a R-drzewo lub kd-tree a następnie znajdź najbliższą parę, wykonując iteracjęwszystkie składniki wektora B i znalezienie jego najbliższego partnera od A --- to byłoby O (n). Nie zapominaj, że big-O jest dla n-> nieskończoności, więc drzewa mogą pochodzić z dość kosztownego, stałego terminu (to jest to podejście może mieć sens tylko dla dużych k lub jeśli wektor A jest zawsze taki sam).


0 dla odpowiedzi № 3

Umieść dwa zestawy współrzędnych w a Spatial Index, np. za Drzewo KD.

Następnie obliczyć punkt przecięcia tych dwóch wskaźników.