Minimizing Sum of Distances: Optimization Problem
The actual question goes like this:
McDonald's is planning to open a number of joints (say n) along a straight highway. These joints require warehouses to store their food. A warehouse can store food for any number of joints, but has to be located at one of the joints only. McD has a limited number of warehouses (say k) available, and wants to place them in such a way that the average distance of joints from their nearest warehouse is minimized.
Given an array (n elements) of coordinates of the joints and an integer 'k', return an array of 'k' elements giving the coordinates of the optimal positioning of warehouses.
Sorry, I don't have any examples available since I'm writing this down from memory. Anyway, one sample could be:
array={1,3,4,5,7,7,8,10,11} (n=9)
k = 1
Ответ: {7}
Это то, о чем я думал: для k = 1 мы можем просто определить медиану набора, которая даст оптимальное местоположение склада. Однако при k> 1 данный набор должен быть разделен на «k» подмножеств (непересекающихся и смежных элементов надмножества), и медиана для каждого подмножества даст места на складе. Однако я не понимаю, на каком основании должны формироваться подмножества 'k'. Заранее спасибо.
РЕДАКТИРОВАТЬ: Существует также вариант этой проблемы: вместо суммы / среднего, минимизируйте максимальное расстояние между суставом и его ближайшим складом. Я тоже этого не понимаю ..
2 ответа
Прямая магистраль превращает это упражнение в динамическое программирование, работая слева направо вдоль трассы. Частичное решение можно описать расположением самого правого склада и количеством размещенных складов. Стоимость частичного решения будет равна общему расстоянию до ближайшего склада (для фиксированного k минимизация это то же самое, что минимизация среднего значения) или максимальному расстоянию до ближайшего склада.
На каждом этапе вы вычислили ответы для N крайних левых соединений и проиндексировали их по количеству используемых складов и положению крайнего правого склада — вам нужно сохранить только наилучшую стоимость. Теперь рассмотрим следующее соединение и выработайте лучшее решение для N + 1 соединений и всех возможных значений k и крайнего правого склада, используя ответы, которые вы сохранили для N соединений, чтобы ускорить это. После того, как вы разработали оптимальное решение по стоимости, охватывающее все соединения, вы знаете, где находится его самый правый склад, что дает вам местонахождение одного склада. Вернитесь к решению, в котором этот склад является крайним правым соединением, и выясните, на каком решении оно было основано. Это дает вам еще один самый правый склад, и вы можете вернуться к местонахождению всех складов для наилучшего решения.
Я склонен неправильно понимать стоимость решения этого вопроса, но с N суставами и k складами нужно сделать N шагов, каждый из которых основан на рассмотрении не более чем Nk предыдущих решений, поэтому я считаю, что стоимость равна kN. ^ 2.
Это НЕ проблема кластеризации, это частный случай проблемы размещения объекта. Вы можете решить ее, используя общий пакет целочисленного/линейного программирования, но, поскольку проблема находится в строке, могут быть более эффективные (и менее дорогие с точки зрения программного обеспечения) алгоритмы, которые будут работать. Вы можете подумать о динамическом программировании, поскольку, вероятно, существует комбинация средств, которые можно довольно быстро устранить. Изучите проблему P-медианы для получения дополнительной информации.