Минимизация суммы расстояний: проблема оптимизации

Question

Фактический вопрос звучит так:

McDonald's планирует открыть несколько стыков (скажем, n) вдоль прямой магистрали. Эти суставы требуют складов для хранения своей еды. Склад может хранить продукты питания для любого количества соединений, но должен располагаться только на одном из них. McD имеет ограниченное количество доступных складов (скажем, k) и хочет разместить их таким образом, чтобы среднее расстояние стыков от ближайшего склада было минимальным.

Учитывая массив (n элементов) координат суставов и целое число «k», вернуть массив «k» элементов, дающий координаты оптимального расположения складов.

Извините, у меня нет доступных примеров, так как я записываю это из памяти. В любом случае, один образец может быть:

массив = {1,3,4,5,7,7,8,10,11} (n = 9)
к = 1

Ответ: {7}

Это то, о чем я думал: для k = 1 мы можем просто определить медиану набора, которая дала бы оптимальное местоположение склада. Однако при k> 1 данный набор должен быть разделен на «k» подмножеств (непересекающихся и смежных элементов надмножества), и медиана для каждого подмножества даст места на складе. Однако я не понимаю, на каком основании должны формироваться подмножества 'k'. Заранее спасибо.

РЕДАКТИРОВАТЬ: Существует также вариант этой проблемы: вместо суммы / среднего, минимизировать максимальное расстояние между суставом и ближайшим складом. Я тоже этого не понимаю ..

Answer 1

Это НЕ проблема кластеризации, это особый случай проблемы расположения объекта. Вы можете решить ее, используя общий пакет целочисленного / линейного программирования, но поскольку проблема стоит на одном месте, могут быть более эффективные (и менее дорогие программные) алгоритмы, которые будут работать. Вы могли бы рассмотреть динамическое программирование, так как, вероятно, есть комбинация средств, которые могут быть устранены довольно быстро. Посмотрите на проблему P-Median для получения дополнительной информации.

Answer 2

Прямое шоссе делает это упражнением в динамическом программировании, работая слева направо вдоль шоссе.Частичное решение может быть описано расположением самого правого склада и количеством размещенных складов.Стоимость частичного решения будет равна общему расстоянию до ближайшего склада (для фиксированного k минимизация аналогична минимизации среднего значения) или максимальному расстоянию до ближайшего склада.

На каждом этапе выразработали ответы для крайних левых N соединений и проиндексировали их по количеству используемых складов и положению самого правого склада - вам нужно сохранить только лучшие затраты.Теперь рассмотрим следующее соединение и разработаем лучшее решение для соединений N + 1 и всех возможных значений k и самого правого склада, используя ответы, которые вы сохранили для N соединений, чтобы ускорить это.После того, как вы разработали наилучшее решение по стоимости, охватывающее все соединения, вы знаете, где находится его самый правый склад, что дает вам местоположение одного склада.Вернитесь к решению, в котором этот склад является самым правым соединением, и выясните, на каком решении это основано.Это дает вам еще один самый правильный склад - и вы сможете вернуться к месту расположения всех складов, чтобы найти наилучшее решение.

Я, как правило, получаю неправильную цену, но с N стыкамии k складов для размещения у вас есть N шагов, каждый из которых основан на рассмотрении не более Nk предыдущих решений, поэтому я считаю, что стоимость kN ^ 2.