Politechnika Łódzka



Pobieranie 6.5 Mb.
Strona31/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   27   28   29   30   31   32   33   34   ...   54

Rozdział V

Algorytm szybkiego deterministycznego szukania
najbliższego sąsiada w metryce miejskiej

W rozdziale dokonano krótkiego przeglądu algorytmów z gwarantowanym dla najgorszego lub średniego przypadku subliniowym w liczności zbioru czasem szukania, a następnie zaproponowano nowy algorytm deterministycznego szukania najbliższego sąsiada w metryce miejskiej (Grabowski, 2001a, Grabowski i Baranowski, 2002). Algorytm ten cechuje się elastycznością (możliwe jest us­tawienie współczynnika kompromisu między czasem szukania a kosztem pamięciowo-czasowym wstępnej obróbki) oraz znaczną prostotą koncepcji. Ponadto przedstawiono wyniki działania implementacji algorytmu na zbiorach sztucznych oraz na zbiorze Iris. Wybór metryki miejskiej został uzasadniony korzystnymi, w stosunku np. do metryki euklidesowej, wartościami miary Cháveza–Navarro (2001) dla szeregu rozpatrywanych zbiorów naturalnych i sztucznych.



5.1. Algorytmy z subliniowym czasem szukania


Liczba metod szukania NS, dla których udowodniono, choćby tylko w przypadku średnim, subliniowość czasu szukania w liczności zbioru n, jest stosunkowo mała. Pierwszy algorytm, działający w Rd (Dobkin i Lipton, 1976), szukał NS w czasie o złożoności , jednak koszt wstępnej obróbki10 wynosił aż . Zastosowana meto­da wykorzystywała diagram Voronoi’a i obniżała rekursywnie wymiarowość problemu. Clarkson (1988) zredukował koszt wstępnego przetwarzania do (wartość oczekiwana), ale czas szukania wzrósł do . W późniejszych propozy­cjach (Yao i Yao, 1985; Agarwal i Matoušek, 1992; Matoušek, 1992) również czas szukania rośnie wykładniczo w d. W bardziej teoretycznej wersji algorytmu Clarksona (Meiser, 1993) czas szukania wygląda interesująco: , ale koszt wstępnej obróbki wynosi .

Należy podkreślić, że nie wszystkie z wymienionych algorytmów gwarantują subliniowy czas szukania w najgorszym przypadku, np. algorytmy Clarksona i Meisera są probabilistyczne. Prezentowany w niniejszej pracy algorytm jest natomiast algorytmem deterministycznym, tj. gwarantuje subliniowość także w najgorszym przypadku.




Pobieranie 6.5 Mb.

Share with your friends:
1   ...   27   28   29   30   31   32   33   34   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna