Minimización de la suma de distancias: problema de optimización

Question

La pregunta real es la siguiente:

McDonald's tiene previsto abrir una serie de juntas (digamos n) a lo largo de una carretera recta. Estas juntas requieren almacenes para almacenar sus alimentos. Un almacén puede almacenar alimentos para cualquier cantidad de juntas, pero tiene que ubicarse en una de las juntas solamente. McD tiene un número limitado de almacenes (por ejemplo, k) disponibles, y desea ubicarlos de manera que se minimice la distancia promedio de las juntas desde su almacén más cercano.

Dada una matriz (n elementos) de coordenadas de las uniones y un número entero 'k', devuelve una matriz de 'k' elementos que proporcionan las coordenadas del posicionamiento óptimo de los almacenes.

Lo siento, no tengo ningún ejemplo disponible ya que estoy escribiendo esto de memoria. De todos modos, una muestra podría ser:

array = {1,3,4,5,7,7,8,10,11} (n = 9)
k = 1

Ans: {7 }

Esto es lo que he estado pensando: Para k = 1, podemos simplemente averiguar la mediana del conjunto, que daría la ubicación óptima del almacén. Sin embargo, para k> 1, el conjunto dado se debe dividir en subconjuntos 'k' (disjuntos y elementos contiguos del superconjunto), y la mediana para cada subconjunto daría las ubicaciones del almacén. Sin embargo, no entiendo en qué se basan los subconjuntos 'k'. Gracias por adelantado.

EDITAR: También hay una variación de este problema: en lugar de sum/avg, minimice la distancia máxima entre una junta y su almacén más cercano. Tampoco entiendo esto ...

Answer 1

La carretera recta hace de esto un ejercicio de programación dinámica, trabajando de izquierda a derecha a lo largo de la carretera. Una solución parcial se puede describir por la ubicación del almacén más a la derecha y la cantidad de almacenes colocados. El costo de la solución parcial será la distancia total al almacén más cercano (para k fijo, minimizar esto es lo mismo que minimizar el promedio) o la distancia máxima hasta el momento al almacén más cercano.

En cada etapa ha resuelto las respuestas para las juntas en el extremo izquierdo y las ha indexado según el número de almacenes utilizados y la posición del almacén más a la derecha; debe ahorrar solo el mejor costo. Ahora considere la siguiente articulación y encuentre la mejor solución para las articulaciones N + 1 y todos los valores posibles de ky la bodega más a la derecha, usando las respuestas que ha almacenado para las articulaciones en N para acelerar esto. Una vez que haya resuelto la mejor solución de costos que cubre todas las uniones, usted sabe dónde se encuentra su almacén más a la derecha, lo que le da la ubicación de un almacén. Vuelva a la solución que tiene ese almacén como la articulación más a la derecha y descubra en qué solución se basó. Eso le da un almacén más a la derecha, por lo que puede volver a la ubicación de todos los almacenes para obtener la mejor solución.

Tiendo a hacer el gasto de resolver esto incorrectamente, pero con N empalmes y k depósitos para ubicarlo, tiene N pasos a seguir, cada uno basado en considerar no más que Nk soluciones previas, entonces creo que el costo es kN^2.

Answer 2

Esto NO es un problema de agrupamiento, es un caso especial de un problema de ubicación de una instalación. Puede resolverlo usando un paquete de programación lineal/entero general, pero debido a que el problema está en una línea, puede haber algoritmos más eficientes (y menos costosos para el software) que funcionen. Puede considerar la programación dinámica ya que probablemente haya una combinación de instalaciones que podrían eliminarse rápidamente. Consulte en el P-Median problem para obtener más información.