Partitionner un ensemble en groupes K avec un nombre minimum de mouvements

Si je comprends bien, les problèmes sont les suivants:

Nous avons n points sur une ligne. Nous voulons placer la position K sur la ligne. Je les appelle des destinations. Déplacez chacun des points de n sur l'une des k Destinations K afin que la somme des distances est minimale. J'appelle cette somme, coût total. Destinations peuvent se chevaucher.

Un fait évident est que pour chaque point, nous devrions rechercher les destinations les plus proches situées à gauche et les destinations les plus proches de droite et choisissez le plus proche.

Un autre fait important est que toutes les destinations devraient être sur les points. Parce que nous pouvons les déplacer sur la ligne à droite ou à gauche pour atteindre un point sans augmenter la distance totale.

Par ces faits, envisagez de suivre la solution DP:

DP [i] [j] signifie le coût total minimum nécessaire pour le premier point que je pointe, lorsque nous ne pouvons utiliser que des destinations J et doivent mettre une destination sur le point I-Th.

Calculer DP [I] [J] [J] Fixez la destination avant le i-the Point (nous avons le choix), et pour chaque choix (par exemple K-th point) Calculez la distance nécessaire pour les points entre l'I- Th Point et le nouveau point ajouté (K-th Point). Ajoutez ceci avec DP [K] [J - 1] et trouvez le minimum pour tous K.

Le calcul des états initiaux (par exemple J = 1) et la réponse finale est laissée comme un exercice!

tâche 0 - Trier la position des objets dans l'ordre non diminuant

Définissez-vous 'Centre' code> comme position de l'objet où il est décalé vers. code> p>

Nous avons maintenant deux observations; p>

1. pour N POSITIONS Le "Centre" serait la position la plus proche de la moyenne de ces n positions. CODE> Exemple, laisse 1,3,6,10 être les positions. Alors signifie = 5. La position la plus proche est 6. Par conséquent, le Centre de ces éléments est de 6. Cela nous donne la position avec un coût minimum de déplacement lorsque tous les éléments doivent être regroupés en 1 groupe. P> LI>

2. Soit n positions être regroupés en k groupes "de manière optimale". Lorsque N + 1 TH Object est ajouté CODE>, il ne dérangera que le groupe K TH, c'est-à-dire que Les premiers groupes K-1 resteront inchangés. Code> P> li> ol>

   de ces observations, nous construisons une approche de programmation dynamique. p>

   Sorting O(NlogN)
   Total Cost Computation Matrix = Total elements * Computecost = O(NK * N)
   Total = O(NlogN + N*NK) = O(N*NK)
   

regardons k = 1.

pour k = 1 et n impair, tous les points doivent passer au point central. Pour K = 1 et N Même, tous les points doivent passer à l'un des points centraux ou de tout endroit entre eux. Par «centre», je veux dire en termes de nombre de points de chaque côté, c'est-à-dire la médiane.

Vous pouvez voir cela parce que si vous sélectionnez une tache cible, X, avec plus de points à sa droite qu'il ne reste plus qu'à une nouvelle cible 1 à droite de X entraînerait une réduction des coûts (sauf indication contraire d'une nouvelle cible. Pointez à droite que la gauche et la cible est un point, auquel cas n est même et la cible est allumée / entre les deux points centraux).

Si vos points sont déjà triés, il s'agit d'une opération O (1). Sinon, je crois que c'est O (n) (via un algorithme statistique de commande).

Une fois que vous avez trouvé l'endroit où tous les points se déplacent, c'est O (n) de trouver le coût.

Ainsi, que les points soient triés ou non, c'est O (n).

Ce problème est une instance unidimensionnelle du problème K-Medians , qui peut être indiqué comme suit. Compte tenu d'un ensemble de points X_1 ... x_n, partitionnez ces points dans K Ensembles S_1 ... S_K et choisissez K Emplacements Y_1 ... Y_K d'une manière qui minimise la somme sur tout X_I de | x_i-y_f (i) | , où y_f (i) est l'emplacement correspondant à l'ensemble sur lequel x_i est attribué.

En raison du fait que la médiane est le minimiseur de la population pour la distance absolue (norme L_1) , il s'ensuit que chaque emplacement Y_J sera la médiane des éléments x dans l'ensemble correspondant S_J (d'où le nom K-MEDIANIANS). Depuis que vous examinez des valeurs entière, il y a la technicité que si S_J contient un nombre pair d'éléments, la médiane pourrait ne pas être un entier, mais dans de tels cas, choisir l'entiers suivant au-dessus ou au-dessous de la médiane donnera la même somme de Distances absolues. P>

L'heuristique standard pour la résolution de K-Medians (et le plus commun et plus commun K-signifie problème) est itératif, mais cela n'est pas garanti de produire une solution optimale ou même bonne. La résolution du problème des K-Medians pour les espaces métriques généraux est le NP-Difficile et la recherche d'approximations efficaces des K-Médians est un problème de recherche ouvert. "Approximation de K-Médians" Google, par exemple, entraînera un tas de papiers donnant des schémas d'approximation. http://www.cis.upenn.edu/~sudipto/mypapers/kmedian_jcsss .pdf http://graphics.stanford.edu/courses/cs468 -06-hiver / papiers / ar-clustering.pdf p>

Dans une dimension, les choses deviennent plus faciles et vous pouvez utiliser une approche de programmation dynamique. Une solution DP au problème k-ois dimensionnel correspondant est décrite dans Ce document et le code source dans R est disponible ici . Voir le papier pour plus de détails, mais l'idée est essentiellement la même que ce que @sajaljain a proposé et peut facilement être adapté pour résoudre le problème des médianes K plutôt que de k-moyen. Pour J xxx pré>

où q gammes de j-1 à m-1 et coût code> est égal à la somme des distances absolues de la médiane . Avec une implémentation naïve O (n) de coût code>, cela produirait une solution O (N ^ 3K) DP à l'ensemble du problème. Cependant, cela peut être amélioré à O (n ^ 2k) en raison du fait que le coût peut être mis à jour en temps constant plutôt que calculé à partir de zéro à chaque fois, en utilisant le fait que, pour une séquence triée: P>

Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_1...x_h)-x_1   if h is odd
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_2...x_h)-x_1   if h is even