Strona główna » Algorytmy » Artykuły » Wyszukiwanie Trójkowe
 

Wyszukiwanie Trójkowe

O algorytmie

Wyszukiwanie Trójkowe to metoda, która znajduje maksimum (lub minimum) funkcji unimodalnej na pewnym przedziale [a, b]. Algorytm ten jest przykładem algorytmu "dziel i zwyciężaj". Jego zasada działania opiera się na pewnych prawdach matematycznych.

Wyszukiwanie maksimum

Szukając maksimum funkcji na przedziale [a, b] wiadomo, że istnieje taki x, że f(a) ≤ f(x) ≤ f(b). Przydatny jest też fakt, że maksimum na pewno nie leży w pierwsze trzeciej części podanego przedziału, ani w ostatniej trzeciej części. Weźmy dowolne dwa punkty p1 oraz p2, które będą leżały na przedziale [a, b] oraz p1 < p2. Istnieją wtedy dokładnie trzy możliwości:

Punkty p1 oraz p2 mogą być dowolne, ale optymalnie jest wybrać je tak, żeby równały się p1 = a + (b - a)/3 oraz p2 = b - (b - a)/3. Jest to związane z faktem, że przedział [a, b] dzielimy na trzy części, a wybrane punkty wskazują na punkty podziału przedziału.

Przykład

Wykres funkcji f(x) = -2x2 - x + 2

Weźmy przykładowo funkcję f(x) = -2x2 - x + 2. Będziemy szukać jej miejsca zerowego na przedziale [-3, 3]. Jak widać na zamieszczonym po prawej stronie obrazku maksimum powinno znajdować się w punkcie xmax = 0.25. Poniżej zostały przedstawione kolejne iteracje wyliczania wyniku. Przyjmujemy, że wykonujemy, aż przedział będzie mniejszy niż 0.1. Wartości zostały przedstawione z dokładnością do czterech miejsc po przecinku.

Przedział
[a, b]
f(p1)f(p2)Komentarz
[-3, 3]1-1odrzucamy prawy
[-3, 1]-1.888892.11111odrzucamy lewy
[-1.66667, 1]1.56791.8642odrzucamy lewy
[-0.777778, 1]2.11661.26063odrzucamy prawy
[-0.777778, 0.407407]2.089771.98735odrzucamy prawy
[-0.777778, 0.0123457]1.985182.125odrzucamy lewy
[-0.514403, 0.0123457]2.109222.10994odrzucamy lewy
[-0.33882, 0.0123457]2.123412.08278odrzucamy prawy
[-0.33882, -0.10471]2.124772.11595odrzucamy prawy
[-0.33882, -0.182747]2.122292.12454odrzucamy lewy
[-0.286796, -0.182747]2.124992.12288odrzucamy prawy
[-0.286796, -0.21743]--Różnica przedziałów mniejsza niż 0.1

W celu popełnienia jak najmniejszego błędu przyjmujemy, że punkt x leży pośrodku przedziału [a, b], więc x = -0.252113. Dokładny punkt to x = -0.25. Punkt ten można uzyskać zmniejszając precyzję poszukiwań na np. 0.0001. Wtedy algorytm zwraca x = -0.25001. Tym razem jednak zostało wykonane ponad 2 razy więcej iteracji.

Implementacja

Podczas implementacji tego algorytmu należy pamiętać, że znalezione wartości w programie będą miały postać przybliżoną, więc warto dodać dodatkowy argument precyzja, który określi dokładność z jaką mają być prowadzone obliczenia. Jednym z pomysłów jest precyzja określająca minimalną długość przedziału. Po osiągnięciu ustalonej długości przedziału podajemy wartość pośrodku przedziału, aby popełnić jak najmniejszy błąd.

Założenia

Podczas implementowania zadania przyda się wczytać funkcję od użytkownika. Skorzystam tutaj z własnej biblioteki wielomian.h, która umożliwia wczytywanie wielomianu, jego wypisanie czy obliczenie wartości w konkretnym punkcie. Szerzej o bibliotece można znaleźć w artykule o Schemacie Hornera.

Wyszukiwanie maksimum

Na początek zastanówmy się nad przypadkiem, gdy chcemy wyszukać maksimum funkcji. Funkcja szukajMaksimum() przyjmuje cztery argumenty: wielomian w, który odpowiada funkcji, lewy i prawy jako przedział [a, b] oraz precyzja - do jakiej rozpiętości ma zostać zawężony maksymalnie przedział.

  1. double szukajMaksimum(wielomian* w, double lewy, double prawy, double precyzja = 0.0001) {
  2.   while (true) {
  3.     if (abs(prawy - lewy) < precyzja)
  4.       return (lewy + prawy) / 2;
  5.     double znacznikLewy = lewy + (prawy - lewy) / 3;
  6.     double znacznikPrawy = prawy - (prawy - lewy) / 3;
  7.     if (wartosc_wielomianu(w, znacznikLewy) <
  8.       wartosc_wielomianu(w, znacznikPrawy)) {
  9.       lewy = znacznikLewy;
  10.     } else {
  11.       prawy = znacznikPrawy;
  12.     }
  13.   }
  14. }

Wyszukiwanie maksimum

W analogiczny sposób implementuje się wyszukiwanie minimum z tą różnicą, że należy zamienić zawężanie przedziałów w instrukcji warunkowej. Wystarczy zmienić znak mniejszości na większości.

Testowanie funkcji

W celu sprawdzenia napisanej funkcji można skorzystać z poniższego fragmentu kodu:

  1. int main() {
  2.   cout << "Podaj wzor funkcji (tylko wielomian):\n";
  3.   wielomian* w = wczytajWieloman();
  4.   cout << "f(x) = ";
  5.   wypiszWieloman(w);
  6.   double a, b;
  7.   cout << "Podaj przedzial [a, b]\na = ";
  8.   cin >> a;
  9.   cout << "b = ";
  10.   cin >> b;
  11.   cout << "Szukany x to " << szukajMaksimum(w, a, b) << endl;
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz rekurencyjną wersję kodu, która będzie wyszukiwać minimum funkcji modalnej używają Wyszukiwania Trójkowego. Przetestuj działanie napisanej funkcji.

Przykładowo dla funkcji f(x) = 7x2 - 4x - 3, przedziału [-3, 3] i precyzji Δ = 0.0001 program powinien znaleźć xmin = 0.285725.