Effizienter Algorithmus für dieses Optimierungsproblem? Dynamische Programmierung?

Ich habe ein Diagramm erstellt, das zeigt, was ich erreichen möchte.

Bild in voller Größe

In der Eingabesequenz sind die Knoten so nah wie möglich beieinander. Aber ich möchte, dass die weißen Knoten so nah wie möglich an ihren jeweiligen schwarzen Knoten sind. Die Kanten zwischen Knoten können verlängert werden, um diesen Fehler zu minimieren. Sie können nicht gekürzt werden. So 1 -> 2kann zum Beispiel nicht weniger als 4 sein.

Ich habe eine mögliche Lösung aufgenommen. Die verlängerten Kanten sind beschriftet. Beachten Sie, dass durch das Verlängern einer Kante alle Knoten nach rechts verschoben werden.

Diese Achse ist durchgehend, aber ich könnte sie möglicherweise diskretisieren, wenn das hilft.

Ich denke, ein dynamischer Programmieransatz könnte hier funktionieren, bin mir aber nicht sicher - ich war nie sehr gut mit DP.

Was ist der am schnellsten laufende Algorithmus, der dies lösen kann? Kann dies als bekanntes Problem eingestuft / umrahmt werden?

Dies ist nur eine Erweiterung der Antwort von @ Sébastien Loisel.

Beachten Sie minimieren $(x_i-y_i)^2$ vorbehaltlich $x_i-x_{i-1}\ge c_i$ ist gleichbedeutend mit minimieren $(x_i-(y_i-c_i))^2$ vorbehaltlich $x_i\geq x_{i-1}$. Lassen$a_i=y_i-c_i$dann ist dies genau das isotonische Regressionsproblem . Es gibt eine$O(n)$ Zeitalgorithmus.

Wenn Sie die Achse diskretisieren, können Sie die dynamische Programmierung verwenden. Für jeden Ball$b$ und machbarer Ort $\ell$ Berechnen Sie (innerhalb einiger vernünftiger Grenzen) den besten mittleren quadratischen Fehler für den ersten $b$Bälle. Dies kann in der Regel nur die gleiche Art von Informationen für Ball erfolgen$b-1$.

Dies ist ein quadratisches Programm. Sie versuchen, die Summe von zu minimieren$(x_i-y_i)^2$ vorbehaltlich $x_i-x_{i-1}\ge c_i$.