Partición de un conjunto en k grupos con un número mínimo de movimientos

Question

Tiene un conjunto de n objetos para los que se dan posiciones enteras. Un grupo de objetos es un conjunto de objetos en la misma posición (no necesariamente todos los objetos en esa posición: puede haber múltiples grupos en una sola posición). Los objetos se pueden mover hacia la izquierda o hacia la derecha, y el objetivo es mover estos objetos para formar grupos k, y para hacerlo con la distancia mínima movida.

Por ejemplo:

• con las posiciones iniciales en [4,4,7], y k = 3: el coste mínimo es 0.
• [4,4,7] y k = 2: coste mínimo es de 0
• [1,2,5,7] y k = 2: coste mínimo es de 1 + 2 = 3

he b Intentando utilizar un enfoque codicioso (calculando qué movimiento sería más corto) pero eso no funcionaría porque cada movimiento involucra dos elementos que podrían moverse de cualquier manera. Todavía no he podido formular un enfoque de programación dinámica, pero estoy trabajando en ello.

Answer 1

según tengo entendido, los problemas es:

tenemos n puntos en una línea. queremos colocar la posición k en la línea. Los llamo destinos. mueve cada uno de los n puntos a uno de los k destinos, por lo que la suma de las distancias es mínima. Llamo a esta suma, costo total. destinos pueden superponerse.

Un hecho obvio es que para cada punto debemos buscar los destinos más cercanos a la izquierda y los destinos más cercanos a la derecha y elegir el más cercano.

Otro hecho importante es que todos los destinos deben estar en los puntos. porque podemos moverlos en la línea hacia la derecha o hacia la izquierda para llegar a un punto sin aumentar la distancia total.

Por estos hechos considerar seguir solución de DP:

DP [i] [j]: el coste total mínimo necesario para el primer punto i, cuando podemos usar sólo destinos j, y tienen que poner un destino en el i-ésimo punto

para calcular DP [i] [j] arregla el destino antes del i-ésimo punto (tenemos opción), y para cada opción (por ejemplo, k-ésimo punto) calcule la distancia necesaria para puntos entre -th punto y el nuevo punto agregado (k-th punto). agréguelo con DP [k] [j - 1] y encuentre el mínimo para todos k.

el cálculo de los estados iniciales (por ejemplo, j = 1) y la respuesta final se deja como un ejercicio!

Answer 2

La tarea 0 - ordenar la posición de los objetos en orden no decreciente

Definamos 'center' como la posición del objeto donde es shifted to.

Ahora tenemos dos observaciones;

1. For N positions the 'center' would be the position which is nearest to the mean of these N positions. Ejemplo, deja 1,3,6,10 en las posiciones. Entonces mean = 5. La posición más cercana es 6. Por lo tanto, el centro para estos elementos es 6. Esto nos da la posición con un costo mínimo de movimiento cuando todos los elementos deben agruparse en 1 grupo.

2. Deje que las posiciones N se agrupen en K grupos "óptimamente". When N+1 th object is added, entonces se va a perturbar sólo el K-ésimo grupo, es decir, first K-1 groups will remain unchanged.

A partir de estas observaciones, construimos un enfoque de programación dinámica.

Let Cost[i][k] and Center[i][k] be two 2D arrays. 
Cost[i][k] = minimum cost when first 'i' objects are partitioned into 'k' groups 
Center[i][k] stores the center of the 'i-th' object when Cost[i][k] is computed. 

Let {L} be the elements from i-L,i-L+1,..i-1 which have the same center.
(Center[i-L][k] = Center[i-L+1][k] = ... = Center[i-1][k])
Estos son los únicos objetos que necesitan ser considerados en el cálculo para i-ésimo elemento (de observación 2)

Ahora

Cost[i][k] will be 
min(Cost[i-1][k-1] , Cost[i-L-1][k-1] + computecost(i-L, i-L+1, ... ,i)) 
Update Center[i-L ... i][k] 

