Algorytm dopasowywania liczb przy minimalnej liczbie ruchów

Jest to rodzaj pytania do edycji i jest bardzo łatwe. Jestem po prostu dość martwy w tym temacie i jak dotąd nie mogę tego rozgryźć.

---

Biorąc pod uwagę szereg liczb, np

[3, 1, 1, 1]

Jak najskuteczniej przekształcić wszystkie liczby w tę samą liczbę przy minimalnej liczbie „ruchów”? Przez „przeniesienie” rozumie się dodanie lub usunięcie jednego z numeru.

W powyższym przykładzie najbardziej wydajnymi ruchami byłyby:

[1, 1, 1, 1]

Wymagałoby to 2 ruchów, dwukrotnie zmniejszając pierwszą liczbę.

Nie mogę znaleźć najlepszego sposobu, aby się tego dowiedzieć, biorąc pod uwagę znacznie większe tablice setek liczb.

Początkowo próbowałem obliczyć zaokrągloną średnią liczbę (sumę wszystkich podzieloną przez długość), a następnie zredukować ją do obliczonej średniej, ale powyższy przykład złamał to, wymagając 4 ruchów zamiast 2.

Myślę, że mógłbym wymyślić:

1. Średnia,
2. Tryb,
3. Mediana

i uzyskaj odległość edycji każdego z nich, wybierając minimalną odległość. Nie jestem jednak pewien, czy byłoby to poprawne w każdym przypadku. Skąd mam wiedzieć?

Odpowiedź brzmi: wziąć medianę. Jedną z właściwości mediany jest to, że minimalizuje odległość L1 do każdego elementu. (Aby zrozumieć sens artykułu z Wikipedii, weź rozkład prawdopodobieństwa za równomierny rozkład w stosunku do oryginalnej serii liczb).

To jest algorytm, który rozwiązuje problem (pierwotnie napisany przez dc2 ):

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

Jak wspomina TCSGrad, biorąc pod uwagę listę liczb całkowitych , szukasz liczby całkowitej m minimalizującej δ ( m ) = n ∑ i = 1 | m - x i | . Pouczające jest obliczenie δ ( m + 1 ) - δ ( m ) : δ ( m + 1 ) - δ ( m ) $x_1,\ldots,x_n$$m$

$$\delta(m) = \sum_{i=1}^n |m - x_i|.$$ $\delta(m+1) - \delta(m)$ Gdymzmienia się z-∞na+∞, ilośćδ(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)$idzie od do n . Ponadto przełącza wartości tylko w punktach x 1 , … , x n . Nie jest trudno sprawdzić, czy optymalna wartość m jest minimalnym punktem, w którym δ ( m + 1 ) - δ ( m ) ≥ 0 . Ten minimalny punkt jest jednym z x i , więc odległość edycji wynosi 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$

Problem można sformułować jako problem LP:

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

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

$x$

$x$$x$

EDYCJA : Jak wskazano w komentarzach, funkcją celu powinna być suma nad różnicami bezwzględnymi. Aby przekształcić go z powrotem w standardowy LP, możemy przepisać LP jako:

$$\min \sum a'_i$$

z zastrzeżeniem:

$$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$