Czy wyszukiwanie trójskładnikowe jest mniej wydajne niż ten powiązany algorytm?

Question

Algorytm ternary search jest szybki Algorytm znalezienia minimum lub maksimum na unimodal function, funkcję, która albo zwiększa, a następnie zmniejsza się lub maleje, a następnie rośnie. Załóżmy, że mamy do czynienia z funkcją, która zmniejsza się, a następnie zwiększa, i że chcemy znaleźć minimalną wartość. Wyszukiwanie trójstronne działa z użyciem następującej rekurencji:

• Jeśli rozmiar okna jest "wystarczająco mały", po prostu zwróć jego punkt środkowy.
• W przeciwnym razie:
  • Ocenić funkcję w granicach lewo i prawo; wywołaj wartości l i r.
  • Oceń funkcję w punktach 1/3 i 2/3; nazywamy wartości m a m
  • jeśli m < m , to jest w kolejności rosnącej obszarze funkcji a maksymalna nie może wynosić m ir .
  • jeśli m > m , to jest w obszarze malejącej funkcji może minimalna nie może być między L i M
  • rekurencyjnie przeszukiwać 2/3 że weren” t odrzucono.

Algorytm ten działa szybko, ponieważ może zachować rzucając się 1/3 wartości w każdej iteracji.

Jednak czuję, że czegoś brakuje, ponieważ uważam, że możemy sprawić, by ten algorytm działał znacznie szybciej. W szczególności zauważ, że zawsze wyrzucamy jedną trzecią zakresu między granicą a jednym z punktów pomiarowych. Oznacza to, że zachowujemy region pomiędzy punktem sondy a drugą granicą. Ponieważ wyszukiwanie potrójne wybiera punkty pomiarowe w 1/3 punktów, oznacza to, że zatrzymujemy 2/3 wartości w każdym punkcie. Co jeśli zamiast sondowania w punktach 1/3 i 2/3, sondowaliśmy na 1/2 - i epsilon; i 1/2 + i epsilon; punktów za bardzo mały i epsilon ;? Oznaczałoby to, że wyrzucilibyśmy 1/2 - i epsilon; zakresu na każdym kroku, co oznacza, że ​​rozmiar zakresu spadłby znacznie szybciej, niż gdybyśmy za każdym razem rzucali 1/3 elementów.

Jako przykład, jeśli wybiorę & epsilon; = 1/1000, możemy rzucić 999/2000 zakresu, aby wyszukać w każdej iteracji. Frakcja pozostała po pewnej liczbie iteracji jest pokazany tutaj (trójskładnikowych wyszukiwania jest po lewej stronie, mój algorytm jest po prawej stronie :)

1 :    1.0 >=    1.0 
2 :  0.666666666667 >=    0.5005 
3 :  0.444444444444 >=   0.25050025 
4 :  0.296296296296 >=  0.125375375125 
5 :  0.197530864198 >= 0.0627503752501 
6 :  0.131687242798 >= 0.0314065628127 
7 : 0.0877914951989 >= 0.0157189846877 
8 : 0.0585276634659 >= 0.00786735183621 
9 : 0.0390184423106 >= 0.00393760959402 
10 : 0.0260122948737 >= 0.00197077360181 
11 : 0.0173415299158 >= 0.000986372187705 
12 : 0.0115610199439 >= 0.000493679279947 
13 : 0.00770734662926 >= 0.000247086479613 
14 : 0.00513823108617 >= 0.00
15 : 0.00342548739078 >= 6.18952249147e-05 
16 : 0.00228365826052 >= 3.09785600698e-05 
17 : 0.00152243884035 >= 1.55047693149e-05 
18 : 0.00101495922690 >= 7.76013704213e-06 
19 : 0.000676639484599 >= 3.88394858959e-06 

Jest to zmodyfikowana wersja algorytmu tylko „lepsze” niż w wersji oryginalnej? Czy jest tu coś czego mi brakowało, co oznaczałoby, że nie powinienem używać zmodyfikowanej strategii do wybierania punktów sondujących?

Answer 1

Ta wersja będzie zbiegać się szybciej, ale może być bardziej podatna na problemy z precyzją zmiennoprzecinkową. Na przykład, jeśli otrzymasz m + eps = m? Jest to realna możliwość, jeśli m jest duże, powiedzmy. Tak więc istnieje kompromis między dokładnością a stopą zbieżności.Najlepszym algorytmem tej klasy jest prawdopodobnie Golden Section Search, który jest zarówno szybki, jak i dokładny.

Answer 2

Jeśli funkcja jest unimodalna, to g (y) = F (y + ε) - F (y) przecina zero tylko raz, zwiększając y od lewej do prawej granicy.

Zasadniczo, w drugim/ulepszonym algorytmie proponuje się wyszukiwanie binarne dla przejścia przez zero (root) g (y). Załóżmy, że robisz minimalizację, więc F (y) ma jedno minimum. Następnie G (y) jest ujemny przez jakiś czas, a następnie dodatni. Zatem jeśli g (x) < 0, to korzeń jest większy niż x (lub dokładniej: x + ε), a jeśli g (x)> 0, to korzeń jest mniejszy niż x.

Jest to szybszy (najgorszy przypadek) niż pierwszy/oryginalny algorytm, ponieważ region, w którym znajduje się minimum, jest o połowę zmniejszony o każdy krok, zamiast pomnożyć przez 2/3.