最小化總：優化問題

Question

實際的問題是這樣的：

麥當勞計劃開設一些關節（說N）沿直線高速公路。這些關節需要倉庫來儲存食物。倉庫可以存儲任意數量的關節的食物，但必須僅位於其中一個關節處。 McD擁有數量有限的倉庫（比如說k），並且希望將它們放置在距離最近的倉庫的平均關節距離最短的地方。

給定一個關節座標的數組（n個元素）和一個整數'k'，返回一個'k'元素數組，給出倉庫的最佳定位座標。

對不起，我沒有任何可用的例子，因爲我從內存中寫下來。無論如何，一個樣本可能是：

陣列= {1,3,4,5,7,7,8,10,11}（N = 9）
k = 1時

答案：{7 }

這就是我一直在想的：對於k = 1，我們可以簡單地找出該集合的中值，這將給出倉庫的最佳位置。然而，對於k> 1，給定的集合應該被劃分爲'k'個子集（不相交的，以及超集的連續元素），並且每個子集的中值將給出倉庫位置。但是，我不明白'k'子集應該形成在什麼基礎上。提前致謝。

編輯：這個問題也有一個變化：代替sum/avg，最小化一個關節和它最近的倉庫之間的最大距離。我也沒有得到這個..

Answer 1

直行高速公路使得這是一個動態規劃練習，從左至右沿高速公路工作。部分解決方案可以通過最右邊倉庫的位置和倉庫數量來描述。部分解決方案的成本將是到最近倉庫的總距離（固定k最小化這與最小化平均值相同）或到最近倉庫的最大距離。

在每個階段，您已經計算出最左邊的N個關節的答案，並根據所用倉庫的數量和最右邊倉庫的位置對它們進行索引 - 您只需要節省最佳成本。現在考慮下一個關節，並使用您爲N個關節存儲的答案加快速度，爲N + 1關節和所有可能的k值和最右邊的倉庫找出最佳解決方案。一旦您制定出涵蓋所有關節的最佳成本解決方案，您就會知道最右邊的倉庫在哪裏，從而爲您提供一個倉庫的位置。回到那個倉庫作爲最右邊聯合的解決方案，並找出基於哪個解決方案。這爲您提供了一個最右邊的倉庫 - 所以您可以回到所有倉庫的位置以獲得最佳解決方案。

我傾向於得到這個錯誤的工作成本，但是用N個關節和k個倉庫來放置你需要N個步驟，每個基於考慮不超過Nk以前的解決方案，所以我估計成本是千牛^ 2。

Answer 2

這不是一個聚類問題，這是一個設施位置問題的特例。你可以使用一般的整數/線性編程軟件包來解決這個問題，但由於問題在線，因此可能會有效率更高（並且更便宜的軟件）算法。您可能會考慮動態編程，因爲可能會相當快地消除這些設施的組合。查看P-Median problem瞭解更多信息。