Środowisko uruchomieniowe optymalnego algorytmu chciwości

16

$|P| = n$ $k$ $k$ $n$ $C = \{ c_1,c_2,\ldots,c_k\}$ $k$ $\text{cost}(C) = \max_i \min_j D(p_i, c_j)$ $D$ oznacza odległość euklidesową między punktem wejściowym a punktem środkowym . Każdy punkt przypisuje się do najbliższego centrum gromady grupującego wierzchołki w różnych skupisk. $p_i$ $c_j$ $k$

Problem znany jest jako (dyskretny) problem klastrowania i jest to -hard. Można to pokazać z redukcją problemu kompletnego dominującego problemu, że jeśli istnieje algorytm aproksymacji dla problemu z to . $k$ $\text{NP}$ $\text{NP}$ $\rho$ $\rho < 2$ $\text{P} = \text{NP}$

Optymalny algorytm aproksymacji jest bardzo prosty i intuicyjny. Najpierw wybiera arbitralnie punkt i umieszcza go w zbiorze centrów skupień. Następnie wybiera się kolejne centrum klastrów, które jest możliwie jak najdalej od wszystkich pozostałych centrów klastrów. Więc póki , my wielokrotnie znaleźć punkt , dla których odległość jest zmaksymalizowane i dodać go do . Raz skończone. $2$ $p \in P$ $C$ $|C| < k$ $j \in P$ $D(j,C)$ $C$ $|C| = k$

Nietrudno zauważyć, że optymalny algorytm zachłanny działa w czasie $O(nk)$ . Rodzi to pytanie: czy możemy osiągnąć czas $o(nk)$ ? O ile lepiej możemy zrobić?

algorithms computational-geometry

— Juho
źródło

7

Problem można rzeczywiście rozpatrywać geometrycznie w taki sposób, że chcielibyśmy objąć punkty kulkami, w których promień największej kuli jest zminimalizowany. $V$ $k$

$O(nk)$ jest rzeczywiście dość proste do osiągnięcia, ale można zrobić lepiej. Feder i Greene, Optymalne algorytmy przybliżonego grupowania, 1988 osiągają czas działania przy użyciu bardziej sprytnych struktur danych i dalej pokazują, że jest to optymalne w algebraicznym modelu drzewa decyzyjnego. $\Theta(n \log k)$

— Juho
źródło

1

Moje pytanie: Czy istnieje sposób, aby uruchomić chciwą strategię kompletacji w czasie ? $o(|V|^2)$

Wydaje mi się, że to opisałeś. W przypadku, gdy przeczytałem zbyt daleko w twoim opisie, oto co zrozumiałem. Posiada strukturę danych asocjacyjny przypisujące każdy element przy czym suma odległości od elementów . Ta struktura danych może być inicjowana kosztem z odległością do a ta inicjalizacja może wytworzyć następny element jako efekt uboczny bez zwiększania złożoności. Można go zaktualizować po wybraniu nowego elementu kosztem , ponownie wytwarzając kolejny element jako efekt uboczny. Powtórz, aby uzyskać $V$ $S$ $O(|V|)$ $p$ $O(|V|)$ $S$ . Wynikająca z tego złożoność to . $O(k |V|)$

— AProgrammer
źródło

1

Ale zwróć uwagę na ograniczenie

: w najgorszym przypadku może być tak duże jak

. Podejrzewam, że istnieją struktury danych, które osiągają jeszcze lepsze granice, ale tak naprawdę nie wiem.

k

$k$

| V |

$|V|$

— Juho

Ups,

a nie

w twoim pytaniu. (Zauważ, że w swoim pytaniu wróciłeś do

, więc powinno to być ulepszenie). To, co proponuję, nie wykorzystuje faktu, że pracujesz w przestrzeni euklidesowej, myślę, że będziesz musiał go użyć, aby zrobić lepiej, ale obecnie nie wiem, jak to zrobić.

o

$o$

O

$O$

k^{3}

$k^3$

— AProgrammer