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:
http://www.ulozto.net/xCTidts/dpg06-pdf
http://www.ulozto.net/xoh6TSD/dpg07-pdf
Na jakie problemy zamiar zastosować ten algorytm? KNN jest naprawdę prosty i możesz spróbować wdrożyć własne podejście. –