La ricerca ternaria è meno efficiente di questo algoritmo correlato?

Question

L'algoritmo ternary search è un algoritmo veloce per trovare il minimo o il massimo di un unimodal function, una funzione che sia aumenta e poi diminuisce o diminuisce e poi aumenta. Supponiamo di avere a che fare con una funzione che diminuisce, poi aumenta e che vogliamo trovare il minimo di valore. La ricerca ternaria funziona utilizzando la seguente ricorsione:

• Se la dimensione della finestra è "abbastanza piccola", è sufficiente tornare al punto centrale.
• Altrimenti:
  • Valutare la funzione ai limiti sinistro e destro; chiama i valori l e r.
  • Valutare la funzione ai punti 1/3 e 2/3; chiamare i valori m e m
  • Se m < m 2 , allora siamo nella crescente regione della funzione e il minimo non può essere compresa tra 2 m e r .
  • Se m > m 2 , allora siamo nella regione diminuzione della funzione può minimo non può essere compresa tra L e M
  • ricorsivamente 2/3 che weren' t scartato.

Questo algoritmo funziona in modo rapido, perché può continuare a tirare fuori 1/3 dei valori su ogni iterazione.

Tuttavia, mi sento come se mi mancasse qualcosa perché credo che possiamo far funzionare questo algoritmo molto più velocemente. In particolare, notiamo che stiamo sempre proiettando uno dei terzi dell'intervallo tra un confine e uno dei punti sonda. Ciò significa che manteniamo la regione tra il punto di tastatura e l'altro limite. Poiché la ricerca ternaria seleziona i punti sonda a 1/3 punti, ciò significa che conserviamo 2/3 dei valori in ogni punto. E se invece di sondare i punti 1/3 e 2/3, abbiamo sondato il 1/2 - & epsilon; e 1/2 + & epsilon; punti per un estremamente piccolo & epsilon ;? Ciò significherebbe che dovremmo buttare fuori 1/2 - & epsilon; dell'intervallo su ogni passo, il che significa che la dimensione dell'intervallo diminuirà molto più rapidamente rispetto a quando avessimo appena lanciato un terzo degli elementi ogni volta.

Ad esempio, se prendo & epsilon; = 1/1000, otteniamo il lancio di 999/2000 dell'intervallo da cercare su ogni iterazione. La frazione rimanente dopo un certo numero di iterazioni qui viene mostrato (ricerca ternario si trova sulla sinistra, il mio algoritmo si trova sulla destra :)

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 

È questa versione modificata dell'algoritmo solo "migliore" rispetto alla versione originale? O c'è qualcosa che mi manca qui significherebbe che non dovrei usare la strategia modificata per scegliere i punti sonda?

Answer 1

Questa versione convergerà sicuramente più velocemente, ma potrebbe essere più incline a problemi di precisione in virgola mobile. Ad esempio, cosa succede se ottieni m + eps = m? Questa è una possibilità reale se m è grande, ad esempio. Quindi c'è un compromesso tra accuratezza e velocità di convergenza.Il miglior algoritmo di questa classe è probabilmente Golden Section Search, che è sia veloce che preciso.

Answer 2

Se una funzione è unimodale, g (y) = F (y + ε) - F (y) incrocia zero solo una volta, aumentando y dal limite sinistro a quello destro.

Fondamentalmente, ciò che si propone nel secondo algoritmo migliorato è una ricerca binaria per lo zero-crossing (radice) di g (y). Supponiamo che stai facendo la minimizzazione, quindi F (y) ha un minimo singolo. Quindi G (y) è negativo per un po ', quindi positivo. Quindi, se g (x) < 0, la radice è più grande di x (o più precisa: x + ε), e se g (x)> 0, la radice è più piccola di x.

Questo è più veloce (caso peggiore) dell'algoritmo primo/originale, poiché la regione in cui si trova il minimo è dimezzata a ogni passaggio, invece di moltiplicata per 2/3.