Politechnika Łódzka



Pobieranie 6.5 Mb.
Strona36/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   32   33   34   35   36   37   38   39   ...   54


dla dowolnych punktów A, B, C

. (5.1)

Idea algorytmu została ukazana na Rys. 5.1 (przykład 2-wymiarowy). Jak zostało powiedziane, jedna z próbek NN(v1), ..., NN(v4) musi być najbliższym sąsiadem q, gdyż wynika to z faktu, że zacienione pasy z definicji algorytmu nie mogą zawierać żadnej próbki z P.


Wracamy teraz do oryginalnego algorytmu. Jest oczywiste, że „globalnie” naj­bliższy sąsiad dla danego wierzchołka nie musi należeć do „ćwiartki” opisanej w alternatywnej wersji algorytmu. Przykładowo na Rys. 5.2 najbliższym sąsiadem dla v1 jest NN(v2), który leży bliżej niż jego najbliższy sąsiad „z ćwiartki”, NN(v1). Łatwo jednak zauważyć, że jeśli NN(v2) jest najbliższym sąsiadem dla v1, to w metryce miejskiej musi być także globalnie najbliższym sąsiadem dla v2. W obu przedstawio­nych wersjach algorytmu listy sąsiadów związane z daną komórką w obu wersjach algorytmu bedą zawierały najbliższego sąsiada dla danej próbki z tej komórki.

Rys. 5.2. Przykład sytuacji, w której najbliższy sąsiad pewnego wierzchołka (v1)


należy do innej „ćwiartki” przestrzeni niż dany wierzchołek.

NN(v2) jest bliższym sąsiadem v1 niż NN(v1).


Co więcej, jeśli , to


. (5.2)

Wnioskiem z przykładu i wzoru (5.2) jest więc stwierdzenie, iż obie wersje algorytmu zwracają na wyjściu najbliższego sąsiada danej próbki. Algorytmy nie są jednak równoważne, jeśli chodzi o koszt przetwarzania wstępnego. Wbrew może pierwszemu wyobrażeniu, znalezienie NS tylko dla konkretnej „ćwiartki” przestrzeni nie jest (w najgorszym przypadku) szybsze niż znalezienie NS w całym zbiorze P (nie wydaje się możliwe takie zindeksowanie zbioru P, aby znalezienie NS było deterministycznie subliniowe w n dla dowolnego d). Wadą wersji alternatywnej (tj. z najbliższymi sąsiadami szukanymi dla „ćwiartek”) jest natomiast związanie z każdym wierzchołkiem aż sąsiadów — w oryginalnej wersji z jednym wierzchołkiem skoja­rzony jest jeden sąsiad. Konkluzja jest oczywista: lepsza jest wersja pierwsza (wersja alternatywna została przedstawiona tylko dlatego, że idea metody jest w niej lepiej widoczna).

Z definicji algorytmu (wersja oryginalna) wynika, że czas szukania wynosi , zaś przetwarzanie wstępne trwa i wymaga pamięci.

Pobieranie 6.5 Mb.

Share with your friends:
1   ...   32   33   34   35   36   37   38   39   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna