Home - Fibonacci Suche

Suchen
Direkt zum Seiteninhalt

Hauptmenü

Ein- und mehrdimensionale Fibonacci Suche
- ganz einfach -


Vorbemerkungen
Über Fibonacci-Zahlen gibt es in der Literatur viele Abhandlungen, deshalb wird hier nur kurz darauf eingegangen. Diese Zahlen haben auch für Suchalgorithmen große Bedeutung. Auch hierzu findet man vor allem im Internet viele Beiträge.
  Viele Beschreibungen von Suchalgorithmen mittels Fibonacci-Zahlen gehen davon aus, dass ausgehend von einem Intervall [a, b], innerhalb dessen das Minimum bzw. für  Maximum einer Funktion y=f(x) bestimmt werden soll, nach bestimmten Regeln mit einer vorgegebenen Anzahl von m Suchschritten immer weitere kleinere Intervalle bestimmt werden, in denen das gesuchte Minimum bzw. Maximum liegt. Solch ein Algorithmus ist recht unübersichtlich und für eine mehrdimensionale Anwendung  äußerst unpraktikabel.
  Sozusagen als Nebenprodukt meiner Diplomarbeit (1973), die sich mit zeitoptimalen Steuerungen befasste, hatte ich einen Algorithmus entwickelt, der die Fibonacci-Suche sehr vereinfachte und problemlos auf mehrdimensionale Probleme anwendbar machte.
 

Kurzbeschreibung der Fibonacci Zahlen
Für Fibonacci-Zahlen gilt folgende Bildungsregel:


und allgemein für das m-te Glied der Zahlenfolge
                                                     Gl. (1)                                                                                          


Damit ergibt sich die unendliche Zahlenfolge:  0, 1 , 1, 2, 3, 5, 8, 13, 21, ...
Hinweis

In manchen Publikationen wird die Zahlenfolge nicht mit F0 = 0 sondern mit F1 = 1 begonnen. Beides ist korrekt.

Die einzelnen Werte können aber nicht nur rekursiv, sondern auch direkt berechnet werden.
Es gilt

                  


Weiteres
Auf den folgenden Seiten werden zunächst die Grundlagen für einen effektiven  Such-Algorithmus dargestellt. Danach wird der Algorithmus für die eindimensionale Suche entwickelt und darauf aufbauend dieser für die n-dimensionale Suche erweitert.
Für Interessierte wird dann noch eine ganz kurze Herleitung der Fibonacci-Formel Gl. (2) dargestellt.


 
Zurück zum Seiteninhalt | Zurück zum Hauptmenü