Diese Frage bezieht sich auf dieses , es wurde von der Optimierung abgeleitet der Weg über eine Reihe von Punkten. Die Situation ist wie folgt: Ein Objekt verfährt einen bestimmten Pfad, der aus einer Liste von 2D-Punkten besteht. (Mehr Ds sind möglich, aber da jede Wendung technisch 2D ist, reicht das Lösen für zwei Dimensionen aus.) An jedem Punkt kann dieses Objekt seine Geschwindigkeit durch einen Vektor ändern, dessen maximale Länge vorbestimmt ist (einem Punkt zugewiesen). Geschwindigkeit am Ende des Pfades ist irrelevant. Die Frage ist, wie man die minimale Zeit bestimmt, die man auf diesem Weg verbringt. Gibt es einen effizienten Algorithmus für diese Aufgabe? Ein Greedy-Algorithmus kann das Objekt im Fall von speziell vorbereiteten Daten eventuell langsam zu einem Crawl machen oder sogar das Objekt nicht in die Lage versetzen, zu seinem nächsten bestimmten Punkt zu gelangen. Ein rückwärts-gieriger Algorithmus ist auch mit dem gleichen Fehler behaftet, es ist nicht immer gut, das Ende mit maximaler Geschwindigkeit zu erreichen.
Ein Beispiel: Punktvektor ist: {(0,0), (0,1), (1,1), (2,2)} und maximaler Längenvektor ist {2.0, 2.0, 3.0} . Der Punkt verläuft beispielsweise bei (0,sqrt(2)) von p1 nach p2, dann bei (sqrt(2),0) von p2 nach p3 und bei (s,s) bei jeder maximalen Geschwindigkeit s von p3 nach p4. Und das könnte eine suboptimale Lösung sein, sagen Sie, dass Sie um 0,01 von p1 auf p2 verlangsamen, indem Sie ein wenig von p2 nach p3 beschleunigen, dann um ein weiteres kurz auf p3 bis p4, wobei die mögliche Gesamtzeit geringer ist Geschwindigkeitssatz.
Dies ist ein konvexes Optimierungsproblem, das durch allgemeine nichtlineare Optimierungsbibliotheken gelöst werden kann. In SciPy:
%Vor%Tags und Links algorithm language-agnostic mathematical-optimization