Algorithme pour faire correspondre les nombres avec un nombre minimum de coups

C'est une sorte de question de distance de montage, et c'est très simple. Je suis tout simplement mort cérébrale sur ce sujet et je ne peux pas le comprendre jusqu'à présent.

---

Étant donné une série de nombres, par exemple

[3, 1, 1, 1]

Comment transformer le plus efficacement tous les nombres en un même nombre, avec le nombre minimum de "coups"? Par «déplacer», on entend ajouter ou supprimer un numéro.

Dans l'exemple ci-dessus, les mouvements les plus efficaces seraient:

[1, 1, 1, 1]

Cela nécessiterait 2 mouvements, réduisant le premier nombre deux fois.

Je ne peux pas trouver la meilleure façon de le savoir, étant donné des tableaux beaucoup plus grands de centaines de nombres.

J'ai à l'origine essayé de calculer le nombre moyen arrondi (somme de tous divisée par la longueur), puis de les réduire à la moyenne calculée, mais l'exemple ci-dessus a cassé cela, nécessitant 4 mouvements au lieu de 2.

Je suppose que je pourrais comprendre:

1. La moyenne,
2. La mode,
3. La médiane

et obtenez la distance d'édition de chacun d'eux, en choisissant la distance minimale. Cependant, je ne suis pas sûr que ce serait correct dans chaque cas. Comment puis-je savoir?

La réponse est de prendre la médiane. L'une des propriétés de la médiane est qu'elle minimise la distance L1 à chaque élément. (Pour donner un sens à l'article Wikipedia, prenez la distribution de probabilité comme étant la distribution uniforme sur votre série de nombres d'origine).

Voici l'algorithme qui résout le problème (écrit à l'origine par 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

$x_1,\ldots,x_n$$m$

$$\delta(m) = \sum_{i=1}^n |m - x_i|.$$ $\delta(m+1) - \delta(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)$$-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))$

Supposons en outre que tous les sont distincts et que est impair. Soit la médiane du . Alors tandis que , et donc est l'optimum unique. Si est pair, un calcul similaire montre que nous pouvons choisir n'importe quel point de l'intervalle reliant les médianes. Un raisonnement similaire mais plus élaboré montre que toute médiane est optimale même lorsque les ne sont pas distincts. Il n'est donc pas nécessaire de calculer sur tous les .$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$

Le problème peut être formulé comme un problème LP:

Étant donné un ensemble de nombres , résolvez le LP suivant:$n$$[a_1,a_2... a_n]$

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

(Suppression des contraintes sur , qui n'étaient pas nécessaires comme l'a souligné Raphael)$x$

Une fois le LP résolu, vous obtiendrez une valeur de correspondant à la solution. Si est un entier, vous avez terminé - sinon, arrondissez-le à l'entier le plus proche.$x$$x$

EDIT : Comme indiqué dans les commentaires, la fonction objectif doit être la somme des différences absolues. Afin de le reconvertir en LP standard, nous pouvons réécrire le LP comme:

$$\min \sum a'_i$$

sujet à:

a ′ i ≤ a i - x ∀ i a ′ i , x ′ ≥ 0 ∀

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

A la solution optimale, , et nous pouvons obtenir la valeur de partir de la solution.$a_i' = | a_i - x|\ \forall i$$x$