computecost() se puede encontrar trivialmente al encontrar el centro (de la observación 1)

Complejidad del tiempo:

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

Answer 3

Veamos k = 1.

Para k = 1 y n impar, todos los puntos deben moverse al punto central. Para k = 1 yn incluso, todos los puntos deben moverse a cualquiera de los puntos centrales o cualquier punto entre ellos. Por "centro" me refiero en términos de cantidad de puntos a cada lado, es decir, la mediana.

Puede ver esto porque si selecciona un punto objetivo, x, con más puntos a la derecha de la izquierda, entonces un nuevo objetivo 1 a la derecha de x daría lugar a una reducción de costos (a menos que haya exactamente uno más punto a la derecha que a la izquierda y el punto objetivo es un punto, en cuyo caso n es par y el objetivo está en/entre los dos puntos centrales).

Si sus puntos ya están ordenados, esta es una operación O (1). Si no, creo que es O (n) (a través de un algoritmo de estadística de orden).

Una vez que haya encontrado el lugar al que se dirigen todos los puntos, es O (n) para encontrar el costo.

Por lo tanto, independientemente de si los puntos están ordenados o no, esto es O (n).

Answer 4

Este problema es una instancia unidimensional del k-medians problem, que se puede establecer de la siguiente manera. Dado un conjunto de puntos x_1 ... x_n, divida estos puntos en k conjuntos S_1 ... S_k y elija k ubicaciones y_1 ... y_k de una manera que minimice la suma sobre todo x_i de | x_i - y_f (i) | , donde y_f (i) es la ubicación correspondiente al conjunto al que se asigna x_i.

Debido al hecho de que la mediana es el population minimizer for absolute distance (i.e. L_1 norm), se sigue que cada y_j ubicación será la mediana de los elementos x en el correspondiente conjunto S_j (de ahí el nombre k-medianas). Dado que usted está buscando valores enteros, existe el tecnicismo de que si S_j contiene un número par de elementos, la mediana podría no ser un número entero, pero en tales casos elegir el siguiente número entero arriba o abajo de la mediana dará la misma suma de distancias absolutas

La heurística estándar para resolver k-medianas (y el problema relacionado y más común k-means) es iterativa, pero no se garantiza que esto produzca una solución óptima o incluso buena. La solución del problema de k-medians para espacios métricos generales es NP-hard, y encontrar aproximaciones eficientes para k-medianas es un problema de investigación abierto. La "aproximación de k-medians" en Google, por ejemplo, dará lugar a un grupo de documentos con esquemas de aproximación. http://www.cis.upenn.edu/~sudipto/mypapers/kmedian_jcss.pdf http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arr-clustering.pdf

En una dimensión cosas se vuelven más fáciles, y se puede utilizar un enfoque de programación dinámica. En this paper se describe una solución DP para el problema unidimensional de k-medias relacionado, y el código fuente en R está disponible here. Vea el documento para más detalles, pero la idea es esencialmente la misma que la propuesta por @SajalJain, y puede adaptarse fácilmente para resolver el problema de k-medians en lugar de k-means. Para j < = k y m < = n, deje que D (j, m) denote el costo de una solución de j-medians óptima para x_1 ... x_m, donde se supone que los x_i están ordenados. Tenemos la recurrencia

D(j,m) = min (D(j-1,q) + Cost(x_{q+1},...,x_m) 

donde q varía desde j-1 a M-1 y Cost es igual a la suma de las distancias absolutas a partir de la mediana. Con una implementación ingenua de O (n) de Cost, esto daría una solución DP de O (n^3k) a todo el problema. Sin embargo, esto puede ser mejorado a O (n^2k) debido al hecho de que el coste se puede actualizar en tiempo constante en lugar de calcular a partir de cero cada vez, usando el hecho de que, para una secuencia ordenada:

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 

Consulte la descripción para obtener más detalles. Excepto por el hecho de que la actualización de la función de Costo es diferente, la implementación será la misma para k-medianas que para k-medias. http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf