Angenommen, ich möchte eine unimodale Funktion optimieren, die in einem realen Intervall definiert ist. Ich kann den bekannten Algorithmus verwenden, wie er in Wikipedia unter dem Namen ternäre Suche beschrieben ist .
Im Falle des Algorithmus , dass Intervalle wiederholt zu halbieren, ist es üblich , den Begriff zu reservieren binäre Suche für diskrete Probleme und die Verwendung des Begriffs Bisektionsmethode anders. Wenn ich diese Konvention extrapoliere, vermute ich, dass der Begriff Trisektionsmethode für den Algorithmus gelten könnte, der mein Problem löst.
Meine Frage ist, ob es unter Akademikern üblich ist und sicher ist, den Begriff ternäre Suche in z. B. Abschlussarbeiten anzuwenden, selbst wenn der Algorithmus auf ein kontinuierliches Problem angewendet wird. Ich brauche dafür eine seriöse Quelle. Mich interessiert auch, ob der Begriff Trisektionsmethode tatsächlich existiert.
Antworten:
Das Wort "bitonische Suche" kann sich wahrscheinlich auf dieses Konzept beziehen. Siehe zum Beispiel dieses Buch und diese Vorlesungsunterlagen .
quelle
Schauen Sie sich die Fibonacci-Suche und die Suche nach goldenen Schnitten an (der Artikel über die Fibonacci-Suche spricht von einem Array, aber die Technik ist genau wie die Golden-Section-Suche auf kontinuierliche Funktionen anwendbar). Die Fibonacci-Suche ist etwas schneller. Der Trick besteht darin, dass Sie die Punkte von einer Iteration zur nächsten wiederverwenden können. Für Fibonacci müssen Sie die Anzahl der Iterationen im Voraus bestimmen. Keine große Sache, Sie kennen die Präzision, die sowieso gesucht wird.
Es kann gezeigt werden, dass die Fibonacci-Suche am schnellsten möglich ist, wenn Sie nur die Funktionswerte für die relative Reihenfolge vergleichen. Wenn Sie die tatsächlichen Werte berücksichtigen, ist eine Form von Quasi-Newton schneller.
quelle