#include <FibonacciDivision.h>
Diagram dziedziczenia dla FibonacciDivision
Metoda Fibonacciego, opublikowana w 1953 roku przez Kiefera, jest szczególnie przydatna w sytuacjach gdy liczba obliczeń, które możemy wykonać jest ograniczona (np. w systemach czasu rzeczywistego). Metoda daje najmniejszy przedział nieokreśloności przy zadanej z góry liczbie wyliczeń funkcji.
Algorytm metody:
Oznaczenia:
- lewy kraniec przedziału poszukiwań w k-tej iteracji
- prawy kraniec przedziału poszukiwań w k-tej iteracji
- pierwszy punkt wyliczany w k-tej iteracji
- drugi punkt wyliczany w k-tej iteracji
- k-ty element ciągu Fibonacciego
Dane potrzebne do obliczeń:
- minimalizowana funkcja jednej zmiennej
- lewy kraniec przedziału poszukiwań
- prawy kraniec przedziału poszukiwań
- wymagana dokładność rozwiązania
W metodzie Fibonacciego dokładność rozumiana jest jako szerokość ostatniego przdziału nieokreśloności. Wymagamy by była ona mniejsza od . Charakterystyczną cechą metody Fibonacciego jest to, że liczbę kroków optymalizacji ustalamy przed rozpoczęciem obliczeń.
musi spełniać warunek:
.
Krok 1:
Tworzymy dwa nowe punkty ( i
) leżące pomiędzy
a
i b
zgodnie ze wzorami:
W nowoutworzonych punktach wyliczamy wartość funkcji.
Krok 2:
Jeśli , to podstawiamy:
oraz obliczamy wartość funkcji w punkcie . Następnie przechodzimy do punktu 4.
Jednak gdy przechodzimy do kroku 3.
Krok 3:
Podstawiamy
i wyliczamy wartość funkcji w punkcie . Następnie przechdzimy do punktu 4.
Krok 4:
Podstawiamy . Jeśli
, to przejść do kroku 2. W przeciwnym wypadku przejść do kroku 5.
Krok 5:
Jeśli , to podstawiamy:
Jeśli natomiast , to podstawiamy:
Wynikiem działania metody jest punkt w środku odcinka .
Algotytm zaimplementowany na podstawie // TODO: tej rosyjskiej ksiażki.
Metody publiczne | |
~FibonacciDivision (void) | |
Destruktor. | |
virtual std::auto_ptr< Method > | Clone () const |
Tworzy kopię metody. | |
virtual const wxString & | Name () const |
Zwraca nazwę metody. | |
virtual MethodIdType | Id () const |
Zwraca ID metody. | |
virtual bool | CanHandle (const ProblemBase *pProblem) const |
Sprawdza, czy dany problem może być rozwiązany tą metodą. | |
Statyczne metody publiczne | |
static MethodIdType | ClassId () |
Zwraca ID metody. | |
Metody chronione | |
FibonacciDivision (void) | |
Konstruktor domyślny. | |
FibonacciDivision (const FibonacciDivision &from) | |
Konstruktor kopiujący. | |
std::vector< unsigned int > | GenerateFibonacciSequence (double a, double b, double epsilon) const |
Wygeneruj ciąg Fibonacciego. | |
virtual wxString & | rName () |
Przyjaciele | |
class | SectionLineSearchPanel< FibonacciDivision > |
|
Konstruktor kopiujący.
|
|
Wygeneruj ciąg Fibonacciego. Wygeneruj ciąg Fibonacciego wystarczająco długi by w wyniku działania metody można było otrzymać przedział nieokresloności o zadanej długości.
|