Gdzie mogę znaleźć seryjną implementację C/C++ algorytmu k-najbliższego sąsiada?
Czy znasz bibliotekę, która to ma?
Znalazłem openCV, ale implementacja jest już równoległa.
Chcę rozpocząć od seryjnej implementacji i zrównoleglować ją z pptreads openMP i MPI.
K-najbliższa sąsiad implementacja C/C++
Dzięki
Alex
A co z ANN? http://www.cs.umd.edu/~mount/ANN/. Kiedyś użyłem implementacji kdtree, ale są inne opcje.
Cytowanie ze strony internetowej: "ANN to biblioteka napisana w języku C++, która obsługuje struktury danych i algorytmy dla dokładnego i przybliżonego najbliższego sąsiada w dowolnie wysokich wymiarach."
Dzięki, ANN jest dobrym punktem wyjścia. – alexsardan
Najprostszym sposobem realizacji tego celu jest pętli wszystkich elementów i zapisz K najbliższego. (tylko porównanie). Złożoność tego jest O(n), która nie jest tak dobra, ale nie jest konieczne wstępne przetwarzanie. Teraz tak naprawdę zależy od twojej aplikacji. Powinieneś użyć jakiegoś indeksu przestrzennego do obszaru podziału, w którym szukasz knn. W przypadku niektórych aplikacji struktura przestrzenna oparta na siatce jest w porządku (wystarczy podzielić swój świat na stały blok i przeszukać tylko w bloki zamykające). Jest to dobre, gdy twoje jednostki są równomiernie rozmieszczone. Lepszym rozwiązaniem jest użycie jakąś strukturę hierarchiczną, kd-drzewa ... To naprawdę wszystko zależy od tego, co trzeba
uzyskać więcej informacji, w tym pseudokod wygląd w tych prezentacjach:
Dzięki za odpowiedź. Właściwie muszę zacząć od już wdrożonej wersji. – alexsardan
Napisałem C++ implementation for a KD-tree z wyszukiwaniem najbliższego sąsiada. Możesz łatwo rozszerzyć go dla najbliższych sąsiadów K przez dodanie kolejki priorytetowej.
Aktualizacja: Dodałem wsparcie dla k najbliższego sąsiada w poszukiwaniu wymiarach N
Dzięki, ale nie widać informacji o licencji. –
Na jakie problemy zamiar zastosować ten algorytm? KNN jest naprawdę prosty i możesz spróbować wdrożyć własne podejście. –