Angenommen, wir haben eine Zahl M und eine Liste von n Zahlen, L [1], ..., L [n], und wir wollen eine Teilfolge von mindestens q der letzteren Zahlen finden, die die Summe der quadrierten Fehler (SSE) in Bezug auf M, wobei die SSE eine Liste von Positionen k x [1], ..., x [k] in Bezug auf M wird durch
SSE(M, x[1], ..., x[k]) = sum((L[x[i]]-L[x[i-1]]-M)^2) over all 2 <= i <= k,
gegeben mit der SSE einer Liste von 0 oder 1 Positionen definiert als 0.
(Ich führe hier den Parameter q und die zugehörige Einschränkung in die Länge der Untersequenz ein, denn ohne diese gibt es immer eine Untersequenz der Länge genau 2, die die mi nimum möglich SSE - und ich vermute, dass eine solche kurze Sequenz Ihnen nicht hilfreich)
Dieses Problem in O (Qn^2) Zeit und O (QN) Raum gelöst werden könnendynamic programming verwenden. .
definieren f (i, j) erreichbar unter den folgenden Randbedingungen die minimale Summe der quadrierten Fehler sein:
- Die Anzahl an Position i ausgewählt wird, und ist die am weitesten rechts liegende Position ausgewählt. (Hier bedeutet i = 0, dass keine Positionen ausgewählt sind.)
- Wir fordern, dass mindestens j (anstelle von q) dieser ersten i-Nummern ausgewählt wird.
Auch g definieren (i, j) das Minimum von f (k, j) über alle < 0 = k < sein = i. Somit ist g (n, q) die kleinste Summe von quadratischen Fehlern, die für das gesamte ursprüngliche Problem erreichbar sind. Für eine effiziente (O (1)) Berechnung von g (i, j), beachten Sie, dass
g(i>0, j>0) = min(g(i-1, j), f(i, j))
g(0, 0) = 0
g(0, j>0) = infinity
Um f (i, j) zu berechnen, beachten Sie, dass, wenn i> 0, dann muss jede Lösung durch Anhängen der gebildet werden i-te Position zu irgendeiner Lösung Y, die wenigstens j-1 Positionen auswählt und deren am weitesten rechts liegende ausgewählte Position sich links von i befindet - dh deren am weitesten rechts liegende ausgewählte Position k ist, für einige k < i. Die Gesamt-SSE dieser Lösung für das (i, j) -Teilproblem wird sein, was immer die SSE von Y war, zuzüglich eines festen Terms von (L [x [i]] - L [x [k]] - M)^2 - - Um diese Gesamt-SSE zu minimieren, genügt es, die SSE von Y zu minimieren. Aber wir können dieses Minimum berechnen: es ist g (k, j-1).
Da dies gilt für jede 0 < = k < i, sie alle solche Werte von k, um zu versuchen genügt, und die man nehmen, die die niedrigste Gesamt SSE gibt:
f(i>=j, j>=2) = min of (g(k, j-1) + (L[x[i]]-L[x[k]]-M)^2) over all 0 <= k < i
f(i>=j, j<2) = 0 # If we only need 0 or 1 position, SSE is 0
f(i, j>i) = infinity # Can't choose > i positions if the rightmost chosen position is i
Mit den oben genannten Rezidiven und Base In Fällen können wir g (n, q) berechnen, die minimal mögliche Summe von quadratischen Fehlern für das gesamte Problem. Nach memoising values of f(i, j) and g(i, j) ist die Zeit zur Berechnung aller benötigten Werte von f (i, j) O (qn^2), da es höchstens (n + 1) * (q + 1) mögliche unterschiedliche Kombinationen von Eingabeparametern gibt (i, j), und das Berechnen eines bestimmten Wertes von f (i, j) erfordert höchstens (n + 1) Iterationen der Schleife, die Werte von k auswählt, wobei jede Iteration O (1) Zeit außerhalb von rekursiven Unteralarmen benötigt. Die Speicherung von Lösungswerten von f (i, j) erfordert höchstens (n + 1) * (q + 1) oder O (qn), Raum und ebenso für g (i, j). Wie oben festgestellt, kann g (i, j) in O (1) -Zeit berechnet werden, wenn alle benötigten Werte von f (x, y) berechnet wurden, so dass g (n, q) in derselben Zeitkomplexität berechnet werden kann.
Um tatsächlich eine Lösung entsprechend dieser minimalen SSE zu rekonstruieren, können Sie die berechneten Werte von f (i, j) in umgekehrter Reihenfolge zurückverfolgen, wobei jedes Mal nach einem Wert von k gesucht wird, der einen Minimalwert in der Wiederholung erreicht (Es kann im Allgemeinen viele solche Werte von k geben), setze i auf diesen Wert von k und fahre fort bis i = 0. Dies ist eine standardmäßige dynamische Programmiertechnik.
Ihre Bedingung (3) nützlich ist, in Verbindung steht, was Sie versuchen, zu tun, was zu sein scheint: Aus einer Folge von n Knoten, wählen Sie eine Teilfolge (Lücken erlaubt) von k Knotenpositionen x_1, ..., x_k, so dass 1 <= x_i <= n, i
Hallo, Sie haben die wichtigen Informationen aus dem Text sehr gut abstrahiert, danke dafür. Alles, was du geschrieben hast, ist korrekt. Ich bemerkte auch das Problem des Algorithmus, dann die Anzahl der Knoten zu reduzieren. Alles, was ich tun kann, ist die Anzahl der Knoten zu schätzen, die berücksichtigt werden sollten. Dies wird jedoch nur eine (relativ gute) Näherung der korrekten Anzahl von Knoten sein. Eine zusätzliche Einschränkung könnte daher sein, diesen Wert zu berücksichtigen, z. um die Anzahl von Knoten zu beschränken, die größer als ein Minimalwert ist. –
Gut, das ist genau das, was ich vorschlage, und das Problem löst meine Antwort :) –