Suchstrategie - Fibonacci Suche

Suchen
Direkt zum Seiteninhalt

Hauptmenü

Suchstrategie

Wie bereits am Anfang bemerkt, funktioniert der übliche Algorithmus derart, dass in spezieller Weise immer kleiner werdende
Intervalle gebildet werden. Nach dem m-ten Schritt wird dann die Lösung gefunden.
Mit der hier beschriebenen Strategie wird das Verfahren extrem einfach. Dazu wird ermittelt, wie sich die Abstände der untersuchten Punkte verhalten. Dabei ergab sich dann ein ganz einfacher Zusammenhang.

Gegeben sei das zu untersuchende Intervall [a,b]. Die Anzahl der Suchschritte sei m. Weiterhin gehen
wir der einfacheren Erklärung wegen generell davon aus, dass ein Minimum gesucht werden soll.
Ausgehend vom Intervallanfang a sind die ersten 2 zu untersuchenden Punkte



Die Abstände von x1 zur linken Intervallgrenze (a) und x2 zur rechten Intervallgrenze (b) sind gleich.
Bei unseren Betrachtungen gehen wir jetzt nur von der linken Intervallgrenze (a) aus.
Der Abstand des 1. Suchpunktes von a ist



Für den Abstand des 2. Suchpunktes vom 1. folgt



Je nachdem an welchem der Punkte der kleinere Funktionswert auftritt, wird dieser als Ausgangspunkt
für den folgenden Suchschritt genommen.

Weitere Betrachtungen, auf die hier nicht näher eingegangen wird, ergeben den Abstand des 3. Suchpunktes
vom vorhergehenden zu



Allgemein ergibt sich für die Schrittweite beim k-ten Suchschritt (k=1,…,m)




Jetzt muss nur noch die Suchrichtung bestimmt werden.
Die Suchrichtung wird solange beibehalten, wie ein Funktionswert kleiner als der vorhergenede ist, ansonsten wird sie geändert.


Damit ist die Grundlage für den Algorithmus der eindimensionalen Fibonacci-Suche gegeben.
Er ist so einfach,  dass die Erweiterung auf höhere Dimensionen überhaupt kein Problem darstellt. Z.B. werden bei einer 2-dimensionalen Suche y=f(x1,x2)  die Schleifen ineinander verschachtelt. Die äußere Schleife geht zum 1. Suchpunkt von x1, danach vollzieht die innere Schleife alle Suchschritte für x2. Dann geht die äußere Schleife zum Suchpunkt 2 für x1, die innere Schleife geht wiederum alle Suchpunkte für x2 durch, usw. Natürlich kann für jede Dimension eine unterschiedliche Anzahl von Suchschritten gewählt werden.

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