Algorithmus zum Abgleichen von Zahlen mit einer minimalen Anzahl von Zügen

Dies ist eine Art Frage zur Bearbeitungsentfernung und sehr einfach. Ich bin in diesem Bereich einfach ziemlich hirntot und kann es bisher nicht herausfinden.

---

Bei einer Reihe von Zahlen, z

[3, 1, 1, 1]

Wie würde man am effizientesten alle Zahlen in dieselbe Zahl verwandeln, mit der minimalen Anzahl von "Zügen"? Mit "Verschieben" ist das Hinzufügen oder Entfernen einer Zahl zu einer Zahl gemeint.

Im obigen Beispiel wären die effizientesten Schritte:

[1, 1, 1, 1]

Dies würde 2 Züge erfordern und die erste Zahl zweimal reduzieren.

Ich kann nicht herausfinden, wie ich das am besten herausfinden kann, wenn man viel größere Arrays mit Hunderten von Zahlen betrachtet.

Ich habe ursprünglich versucht, die gerundete Durchschnittszahl (Summe aller geteilt durch die Länge) zu berechnen und sie dann auf den berechneten Durchschnitt zu reduzieren, aber das obige Beispiel hat dies gebrochen und erfordert 4 Züge anstelle von 2.

Ich könnte mir vorstellen:

1. Der Durchschnitt,
2. Der Modus,
3. Der Median

und ermitteln Sie den Bearbeitungsabstand für jeden von ihnen, indem Sie den Mindestabstand auswählen. Ich bin mir jedoch nicht sicher, ob dies in jedem Fall richtig wäre. Wie kann ich es wissen?

Die Antwort ist, den Median zu nehmen. Eine der Eigenschaften des Medians ist, dass er den L1-Abstand zu jedem Element minimiert . (Um den Wikipedia-Artikel zu verstehen, nehmen Sie die Wahrscheinlichkeitsverteilung als gleichmäßige Verteilung über Ihre ursprüngliche Zahlenreihe.)

Dies ist der Algorithmus, der das Problem löst (ursprünglich von dc2 geschrieben ):

function median(arr) {
  arr.sort(function(a, b) { return a - b; });
  var half = floor(arr.length/2);
  if ( arr.length % 2 ) {
    return arr[half];
  } else {
    return (arr[half-1] + arr[half]) / 2.0;
  }
}

function minl1(arr) {
  var moves = 0;
  var mdn = median(arr);
  for ( var i = 0; i < arr.length; ++i ) {
    moves += Math.abs(mdn - arr[i]);
  }
  return moves;
}

minl1([3, 1, 1, 1]); // -> 2

Wie TCSGrad erwähnt, suchen Sie bei einer Liste von ganzen Zahlen nach der ganzen Zahl m, die δ ( m ) = n ∑ i = 1 | minimiert m - x i | . Es ist lehrreich, δ ( m + 1 ) - δ ( m ) zu berechnen : δ ( m + 1 ) - δ ( m ) $x_1,\ldots,x_n$$m$

$$\delta(m) = \sum_{i=1}^n |m - x_i|.$$ $\delta(m+1) - \delta(m)$ Wennmvon-∞nach+∞ geht, ist die Größeδ(m+1)-δ(m $$\delta(m+1) - \delta(m) = \sum_{i=1}^n \begin{cases} +1 & m \geq x_i \\ -1 & m < x_i \end{cases} = \#\{i : m \geq x_i\} - \#\{i : m < x_i\}.$$ $m$$-\infty$$+\infty$$\delta(m+1) - \delta(m)$geht von nach n . Außerdem werden die Werte nur an den Punkten x 1 , … , x n umgeschaltet . Es ist nicht schwer zu überprüfen, ob ein optimaler Wert von m der minimale Punkt ist, an dem δ ( m + 1 ) - δ ( m ) ≥ 0 ist . Dieser Minimalpunkt ist einer der x i , daher beträgt der Bearbeitungsabstand min ( δ ( x 1 ) , … , δ ( $-n$$n$$x_1,\ldots,x_n$$m$$\delta(m+1) - \delta(m) \geq 0$$x_i$ .$\min(\delta(x_1),\ldots,\delta(x_n))$

$x_i$$n$$m$$x_i$$\delta(m+1) - \delta(m) = 1$$\delta(m) - \delta(m-1) = -1$$m$$n$$x_i$$\delta$$x_i$

Das Problem kann als LP-Problem formuliert werden:

$n$$[a_1,a_2... a_n]$

$$\min \sum |a_i - x|$$

$x$

$x$$x$

EDIT : Wie in den Kommentaren ausgeführt, sollte die Zielfunktion Summe über absolute Differenzen sein. Um es wieder in eine Standard-LP umzuwandeln, können wir die LP wie folgt umschreiben:

$$\min \sum a'_i$$

vorbehaltlich:

$$a'_i \geq a_i - x\ \forall i$$ $$a'_i \leq a_i - x\ \forall i$$ $$a'_i, x' \geq 0\ \forall i$$

$a_i' = | a_i - x|\ \forall i$$x$