Witam,
Poszukuje jakiegoś algorytmu który znajdzie mi najbliższego sąsiada
do zadanego punktu.
przyjmijmy, że punkt jest w dowolnie skończonej wymiarowej
przestrzeni z miarą Euklidesową.
mam zbiór punktów które muszę poparować w pary tak by dal wybranego
punktu p znaleźć najbliższego sąsiada.

Na razie mam tak, że dla zadanego punktu p obliczam odległości od
niego do pozostałych punktów i wybieram najmniejszy. jednak się to długo
liczy.
Czy są jakieś szybsze algorytmy tego typu? gdzie można znaleźć ich opis?

B.

do góry

B wrote:
> Witam,
> Poszukuje jakiegoś algorytmu który znajdzie mi najbliższego sąsiada do
> zadanego punktu.
> przyjmijmy, że punkt jest w dowolnie skończonej wymiarowej przestrzeni
> z miarą Euklidesową.
> mam zbiór punktów które muszę poparować w pary tak by dal wybranego
> punktu p znaleźć najbliższego sąsiada.
>
> Na razie mam tak, że dla zadanego punktu p obliczam odległości od niego
> do pozostałych punktów i wybieram najmniejszy. jednak się to długo liczy.
> Czy są jakieś szybsze algorytmy tego typu? gdzie można znaleźć ich opis?

Szukaj o problemie NNS albo kNN

Np. http://en.wikipedia.org/wiki/Kd-tree

Więcej http://www.sswiki.tierra-aoi.net/index.php?title=Mai
n_Page
--
Mateusz Ludwin mateuszl [at] gmail [dot] com

do góry

On 13 Maj, 14:45, B <B...@...pl> wrote:
> Witam,
>    Poszukuje jakiegoś algorytmu który znajdzie mi najbliższego sąsiada
> do zadanego punktu.
>    przyjmijmy, że punkt jest w dowolnie skończonej wymiarowej
> przestrzeni z miarą Euklidesową.
>    mam zbiór punktów które muszę poparować w pary tak by dal wybranego
> punktu p znaleźć najbliższego sąsiada.o dla
Jeden punkt może należeć tylko do jednej pary, czy do wielu? Mając
np.: 1 5 6 7 10; szóstka jest najbliższym sąsiadem zarówno dla 5 i 7.

>   Na razie mam tak, że dla zadanego punktu p obliczam odległości od
> niego do pozostałych punktów i wybieram najmniejszy. jednak się to długo
> liczy.
>   Czy są jakieś szybsze algorytmy tego typu? gdzie można znaleźć ich opis?
Nie wiem czemu ma służyć ten algorytm. Może warto znaleźć "wszystkie"
długości,
następnie posortować je od najkrótszych i zachłannie wybierać od
najkrótszych.
Jeśli jest dokładnie tak jak piszesz, czyli dla każdego punktu znaleźć
najbliższy
sąsiedni punkt, to od około kilkunastu tysięcy punktów z KD-Tree
powinno
być szybciej. Jeśli punktów jest mało, to z KD-Tree będzie wolniej.

Pozdrawiam

do góry

Dnia 13-05-2010 o 14:45:38 B <...@...pl> napisał(a):

> Witam,
> Poszukuje jakiegoś algorytmu który znajdzie mi najbliższego sąsiada
> do zadanego punktu.
> przyjmijmy, że punkt jest w dowolnie skończonej wymiarowej
> przestrzeni z miarą Euklidesową.
> mam zbiór punktów które muszę poparować w pary tak by dal wybranego
> punktu p znaleźć najbliższego sąsiada.
>
> Na razie mam tak, że dla zadanego punktu p obliczam odległości od
> niego do pozostałych punktów i wybieram najmniejszy. jednak się to długo
> liczy.
> Czy są jakieś szybsze algorytmy tego typu? gdzie można znaleźć ich
> opis?

Myślę, że mogą tu pomóc diagramy Voronoi.

> B.

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

W dniu 13.05.2010 14:45, B pisze:
[...]
Dziękuję wszystkim za podpowiedzi.
B.

do góry